TreeSet en Java – Part 1

TreeSet es una de las implementaciones más importantes de la interfaz SortedSet en Java que utiliza un árbol para el almacenamiento. El orden de los elementos se mantiene mediante un conjunto utilizando su orden natural, se proporcione o no un comparador explícito . Esto debe ser consistente con equals si se quiere implementar correctamente la interfaz Set . 

También se puede ordenar mediante un comparador proporcionado en el momento de la creación del conjunto, según el constructor que se utilice. TreeSet implementa una interfaz NavigableSet al heredar la clase AbstractSet .

Se puede percibir claramente en la imagen de arriba que el conjunto navegable extiende la interfaz del conjunto ordenado. Dado que un conjunto no conserva el orden de inserción, la interfaz de conjunto navegable proporciona la implementación para navegar por el Conjunto. La clase que implementa el conjunto navegable es un TreeSet que es una implementación de un árbol autoequilibrado. Por lo tanto, esta interfaz nos proporciona una forma de navegar a través de este árbol. 

Nota:

• Se dice que un objeto es comparable si y solo si la clase correspondiente implementa una interfaz Comparable .
• La clase String y todas las clases Wrapper ya implementan una interfaz Comparable, pero la clase StringBuffer  implementa una interfaz Comparable. Por lo tanto, NO obtenemos una ClassCastException en el ejemplo anterior.
• Para un conjunto de árbol vacío, al intentar insertar nulo como el primer valor, se obtendrá NPE de JDK 7. Desde JDK 7 en adelante, TreeSet no acepta nulo en absoluto. Sin embargo, hasta JDK 6, nulo se aceptaba como el primer valor, pero cualquier inserción de más valores nulos en el TreeSet generaba NullPointerException. Por lo tanto, se consideró un error y, por lo tanto, se eliminó en JDK 7.
• TreeSet sirve como una excelente opción para almacenar grandes cantidades de información ordenada a la que se supone que se debe acceder rápidamente debido a su acceso y tiempo de recuperación más rápidos.
• La inserción de valores nulos en un TreeSet arroja NullPointerException porque, mientras se inserta un valor nulo, se compara con los elementos existentes, y el valor nulo no se puede comparar con ningún valor.

¿Cómo funciona TreeSet internamente?

TreeSet es básicamente una implementación de un árbol de búsqueda binario autoequilibrado como un árbol rojo-negro . Por lo tanto, operaciones como agregar, eliminar y buscar requieren un tiempo O(log(N)). La razón es que en un árbol autoequilibrado, se asegura que la altura del árbol sea siempre O(log(N)) para todas las operaciones. Por lo tanto, esta se considera una de las estructuras de datos más eficientes para almacenar los grandes datos ordenados y realizar operaciones en ellos. Sin embargo, operaciones como imprimir N elementos en el orden ordenado toman O(N) tiempo.

Ahora analicemos el TreeSet sincronizado antes de seguir adelante. La implementación de un TreeSet no está sincronizada. Esto significa que si varios subprocesos acceden a un conjunto de árboles al mismo tiempo y al menos uno de los subprocesos modifica el conjunto, debe sincronizarse externamente. Esto normalmente se logra sincronizando algún objeto que encapsule naturalmente el conjunto. Si no existe tal objeto, el conjunto debe «envolverse» utilizando el método Collections.synchronizedSortedSet . Es mejor hacerlo en el momento de la creación, para evitar el acceso no sincronizado accidental al conjunto. Se puede lograr como se muestra a continuación de la siguiente manera:

TreeSet ts = new TreeSet(); 
Set syncSet = Collections.synchronziedSet(ts); 

Los constructores de la clase TreeSet son los siguientes:

Para crear un TreeSet, necesitamos crear un objeto de la clase TreeSet. La clase TreeSet consta de varios constructores que permiten la posible creación del TreeSet. Los siguientes son los constructores disponibles en esta clase:

• TreeSet(): este constructor se usa para crear un objeto TreeSet vacío en el que los elementos se almacenarán en el orden de clasificación natural predeterminado.

Sintaxis: si deseamos crear un TreeSet vacío con el nombre ts, entonces, se puede crear como: 

TreeSet ts = new TreeSet(); 

• TreeSet(Comparator): este constructor se usa para crear un objeto TreeSet vacío en el que los elementos necesitarán una especificación externa del orden de clasificación.

Sintaxis: si deseamos crear un TreeSet vacío con el nombre ts con un fenómeno de clasificación externo, entonces, se puede crear como:

TreeSet ts = new TreeSet(Comparator comp); 

