TreeSet in Java

Java fornisce un vasto insieme di strutture dati per lavorare in modo efficiente con le raccolte di elementi. Una di queste strutture dati è TreeSet, un'implementazione di un albero rosso-nero in Java. TreeSet mantiene un ordine ordinato per la memorizzazione di elementi univoci. I principianti potrebbero trovare inizialmente un po' impegnativo l'utilizzo della classe Java TreeSet . In questo articolo, scopriremo come utilizzare TreeSet , spiegandone i concetti fondamentali e fornendo esempi di codice per aiutarti a iniziare a incorporare TreeSet nei tuoi progetti Java.

Struttura TreeSet: albero Rosso-Nero

Come accennato in precedenza, la struttura della classe Java TreeSet è implementata come un albero di ricerca binario autobilanciante noto come albero Rosso-Nero. Spieghiamo di cosa si tratta... Un albero rosso-nero rappresenta una struttura di dati di ricerca binaria bilanciata comunemente utilizzata per archiviare e organizzare dati ordinati. Deriva il suo nome dalle proprietà che ne mantengono l'equilibrio:

• Ogni nodo nell'albero è rosso o nero.
• La radice dell'albero Rosso-Nero è sempre nera.
• Tutti i nodi foglia (nodi NIL o collegamenti nulli) sono neri.
• Se un nodo dell'albero è rosso, i suoi figli sono neri.
• Ogni percorso semplice da un nodo ai suoi nodi discendenti contiene un numero uguale di nodi neri.

Gli alberi rosso-neri mostrano prestazioni efficienti per le operazioni di inserimento, eliminazione e ricerca di elementi garantendo l'equilibrio. Ciò garantisce che l'altezza dell'albero rimanga proporzionale al logaritmo del numero di nodi che contiene, risultando in una complessità temporale logaritmica per le operazioni. Gli alberi rosso-neri trovano ampie applicazioni in vari domini, inclusa l'implementazione di alberi di ricerca bilanciati nei linguaggi di programmazione, nei database (ad esempio, strutture di indici interni) e in altri scenari in cui sono necessarie archiviazione e operazioni efficienti su dati ordinati.

Caratteristiche e punti deboli di TreeSet

TreeSet fornisce diverse funzionalità chiave che lo rendono uno strumento prezioso per gestire raccolte di oggetti in modo ordinato. Vantaggi:

• Manutenzione automatica degli elementi in ordine ordinato. Quando si aggiungono o rimuovono elementi, la struttura ad albero si adatta per mantenerli ordinati. Ciò elimina la necessità di ordinamento manuale e fornisce un accesso efficiente in ordine crescente o decrescente.
• Operazioni di ricerca, inserimento ed eliminazione efficienti. Utilizza una struttura ad albero di ricerca binaria, consentendo queste operazioni con una complessità temporale di O(log N) . Qui N è il numero di elementi.
• TreeSet garantisce l'unicità degli elementi utilizzando il loro ordinamento naturale o un comparatore personalizzato . Ciò è utile quando si lavora con raccolte che richiedono elementi distinti.

Limitazioni:

• Leggermente più lento di HashSet a causa del mantenimento dell'ordine.
• Non consente elementi nulli, poiché si basa sull'ordinamento naturale o su un comparatore personalizzato per il confronto degli elementi.

Java TreeSet: esempio delle operazioni principali

Ora dimostriamo come creare un TreeSet in Java, ottenere la dimensione della raccolta, aggiungere elementi al suo interno, rimuoverli e verificare se un elemento è nel TreeSet . Questi esempi di codice illustrano le operazioni principali quando si lavora con TreeSet : creazione di un'istanza, aggiunta di elementi, rimozione di elementi, verifica della presenza di elementi e ottenimento della dimensione di TreeSet . Creazione di un'istanza TreeSet e aggiunta di elementi:

// 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]

Qui usiamo il metodo add() per aggiungere 4 numeri nel nostro TreeSet . Se creiamo un metodo main ed eseguiamo il programma, l'output sarà in ordine (2, 7, 18, 28). Rimozione di elementi da 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]

