Conjunto de árboles en Java

Java proporciona un amplio conjunto de estructuras de datos para trabajar de manera eficiente con colecciones de elementos. Una de esas estructuras de datos es TreeSet, una implementación de un árbol rojo-negro en Java. TreeSet mantiene un orden ordenado para almacenar elementos únicos. Los principiantes pueden encontrar el uso de la clase Java TreeSet un poco desafiante al principio. En este artículo, descubriremos cómo usar TreeSet , explicaremos sus conceptos centrales y brindaremos ejemplos de código para ayudarlo a comenzar a incorporar TreeSet en sus proyectos Java.

Estructura TreeSet: árbol rojo-negro

Como mencionamos antes, la estructura de clases Java TreeSet se implementa como un árbol de búsqueda binario autoequilibrado conocido como árbol Rojo-Negro. Expliquemos qué es esto... Un árbol rojo-negro representa una estructura de datos de búsqueda binaria equilibrada que se emplea comúnmente para almacenar y organizar datos ordenados. Deriva su nombre de las propiedades que mantienen su equilibrio:

• Cada nodo del árbol es rojo o negro.
• La raíz del árbol Rojo-Negro es siempre negra.
• Todos los nodos hoja (nodos NIL o enlaces nulos) son negros.
• Si un nodo del árbol es rojo, sus hijos son negros.
• Cada camino simple desde un nodo hasta sus nodos descendientes contiene el mismo número de nodos negros.

Los árboles rojo-negro exhiben un rendimiento eficiente para las operaciones de inserción, eliminación y búsqueda de elementos al garantizar el equilibrio. Esto garantiza que la altura del árbol sigue siendo proporcional al logaritmo del número de nodos que contiene, lo que da como resultado una complejidad temporal logarítmica para las operaciones. Los árboles rojo-negro encuentran amplias aplicaciones en diversos dominios, incluida la implementación de árboles de búsqueda equilibrados en lenguajes de programación, bases de datos (por ejemplo, estructuras de índices internos) y otros escenarios donde son necesarios un almacenamiento y operaciones eficientes con datos ordenados.

Características y debilidades de TreeSet

TreeSet proporciona varias características clave que lo convierten en una herramienta valiosa para gestionar colecciones de objetos de forma ordenada. Ventajas:

• Mantenimiento automático de elementos ordenados. Al agregar o eliminar elementos, la estructura de árbol se ajusta para mantenerlos ordenados. Esto elimina la necesidad de clasificación manual y proporciona un acceso eficiente en orden ascendente o descendente.
• Operaciones eficientes de búsqueda, inserción y eliminación. Utiliza una estructura de árbol de búsqueda binaria, lo que permite estas operaciones con una complejidad temporal de O(log N) . Aquí N es el número de elementos.
• TreeSet garantiza la singularidad de los elementos utilizando su orden natural o un Comparador personalizado . Esto resulta útil cuando se trabaja con colecciones que requieren elementos distintos.

Limitaciones:

• Ligeramente más lento que HashSet debido a que mantiene el orden.
• No permite elementos nulos, ya que se basa en el orden natural o en un Comparador personalizado para la comparación de elementos.

Java TreeSet: ejemplo de operaciones principales

Ahora demostremos cómo crear un TreeSet en Java, obtener el tamaño de la colección, agregarle elementos, eliminarlos y verificar si un elemento está en el TreeSet . Estos ejemplos de código demuestran las operaciones principales cuando se trabaja con TreeSet : crear una instancia, agregar elementos, eliminar elementos, verificar la presencia de elementos y obtener el tamaño de TreeSet . Crear una instancia de TreeSet y agregar elementos:

// Creating a TreeSet of Integer type
TreeSet<Integer> numbers = new TreeSet<>();

// Adding elements to the TreeSet
numbers.add(18);
numbers.add(2);
numbers.add(7);
numbers.add(28);

System.out.println(numbers); // Output: [2, 7, 18, 28]

Aquí usamos el método add() para sumar 4 números en nuestro TreeSet . Si creamos un método principal y ejecutamos el programa, la salida estará en orden (2, 7, 18, 28). Eliminando elementos de TreeSet :

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

names.add("Johnny");
names.add("Ivy");
names.add("David");
names.add("Ricky");

// Removing an element from the TreeSet
names.remove("David");

System.out.println(names); // Output: [Ivy, Johnny, Ricky]

Comprobando la presencia de un elemento en TreeSet :

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

musicalInstrument.add("Piano");
musicalInstrument.add("Drums");
musicalInstrumentfruits.add("Violin");
musicalInstrument.add("Double Bass");

// Checking if an element exists in the TreeSet
boolean containsPiano = musicalInstrument.contains("Piano");
boolean containsCello = musicalInstrument.contains("Cello");

System.out.println(containsPiano); // Output: true
System.out.println(containsCello); // Output: false

Obteniendo el tamaño de TreeSet :

TreeSet<Character> letters = new TreeSet<>();

letters.add('A');
letters.add('B');
letters.add('C');
letters.add('D');

// Getting the size of the TreeSet
int size = letters.size();

System.out.println(size); // Output: 4