• TreeSet (Colección): este constructor se usa para construir un objeto TreeSet que contiene todos los elementos de la colección dada en la que los elementos se almacenarán en el orden de clasificación natural predeterminado. En resumen, este constructor se usa cuando se necesita cualquier conversión de cualquier objeto Collection a objeto TreeSet.

Sintaxis: Si deseamos crear un TreeSet con el nombre ts, entonces, se puede crear de la siguiente manera:

TreeSet t = new TreeSet(Collection col);  

• TreeSet(SortedSet): este constructor se usa para construir un objeto TreeSet que contiene todos los elementos del conjunto ordenado dado en el que los elementos se almacenarán en el orden de clasificación natural predeterminado. En resumen, este constructor se usa para convertir el objeto SortedSet en el objeto TreeSet.

Sintaxis: Si deseamos crear un TreeSet con el nombre ts, entonces, se puede crear de la siguiente manera:

TreeSet t = new TreeSet(SortedSet s);

Los métodos en la clase TreeSet se muestran a continuación en formato tabular que más adelante implementaremos para mostrar en la parte de implementación.

TreeSet implementa SortedSet para que tenga la disponibilidad de todos los métodos en las interfaces Collection, Set y SortedSet . Los siguientes son los métodos en la interfaz de Treeset. En la siguiente tabla, el «?» significa que el método funciona con cualquier tipo de objeto, incluidos los objetos definidos por el usuario. 

Ilustración: La siguiente implementación demuestra cómo crear y usar un TreeSet.

// Java program to Illustrate Working of  TreeSet 
  
// Importing required utility classes
import java.util.*;
  
// Main class
class GFG {
  
    // Main driver method
    public static void main(String[] args)
    {
        // Creating a Set interface with reference to
        // TreeSet
        Set<String> ts1 = new TreeSet<>();
  
        // Elements are added using add() method
        ts1.add("A");
        ts1.add("B");
        ts1.add("C");
  
        // Duplicates will not get insert
        ts1.add("C");
  
        // Elements get stored in default natural
        // Sorting Order(Ascending)
        System.out.println(ts1);
    }
}

[A, B, C]

Implementación:

Aquí realizaremos varias operaciones sobre el objeto TreeSet para familiarizarnos con los métodos y conceptos de TreeSet en Java. Veamos cómo realizar algunas operaciones de uso frecuente en el TreeSet. Se enumeran de la siguiente manera:

• Agregar elementos
• Acceder a elementos
• Quitar elementos
• Iterando a través de elementos

Ahora analicemos cada operación individualmente una por una más adelante junto con la comprensión con la ayuda de un programa Java limpio.

Operación 1: Adición de elementos

Para agregar un elemento al TreeSet, podemos usar el método add() . Sin embargo, el orden de inserción no se conserva en el TreeSet. Internamente, para cada elemento, los valores se comparan y ordenan en orden ascendente. Debemos tener en cuenta que los elementos duplicados no están permitidos y todos los elementos duplicados se ignoran. Y también, los valores nulos no son aceptados por el TreeSet.

Ejemplo

// Java code to Illustrate Addition of Elements to TreeSet
  
// Importing utility classes
import java.util.*;
  
// Main class
class GFG {
  
    // Main driver method
    public static void main(String[] args)
    {
        // Creating a Set interface with
        // reference to TreeSet class
        // Declaring object of string type
        Set<String> ts = new TreeSet<>();
  
        // Elements are added using add() method
        ts.add("Geek");
        ts.add("For");
        ts.add("Geeks");
  
        // Print all elements inside object
        System.out.println(ts);
    }
}

[For, Geek, Geeks]

Operación 2: Acceso a los Elementos

Después de agregar los elementos, si deseamos acceder a los elementos, podemos usar métodos incorporados como contains() , first() , last() , etc. 

Ejemplo

// Java code to Illustrate Working of TreeSet by
// Accessing the Element of TreeSet
  
// Importing utility classes
import java.util.*;
  
// Main class 
class GFG {
  
    // Main driver method 
    public static void main(String[] args)
    {
        // Creating a NavigableSet object  with 
      // reference to TreeSet class 
        NavigableSet<String> ts = new TreeSet<>();
  
        // Elements are added using add() method
        ts.add("Geek");
        ts.add("For");
        ts.add("Geeks");
  
         // Printing the elements inside the TreeSet object 
        System.out.println("Tree Set is " + ts);
  
        String check = "Geeks";
  
        // Check if the above string exists in
        // the treeset or not
        System.out.println("Contains " + check + " "
                           + ts.contains(check));
  
        // Print the first element in
        // the TreeSet
        System.out.println("First Value " + ts.first());
  
        // Print the last element in
        // the TreeSet
        System.out.println("Last Value " + ts.last());
  
        String val = "Geek";
  
        // Find the values just greater
        // and smaller than the above string
        System.out.println("Higher " + ts.higher(val));
        System.out.println("Lower " + ts.lower(val));
    }
}