Verifica della presenza di un elemento in 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

Ottenere la dimensione di 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

Ordinamento e iterazione in TreeSet

TreeSet in Java fornisce potenti funzionalità per l'ordinamento e l'iterazione su raccolte di elementi. In questa sezione esploreremo varie tecniche per ordinare gli elementi, eseguire iterazioni su TreeSet ed eseguire ricerche basate su intervalli utilizzando i metodi subSet() , headSet() e tailSet() . Per impostazione predefinita, TreeSet mantiene automaticamente gli elementi in ordine. Tuttavia, possiamo personalizzare il comportamento di ordinamento fornendo un comparatore durante la creazione di TreeSet . Vediamo un esempio:

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]
  }
}

Nel codice precedente, creiamo un TreeSet di tipo Integer e forniamo un comparatore personalizzato utilizzando Comparator.reverseOrder() per ordinare gli elementi in ordine decrescente. Il TreeSet risultante conterrà elementi [7, 5, 3, 1] . Esistono diversi modi per scorrere TreeSet . Possiamo utilizzare un iteratore o utilizzare il ciclo for-each avanzato . Vediamo esempi di entrambi gli approcci:

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);
    }
  }
}

Nel codice sopra creiamo un TreeSet chiamato nomi e aggiungiamo alcuni elementi. Dimostreremo quindi due modi di eseguire l'iterazione su TreeSet : utilizzando un iteratore e utilizzando il ciclo for-each migliorato. TreeSet fornisce metodi per eseguire ricerche basate su intervalli, consentendoci di recuperare sottoinsiemi di elementi in base a criteri specifici. I tre metodi principali per le ricerche basate su intervalli sono:

• subSet(E fromElement, E toElement) : Restituisce un sottoinsieme di elementi da fromElement (incluso) a toElement (esclusivo).
• headSet(E toElement) : Restituisce un sottoinsieme di elementi inferiore a toElement .
• tailSet(E fromElement) : Restituisce un sottoinsieme di elementi maggiori o uguali a fromElement .

Vediamo un esempio:

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]
  }
}

Nel codice sopra creiamo un TreeSet chiamato numeri e aggiungiamo alcuni elementi. Successivamente dimostreremo le ricerche basate su intervalli utilizzando i metodi subSet() , headSet() e tailSet() .

• Il sottoinsieme TreeSet contiene elementi compresi tra 3 (incluso) e 8 (esclusivo), che sono [3, 5, 7] .
• headSet TreeSet contiene elementi inferiori a 6, che sono [1, 3, 5 ] .
• Il tailSet TreeSet contiene elementi maggiori o uguali a 5, che sono [5, 7, 9] .

Questi metodi di ricerca basati su intervalli ci consentono di recuperare sottoinsiemi di elementi in base a criteri specifici, fornendo flessibilità nel lavorare con dati ordinati.

Comparatore in TreeSet: ordinamento con criteri personalizzati

Ad eccezione dell'ordinamento naturale, è possibile utilizzare un Comparator personalizzato per l'ordinamento TreeSet . In questa sezione approfondiremo il concetto di comparatore e il suo ruolo in TreeSet . Esploreremo come creare un TreeSet con un comparatore personalizzato e forniremo esempi di codice per dimostrare l'ordinamento di TreeSet in base a criteri specifici.

Cos'è il comparatore?

Un comparatore è un'interfaccia in Java che consente l'ordinamento personalizzato degli oggetti. Fornisce un modo per definire l'ordinamento degli elementi in base a attributi o proprietà specifici. Implementando l' interfaccia Comparator e sovrascrivendo il suo metodo compare() , possiamo specificare come devono essere ordinati gli elementi in un TreeSet .

Creazione di TreeSet con un comparatore personalizzato

Per creare un TreeSet con un comparatore personalizzato, dobbiamo fornire il comparatore come argomento durante la creazione dell'istanza TreeSet . Vediamo un esempio:

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());
  }
}

