TreeSet

Kurz: Eine Set-Implementierung, die ihre Elemente automatisch sortiert hält — intern über einen balancierten Binärbaum (Red-Black-Tree).

Genauer: Die Sortierung erfolgt entweder über die natürliche Ordnung (das Element muss Comparable implementieren) oder über einen beim Erzeugen übergebenen Comparator. Einfügen/Entfernen/Suchen ist bei TreeSet mit logarithmischer statt konstanter Zeit etwas langsamer als bei HashSet, dafür ist die Reihenfolge immer garantiert vorhersehbar.

Im Detail

// Natürliche Ordnung (String implementiert Comparable bereits selbst):
TreeSet<String> namen = new TreeSet<>();
namen.add("Bob");
namen.add("Anna");
namen.add("Carl");
System.out.println(namen); // [Anna, Bob, Carl] - immer sortiert
 
// Eigene Ordnung per Comparator, z.B. absteigend:
TreeSet<Integer> zahlen = new TreeSet<>(Comparator.reverseOrder());
zahlen.add(5);
zahlen.add(1);
zahlen.add(3);
System.out.println(zahlen); // [5, 3, 1]
 
System.out.println(namen.first()); // "Anna" - kleinstes Element
System.out.println(namen.last());  // "Carl" - größtes Element

Intern verwaltet TreeSet seine Elemente in einem Rot-Schwarz-Baum (eine selbstbalancierende Variante eines Binärbaums), der garantiert, dass Einfügen, Löschen und Suchen immer in logarithmischer Zeit (O(log n)) ablaufen, egal in welcher Reihenfolge Elemente eingefügt wurden. Der Baum bleibt dabei automatisch balanciert, statt bei bestimmten Einfügereihenfolgen zu einer entarteten, listenähnlichen Struktur zu degenerieren.

Objekte, die in einem TreeSet landen sollen, müssen entweder selbst Comparable<T> implementieren (definiert eine “natürliche” Standardordnung, wie bei String oder Integer schon vorgegeben) oder es muss beim Erzeugen ein Comparator übergeben werden — ohne eines von beidem wirft TreeSet beim ersten Einfügeversuch eine ClassCastException, weil er keine Möglichkeit hat, zwei Elemente zu vergleichen. Zusätzlich zu den normalen Set-Operationen bietet TreeSet dank der garantierten Sortierung praktische Zusatzmethoden wie first(), last(), headSet(x) (alle Elemente kleiner als x) und higher(x) (nächstgrößeres Element nach x).

Siehe auch: HashSet, Set, Sorting