¿Cuál es la complejidad temporal de las operaciones ordenadas en TreeSet?

Posteriormente a consultar con expertos en la materia, programadores de varias áreas y maestros hemos dado con la solución a la pregunta y la plasmamos en este post.

Solución:

En realidad, habría pensado que todas esas operaciones van a ser O(logN) para una implementación general.

• Para first() y last() ser O(1) la implementación de TreeSet necesitaría mantener un puntero a los nodos de hoja más a la izquierda y más a la derecha en el árbol, respectivamente. Mantenerlos agrega un costo constante a cada inserción y al menos un costo constante a cada eliminación. En realidad, la implementación probablemente encontrará los nodos más a la izquierda/derecha sobre la marcha… lo cual es una O(logN) operación.

• los lower() y higher() Los métodos tienen que hacer el mismo trabajo que get y son por lo tanto O(logN).

Por supuesto, puede verificar el código fuente usted mismo para ver qué sucede realmente. (Como otras personas han hecho: ver más abajo).

Parece que tanto first() como last() serán O(log n) y no O(1) según la implementación (sun jdk 1.6.0_23) de TreeMap que utiliza TreeSet de forma predeterminada:

 /**
 * Returns the first Entry in the TreeMap (according to the TreeMap's
 * key-sort function).  Returns null if the TreeMap is empty.
 */
final Entry getFirstEntry() 
    Entry p = root;
    if (p != null)
        while (p.left != null)
            p = p.left;
    return p;


/**
 * Returns the last Entry in the TreeMap (according to the TreeMap's
 * key-sort function).  Returns null if the TreeMap is empty.
 */
final Entry getLastEntry() 
    Entry p = root;
    if (p != null)
        while (p.right != null)
            p = p.right;
    return p;

Finalizando este artículo puedes encontrar las ilustraciones de otros administradores, tú todavía puedes mostrar el tuyo si lo crees conveniente.

---

---

Utiliza Nuestro Buscador