Ordenar e iterar en TreeSet

TreeSet en Java proporciona potentes funciones para ordenar e iterar sobre colecciones de elementos. En esta sección, exploraremos varias técnicas para ordenar elementos, iterar sobre TreeSet y realizar búsquedas basadas en rangos utilizando los métodos subSet() , headSet() y tailSet() . De forma predeterminada, TreeSet mantiene automáticamente los elementos ordenados. Sin embargo, podemos personalizar el comportamiento de clasificación proporcionando un Comparador durante la creación de TreeSet . Veamos un ejemplo:

import java.util.Comparator;
import java.util.TreeSet;

public class TreeSetSortingExample {
  public static void main(String[] args) {
    // Create a TreeSet with custom sorting
    TreeSet<Integer> numbers = new TreeSet<>(Comparator.reverseOrder());

    // Add elements to the TreeSet
    numbers.add(5);
    numbers.add(3);
    numbers.add(7);
    numbers.add(1);

    System.out.println(numbers); // Output: [7, 5, 3, 1]
  }
}

En el código anterior, creamos un TreeSet de tipo Integer y proporcionamos un Comparador personalizado usando Comparator.reverseOrder() para ordenar los elementos en orden descendente. El TreeSet resultante contendrá elementos [7, 5, 3, 1] . Hay varias formas de iterar sobre TreeSet . Podemos usar un iterador o utilizar el bucle for-each mejorado . Veamos ejemplos de ambos enfoques:

import java.util.TreeSet;
import java.util.Iterator;

public class TreeSetIterationExample {
  public static void main(String[] args) {
    TreeSet<String> names = new TreeSet<>();

    names.add("Johnny");
    names.add("Ivy");
    names.add("Ricky");
    names.add("David");

    // Iterating using an iterator
    Iterator<String> iterator = names.iterator();
    while (iterator.hasNext()) {
      String name = iterator.next();
      System.out.println(name);
    }

    // Iterating using the enhanced for-each loop
    for (String name : names) {
      System.out.println(name);
    }
  }
}

En el código anterior, creamos un TreeSet llamado nombres y agregamos algunos elementos. Luego demostramos dos formas de iterar sobre TreeSet : usando un iterador y utilizando el bucle for-each mejorado. TreeSet proporciona métodos para realizar búsquedas basadas en rangos, lo que nos permite recuperar subconjuntos de elementos según criterios específicos. Los tres métodos principales para búsquedas basadas en rangos son:

• subSet(E fromElement, E toElement) : devuelve un subconjunto de elementos desde fromElement (inclusive) hasta toElement (exclusivo).
• headSet(E toElement) : devuelve un subconjunto de elementos menores que toElement .
• tailSet(E fromElement) : devuelve un subconjunto de elementos mayor o igual que fromElement .

Veamos un ejemplo:

import java.util.TreeSet;

public class TreeSetRangeSearchExample {
  public static void main(String[] args) {
    TreeSet<Integer> numbers = new TreeSet<>();

    numbers.add(1);
    numbers.add(3);
    numbers.add(5);
    numbers.add(7);
    numbers.add(9);

    // Performing range-based search using subSet()
    TreeSet<Integer> subset = new TreeSet<>(numbers.subSet(3, 8));
    System.out.println(subset); // Output: [3, 5, 7]

    // Performing range-based search using headSet()
    TreeSet<Integer> headSet = new TreeSet<>(numbers.headSet(6));
    System.out.println(headSet); // Output: [1, 3, 5]

    // Performing range-based search using tailSet()
     TreeSet<Integer> tailSet = new TreeSet<>(numbers.tailSet(5));
    System.out.println(tailSet); // Output: [5, 7, 9]
  }
}

En el código anterior, creamos un TreeSet llamado números y agregamos algunos elementos. Luego demostramos búsquedas basadas en rangos utilizando los métodos subSet() , headSet() y tailSet() .

• El subconjunto TreeSet contiene elementos entre 3 (inclusive) y 8 (exclusivo), que son [3, 5, 7] .
• El headSet TreeSet contiene elementos menores de 6, que son [1, 3, 5] .
• El tailSet TreeSet contiene elementos mayores o iguales a 5, que son [5, 7, 9] .

Estos métodos de búsqueda basados ​​en rangos nos permiten recuperar subconjuntos de elementos según criterios específicos, lo que brinda flexibilidad al trabajar con datos ordenados.

Comparador en TreeSet: clasificación con criterios personalizados

Excepto por el orden natural, puede utilizar un Comparador personalizado para ordenar TreeSet . En esta sección profundizaremos en el concepto de comparador y su papel en TreeSet . Exploraremos cómo crear un TreeSet con un comparador personalizado y proporcionaremos ejemplos de código para demostrar la clasificación de TreeSet según criterios específicos.

¿Qué es el comparador?

Un Comparador es una interfaz en Java que permite la clasificación personalizada de objetos. Proporciona una forma de definir el orden de los elementos en función de atributos o propiedades específicas. Al implementar la interfaz Comparator y anular su método compare() , podemos especificar cómo se deben ordenar los elementos en un TreeSet .

Creando TreeSet con un comparador personalizado

