TreeSet: Collections en Java - Blog de Programación

TreeSet es parte también de la API de Java Collection, antes mencionamos otras implementaciones de la interfaz NavigableSet, ésta de SortedSet y a su vez ella de Set pero ahora veremos esta nueva clase y el funcionamiento interno

¿Qué es TreeSet?

Es un estructura de datos de un árbol, el cual es de tipo “Árbol binario balanceado de búsqueda” (balanced-binary search tree).

El TreeSet es similar al HashSet en que previene duplicados, también mantiene las lista ordenada por criterio, eso cuando le dejamos por defecto que use el método compareTo() implementado en el tipo de dato que usará TreeSet, pero podemos pasarle también al constructor de TreeSet un objeto Comparator.
TreeSet funciona de manera muy similar al método sort(): tiene la opción de usar el método compareTo() del elemento, asumiendo que el tipo de elemento implementó la interfaz Comparable, o puede usar un Comparator personalizado que sabe cómo ordenar los elementos en el conjunto . Para usar un comparador personalizado, llame al constructor TreeSet que toma un comparador.

import java.util.*;

class Book implements Comparable < Book > {
    private String title;
    public Book(String t) {
        title = t;
    }
    public String getTitle(){
        return this.title;
    }
    public int compareTo(Book other) {
        return title.compareTo(other.title);
    }
    public String toString(){
        return getTitle();
    }
}

class BookCompare implements Comparator < Book > {
    public int compare(Book one, Book two) {
        return one.getTitle().compareTo(two.getTitle());
    }
}
public class Main {
    public static void  main(String[] args) {
        Book b1 = new Book("How Cats Work");
        Book b2 = new Book("Remix your Body");
        Book b3 = new Book("Finding Emo");
        BookCompare bookCompare = new BookCompare();
        Set < Book > tree = new TreeSet < > (bookCompare);
        tree.add(b1);
        tree.add(b2);
        tree.add(b3);
        System.out.println(tree);
    }
}

import java.util.*;

class Book implements Comparable < Book > {

private String title;

public Book(String t) {

title = t;

}

public String getTitle(){

return this.title;

}

public int compareTo(Book other) {

return title.compareTo(other.title);

}

public String toString(){

return getTitle();

}

class BookCompare implements Comparator < Book > {

public int compare(Book one, Book two) {

return one.getTitle().compareTo(two.getTitle());

}

public class Main {

public static void main(String[] args) {

Book b1 = new Book("How Cats Work");

Book b2 = new Book("Remix your Body");

Book b3 = new Book("Finding Emo");

BookCompare bookCompare = new BookCompare();

Set < Book > tree = new TreeSet < > (bookCompare);

tree.add(b1);

tree.add(b2);

tree.add(b3);

System.out.println(tree);

}

Puedes ejecutar el código aquí: https://paiza.io/projects/YqWsPo9SgyAhv0OhUNi_7w

¿Cuáles son las características de TreeSet?

-Permite criterio de ordenación donde se puede usar Comparable y/o Comparator
-Su tarea principal es búsqueda y eliminación de elementos
-No permite duplicados
-No permite nulos si la ordenación natural es usada o la clase Comparator no acepta nulos
-Los elementos en el Set deben ser de un tipo de Clase que implementen la interfaz Comparable caso contrario no trabajaran en tiempo de Ejecución con al menos dos elementos agregados

¿Cuándo usar TreeSet?

Los árboles son la estructura de datos que elegiría para una aplicación que necesita una inserción y recuperación rápidas de elementos individuales pero que también requiere que se mantengan ordenados.

Por ejemplo, suponga que desea hacer coincidir todas las palabras de un conjunto con un prefijo determinado, un requisito común en las aplicaciones visuales donde, idealmente, un menú desplegable debería mostrar todos los elementos posibles que coinciden con el prefijo que el usuario ha escrito.

Una tabla hash no puede devolver sus elementos ordenados y una lista no puede recuperar sus elementos rápidamente por su contenido, pero un árbol puede hacer ambas cosas y tener como máximo dos hijos

¿Cómo funciona internamente?

Veamos el siguiente ejemplo con código:

public class Main {
    public static void main(String[] args) throws Exception {
        // Your code here!
        String frase="no amemos de palabra y con la boca, sino con obras y de verdad.";
        String[] fraseSplit=frase.split(" ");
        TreeSet<String> arbolPalabra=new TreeSet<String>();
        arbolPalabra.addAll(Arrays.asList(fraseSplit));
        for(String palabra:arbolPalabra){
            System.out.println(palabra);
        }
        
    }
}

public class Main {

public static void main(String[] args) throws Exception {

// Your code here!

String frase="no amemos de palabra y con la boca, sino con obras y de verdad.";

String[] fraseSplit=frase.split(" ");

TreeSet<String> arbolPalabra=new TreeSet<String>();

arbolPalabra.addAll(Arrays.asList(fraseSplit));

for(String palabra:arbolPalabra){

System.out.println(palabra);

}

Puedes compilarlo aquí: https://paiza.io/projects/C_FAeh4n6qFJvFCFX0EDCQ?language=java

Como veras en el resultado, vemos que se han ordenado de forma alfabética y no aceptó palabras repetidas, internamente se comporta como un árbol de búsqueda binaria:
a) Se coloca la primera palabra de la lista “no” como raíz inicial, luego la siguiente palabra “amemos” comienza a comparar por orden alfabético y pasará a ser un hijo del nodo raíz pero al lado izquierdo por ser anterior al orden alfabético, para el siguiente nodo con la palabra “de” se compara primero el nodo raíz “no”, esto implica que será anterior al orden alfabético y allí se encuentra ocupado por el nodo “amemos”, nuevamente compara y al verse superior en orden, pasa a ser el nodo hijo derecho, quedaría como en la imagen:

b) Para “palabra”, aquí comparamos con el nodo raíz “no”, este vendrá a ser su hijo nodo derecho.
c) El siguiente paso se coloca la palabra “y”, siguiendo las reglas de árboles binarios, solo pueden tener 2 nodos hijos, viene a colocarse como hijo de “palabra” pero como nodo derecho, de esa manera colocamos “con”, “la”, “boca,” y “sino”.
d) El siguiente caso es cuando evaluamos “con” nuevamente (es la que sigue según la frase), viene a compararse con el nodo raíz, luego con “amemos”, después con “de”, y se compara nuevamente con “con”, aquí es donde se descarta, ya que en TreeSet no acepta repetidos, el árbol queda como la imagen:

Continuemos…

e) Las palabras quedan como en la imagen, usando el criterio de comparación de orden alfabético.