Tree Set is [For, Geek, Geeks]
Contains Geeks true
First Value For
Last Value Geeks
Higher Geeks
Lower For

Operación 3: Eliminación de los valores

Los valores se pueden eliminar del TreeSet mediante el método remove() . Hay varios otros métodos que se utilizan para eliminar el primer valor o el último valor. 

Ejemplo

// Java Program to Illustrate Removal of Elements
// in a TreeSet
  
// Importing utility classes
import java.util.*;
  
// Main class
class GFG {
  
    // Main driver method
    public static void main(String[] args)
    {
        // Creating an object of NavigableSet
        // with reference to TreeSet class
        // Declaring object of string type
        NavigableSet<String> ts = new TreeSet<>();
  
        // Elements are added
        // using add() method
        ts.add("Geek");
        ts.add("For");
        ts.add("Geeks");
        ts.add("A");
        ts.add("B");
        ts.add("Z");
  
        // Print and display initial elements of TreeSet
        System.out.println("Initial TreeSet " + ts);
  
        // Removing a specific existing element inserted
        // above
        ts.remove("B");
  
        // Printing the updated TreeSet
        System.out.println("After removing element " + ts);
  
        // Now removing the first element
        // using pollFirst() method
        ts.pollFirst();
  
        // Again printing the updated TreeSet
        System.out.println("After removing first " + ts);
  
        // Removing the last element
        // using pollLast() method
        ts.pollLast();
  
        // Lastly printing the elements of TreeSet remaining
        // to figure out pollLast() method
        System.out.println("After removing last " + ts);
    }
}

Initial TreeSet [A, B, For, Geek, Geeks, Z]
After removing element [A, For, Geek, Geeks, Z]
After removing first [For, Geek, Geeks, Z]
After removing last [For, Geek, Geeks]

Operación 4: Iterando a través del TreeSet

Hay varias formas de iterar a través del TreeSet. El más famoso es usar el bucle for mejorado . y los geeks en su mayoría estarían iterando los elementos con este enfoque mientras practican preguntas sobre TreeSet, ya que se usa con más frecuencia cuando se trata de problemas de árboles, mapas y gráficos. 

Ejemplo

// Java Program to Illustrate Working of TreeSet
  
// Importing utility classes
import java.util.*;
  
// Main class
class GFG {
  
    // Main driver method
    public static void main(String[] args)
    {
        // Creating an object of Set with reference to
        // TreeSet class
  
        // Note: You can refer above media if geek
        // is confused in programs why we are not
        // directly creating TreeSet object
        Set<String> ts = new TreeSet<>();
  
        // Adding elements in above object
        // using add() method
        ts.add("Geek");
        ts.add("For");
        ts.add("Geeks");
        ts.add("A");
        ts.add("B");
        ts.add("Z");
  
        // Now we will be using for each loop in order
        // to iterate through the TreeSet
        for (String value : ts)
  
            // Printing the values inside the object
            System.out.print(value + ", ");
  
        System.out.println();
    }
}

A, B, For, Geek, Geeks, Z,

Características de un TreeSet:

1. TreeSet implementa la interfaz SortedSet . Por lo tanto, no se permiten valores duplicados.
2. Los objetos en un TreeSet se almacenan ordenados y en orden ascendente.
3. TreeSet no conserva el orden de inserción de los elementos, pero los elementos se ordenan por claves.
4. Si dependemos del orden de clasificación natural predeterminado, los objetos que se insertan en el árbol deben ser homogéneos y comparables. TreeSet no permite la inserción de objetos heterogéneos. Lanzará una classCastException en tiempo de ejecución si intentamos agregar objetos heterogéneos.
5. El TreeSet solo puede aceptar tipos genéricos que sean comparables.
   Por ejemplo, la clase StringBuffer implementa la interfaz Comparable

// Java code to illustrate What if Heterogeneous 
// Objects are Inserted
  
// Importing all utility classes
import java.util.*;
  
// Main class
class GFG {
  
    // Main driver method
    public static void main(String[] args)
    {
  
        // Object creation
        Set<StringBuffer> ts = new TreeSet<>();
  
        // Adding elements to above object
        // using add() method
        ts.add(new StringBuffer("A"));
        ts.add(new StringBuffer("Z"));
        ts.add(new StringBuffer("L"));
        ts.add(new StringBuffer("B"));
        ts.add(new StringBuffer("O"));
        ts.add(new StringBuffer(1));
  
        // Note: StringBuffer implements Comparable
        // interface
  
        // Printing the elements
        System.out.println(ts);
    }
}

[, A, B, L, O, Z]