Para crear un TreeSet con un comparador personalizado, debemos proporcionar el comparador como argumento al crear la instancia de TreeSet . Veamos un ejemplo:

import java.util.Comparator;
import java.util.TreeSet;

public class TreeSetComparatorExample {
  public static void main(String[] args) {
    // Create a TreeSet with a custom comparator
    TreeSet<String> names = new TreeSet<>(new LengthComparator());

    // Add elements to the TreeSet
    names.add("Johnny");
    names.add("Ivy");
    names.add("Rick");
    names.add("David");

    System.out.println(names); // Output: [Ivy, Johnny, David, Rick]
  }
}

class LengthComparator implements Comparator<String> {
  @Override
  public int compare(String s1, String s2) {
    return Integer.compare(s1.length(), s2.length());
  }
}

En el código anterior, creamos un TreeSet llamado nombres con un comparador personalizado llamado LongitudComparator . LongitudComparator compara la longitud de dos cadenas y las clasifica en consecuencia. Como resultado, TreeSet se ordena según la longitud de las cadenas, lo que nos da el resultado [Ivy, Rick, David, Johnny] .

Ejemplos de clasificación de TreeSet utilizando un comparador

Además de crear un TreeSet con un comparador personalizado, también podemos usar un comparador para ordenar un TreeSet temporalmente sin modificar su orden natural. Veamos un ejemplo:

import java.util.Comparator;
import java.util.TreeSet;

  public class TreeSetTest {
    public static void main(String[] args) {
      TreeSet<String> names = new TreeSet<>();

      names.add("Johnny");
      names.add("Ivy");
      names.add("Ricky");
      names.add("David");

      // Sort TreeSet temporarily using a comparator
      TreeSet<String> sortedNames = new TreeSet<>(Comparator.reverseOrder());
      sortedNames.addAll(names);

      System.out.println(sortedNames); // Output: [Ricky, Johnny, Ivy, David]
      System.out.println(names); // Output: [David, Ivy, Johnny, Ricky]
    }
  }

En el código anterior, creamos un TreeSet llamado nombres y agregamos algunos elementos. Luego creamos un nuevo TreeSet llamado sortedNames con un comparador personalizado Comparator.reverseOrder() . Al agregar todos los elementos de los nombres originales TreeSet a sortedNames , obtenemos una versión ordenada temporal de TreeSet .

Comparando TreeSet con otras estructuras de datos

Comparando TreeSet con HashSet

Tanto TreeSet como HashSet son implementaciones de la interfaz Set en Java. Sin embargo, existen diferencias significativas entre ellos. TreeSet : TreeSet almacena elementos únicos en orden. Utiliza un árbol de búsqueda binario autoequilibrado (normalmente un árbol rojo-negro) para mantener el orden, lo que da como resultado una complejidad de tiempo logarítmica para operaciones como inserción, eliminación y búsqueda. TreeSet es eficaz para mantener una colección ordenada y realizar operaciones basadas en rangos. Sin embargo, tiene una mayor sobrecarga de memoria debido a la estructura de árbol y no permite elementos nulos. HashSet : HashSet almacena elementos únicos de manera desordenada utilizando códigos hash y tablas hash internamente. Proporciona una complejidad de tiempo constante para operaciones básicas como inserción, eliminación y búsqueda. HashSet es eficiente para la búsqueda rápida de elementos y no impone ninguna sobrecarga de memoria adicional para mantener el orden. Sin embargo, no garantiza ningún orden específico de elementos.

Cuándo utilizar TreeSet:

• Cuando necesita mantener elementos ordenados automáticamente.
• Cuando necesita operaciones basadas en rangos o necesita encontrar elementos dentro de un rango específico de manera eficiente.
• Cuando no se permiten elementos duplicados y la unicidad es fundamental.
• Cuando esté dispuesto a intercambiar un uso de memoria ligeramente mayor por los beneficios de las operaciones de clasificación y rango automático.

Comparando TreeSet con ArrayList

ArrayList es una implementación de matriz dinámica en Java. Estas son las diferencias clave entre TreeSet y ArrayList :

• TreeSet : TreeSet almacena elementos únicos en orden, proporcionando operaciones eficientes para mantener una colección ordenada y realizar búsquedas basadas en rangos. Tiene complejidad de tiempo logarítmica para las operaciones. TreeSet no es adecuado para acceso aleatorio ni para mantener el orden de inserción.
• ArrayList : ArrayList almacena elementos en el orden de inserción, proporcionando un acceso aleatorio rápido a los elementos mediante índices. Tiene una complejidad de tiempo constante para la mayoría de las operaciones al acceder a elementos por índice. Sin embargo, tiene una complejidad de tiempo lineal para insertar o eliminar elementos del medio de la lista, ya que requiere cambiar elementos.

Cuándo considerar otras estructuras de datos

• Si no es necesario mantener los elementos en un orden ordenado y necesita una búsqueda rápida de elementos o una colección desordenada, HashSet podría ser una mejor opción.
• Si necesita acceso aleatorio frecuente a elementos por índice o necesita mantener el orden de inserción, ArrayList sería más adecuado.