Nel codice precedente creiamo un TreeSet chiamato nomi con un comparatore personalizzato chiamato LengthComparator . Il LengthComparator confronta la lunghezza di due stringhe e le ordina di conseguenza. Di conseguenza, TreeSet viene ordinato in base alla lunghezza delle stringhe, dandoci l'output [Ivy, Rick, David, Johnny] .

Esempi di ordinamento di TreeSet utilizzando un comparatore

Oltre a creare un TreeSet con un comparatore personalizzato, possiamo anche utilizzare un comparatore per ordinare temporaneamente un TreeSet senza modificarne l'ordinamento naturale. Vediamo un esempio:

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]
    }
  }

Nel codice sopra creiamo un TreeSet chiamato nomi e aggiungiamo alcuni elementi. Creiamo quindi un nuovo TreeSet chiamato sortedNames con un comparatore personalizzato Comparator.reverseOrder() . Aggiungendo tutti gli elementi dai nomi originali TreeSet a sortedNames , otteniamo una versione ordinata temporanea di TreeSet .

Confronto di TreeSet con altre strutture dati

Confronto tra TreeSet e HashSet

Sia TreeSet che HashSet sono implementazioni dell'interfaccia Set in Java. Tuttavia, ci sono differenze significative tra loro. TreeSet : TreeSet memorizza elementi univoci in ordine ordinato. Utilizza un albero di ricerca binario autobilanciante (solitamente un albero rosso-nero) per mantenere l'ordine ordinato, risultando in una complessità temporale logaritmica per operazioni come l'inserimento, l'eliminazione e la ricerca. TreeSet è efficiente per mantenere una raccolta ordinata ed eseguire operazioni basate su intervalli. Tuttavia, ha un sovraccarico di memoria maggiore a causa della struttura ad albero e non consente elementi null. HashSet : HashSet memorizza elementi univoci in modo non ordinato utilizzando codici hash e tabella hash internamente. Fornisce una complessità temporale costante per operazioni di base come l'inserimento, l'eliminazione e la ricerca. HashSet è efficiente per la ricerca rapida degli elementi e non impone alcun sovraccarico di memoria aggiuntivo per il mantenimento dell'ordine. Tuttavia, non garantisce alcun ordinamento specifico degli elementi.

Quando utilizzare TreeSet:

• Quando è necessario mantenere automaticamente gli elementi in un ordine ordinato.
• Quando sono necessarie operazioni basate su intervalli o è necessario trovare in modo efficiente elementi all'interno di un intervallo specifico.
• Quando non sono consentiti elementi duplicati e l'unicità è essenziale.
• Quando si è disposti a sacrificare un utilizzo della memoria leggermente superiore per i vantaggi dell'ordinamento automatico e delle operazioni di intervallo.

Confronto TreeSet con ArrayList

ArrayList è un'implementazione di array dinamico in Java. Ecco le differenze principali tra TreeSet e ArrayList :

• TreeSet : TreeSet memorizza elementi univoci in ordine ordinato, fornendo operazioni efficienti per mantenere una raccolta ordinata ed eseguire ricerche basate su intervalli. Ha una complessità temporale logaritmica per le operazioni. TreeSet non è adatto per l'accesso casuale o per il mantenimento dell'ordine di inserimento.
• ArrayList : ArrayList memorizza gli elementi nell'ordine di inserimento, fornendo un rapido accesso casuale agli elementi utilizzando gli indici. Ha una complessità temporale costante per la maggior parte delle operazioni quando si accede agli elementi tramite indice. Tuttavia, ha una complessità temporale lineare per l'inserimento o la rimozione di elementi dal centro dell'elenco, poiché richiede lo spostamento degli elementi.

Quando considerare altre strutture dati

• Se non è necessario mantenere gli elementi in ordine ordinato ed è necessaria una ricerca rapida degli elementi o una raccolta non ordinata, HashSet potrebbe essere una scelta migliore.
• Se è necessario un accesso casuale frequente agli elementi per indice o è necessario mantenere l'ordine di inserimento, ArrayList sarebbe più adatto.