La classe TreeSet di Set – Lezione 34 di Java Avanzato

TreeSet come un albero di ricerca bilanciato

TreeSet, è un Set implementato interiormente come un albero di ricerca bilanciato. Questa classe estende l’interfaccia SortedSet perché gli elementi vengono inseriti in modo ordinato secondo un ordinamento naturale della classe o non naturale. Di conseguenza gli elementi presenti nel TreeSet devono implementare l’interfaccia Comparable o l’interfaccia Comparator.
Nello specifico gli elementi inseriti in un TreeSet formano un albero rosso/nero e indipendentemente dall’inserimento, l’iterarotre restituisce gli oggetti in modo ordinata.

Graficamente la classe TreeSet è così composta:

La classe TreeSet di Set

In TreeSet abbiamo a disposizione diversi costruttori, tra cui:

  •   public TreeSet()

    Questo costruttore consente di creare un TreeSet vuoto;

  •   public TreeSet(Collection c)

    Consente di creare un TreeSet con gli elementi contenuti nella Collection passata come argomento;

  •   public TreeSet(Comparator c)
    Consente di di assegnare a gli elementi da ordinare una relazione d’ordine non naturale.

Iterando con un iteratore su TreeSet, gli elementi verranno restituiti in maniera ordinata.

Coerenza tra equals e l’ordinamento

L’interfaccia Set utilizza il metodo equals per confrontare gli elementi, mentre TreeSet utilizza un ordinamento, fornito da Comparable o Comparator, per decidere dove inserire gli elementi all’interno dell’albero.
Se l’ordinamento non fosse coerente con l’uguaglianza definita da equals, la struttura dati potrebbe comportarsi in modo imprevedibile. In genere la coerenza tra equals e l’ordinamento è consigliata, ma nel caso di TreeSet è obbligatoria!

Vediamo il caso di Comparable:
Per ogni coppia di elementi x e y, in aggiunta alla normale proprietà di equals e compareTo, deve valere la seguente condizione:

x.equals(y) == true se e solo se x.compareTo(y) == 0

Una condizione analoga vale per Comparator.

Nei TreeSet le funzioni last e first ereditate da SortedSet avvengono in tempo costante, sono presenti all’interno della classe due campi che puntano costantemente all’elemento più piccolo e più grande dell’albero.

Aggiungere un elemento in un TreeSet è una operazione meno efficiente rispetto agli HashSet, ma sicuramente molto più efficiente rispetto una LinkedList che preservi l’ordinamento. Per un TreeSet che contiene n elementi, sono richieste log(n) confronti, rispetto ai agli n confronti di una lista ordinata.

Indice Lezione PrecedenteLezione Successiva

Pubblicato in Collezioni, Guide, Java, Programmazione Taggato con: , , , , ,

Lascia un commento

Il tuo indirizzo email non sarà pubblicato. I campi obbligatori sono contrassegnati *

*