f) el resultado final, sobre cómo se hará la búsqueda y/o impresión en pantalla se realizará siguiendo estas reglas:
Se visita los hijos del nodo del lado izquierdo caso contrario se marca y luego visitamos el lado derecho, si existe el nodo derecho hijo, y así hasta completar de visitar los nodos y volvemos a subir hasta el nodo raíz, el cual marcaremos y luego visitamos el nodo hijo derecho, realizamos los mismos pasos anteriores.

Para terminar

Visitamos “no”, luego a hijo izquierdo “amemos”, como no tiene hijo izquierdo, marcamos, esto implica que será nuestra primera palabra a mostrar o imprimir en consola, luego de ello vamos al nodo derecho hijo “de”, el cual tiene otro hijo izquierdo “con”, preguntamos si existe hijo nodo izquierdo, este es “boca”, el cual marcaremos como segunda palabra y mostrará como otra palabra a imprimir en consola

Después sube a “con” y lo marca, será la tercera en imprimirse, luego sube a “de” y será nuestra cuarta palabra en imprimirse, ya no imprimimos “amemos”, porque está marcado y por regla solo las que no tienen hijos izquierdos o se visiten de abajo a arriba nuevamente, en este caso ahora visitamos a “la” y lo imprimimos en consola, ya tenemos

"amemos","boca,","con","de","la"

1	"amemos","boca,","con","de","la"

Marcamos “no” e imprimimos, luego visitamos su nodo derecho y repetimos lo mismo: marcamos “palabra” e imprimimos, pues no tiene nodo hijo izquierdo, luego visitamos el derecho, “y”, luego “sino” y “obras” para imprimir y marcar ésta, así hasta obtener

"amemos","boca,","con","de","la", "no","obras","palabra","sino","verdad.","y"

1	"amemos","boca,","con","de","la", "no","obras","palabra","sino","verdad.","y"

Análisis de Complejidad

La eficiencia con la Notación O para las operaciones Add, Remove, Contains y Next son de O(log n)

Fuentes

Data Structure and Problem Solvin Using Java, Wiss, Mark A.
Data Structure and the Java Collections Framework
Java Generics and Collections ( Maurice Naftalin, Philip Wadler)
Advanced Java A Book for Advanced Users
Java Language Features 2nd Edition
Head First Java
https://www.youtube.com/watch?v=MbUzYzxjZmk