Java TreeSet

TreeSet<E> ist die Set-Implementierung, die ihre Elemente sortiert hält. Sie basiert auf einem Rot-Schwarz-Baum (demselben ausgeglichenen binären Suchbaum, der intern auch TreeMap antreibt), sodass jede Operation — add, remove, contains, first, last, Bereichsabfragen — O(log n) ist. Das ist langsamer als O(1) bei HashSet, aber du erhältst etwas, das HashSet überhaupt nicht liefern kann: einen sortierten Iterator, das kleinste Element auf Abruf und die Möglichkeit zu fragen „alle Tags zwischen a und m."

TreeSet implementiert das reichhaltigere NavigableSet<E>-Interface (das SortedSet<E> erweitert), sodass alle Bereichs- und Nachbarabfragen direkt auf der Klasse verfügbar sind und nicht in Collections-Hilfsmethoden versteckt sind. Falls du den Basisvertrag noch nicht kennst, lies zuerst das Kapitel über das Set-Interface — alles dort (keine Duplikate, add gibt false bei Wiederholung zurück) gilt weiterhin.

Zwei Wege, die Reihenfolge zu definieren

Ein TreeSet benötigt eine Möglichkeit, Elemente zu vergleichen. Es gibt zwei:

1. Natürliche Reihenfolge — der Elementtyp implementiert Comparable<E>. String, Integer, LocalDate, jeder Wrapper, jedes Enum, jeder record, den du schreibst und der Comparable implementiert. Der No-Arg-Konstruktor new TreeSet<>() verwendet dies.
2. Ein Comparator<E>, den du angibst — übergib ihn an den Konstruktor. Das Set verwendet deinen Comparator für jeden Vergleich.

Set<String> caseInsensitive = new TreeSet<>(String.CASE_INSENSITIVE_ORDER);
caseInsensitive.add("Banana");
caseInsensitive.add("apple");
caseInsensitive.add("BANANA");   // equals "Banana" by this comparator → not added
System.out.println(caseInsensitive); // [apple, Banana]

Das zweite Beispiel ist wichtig. TreeSet entscheidet „gleich" anhand von compareTo, das 0 zurückgibt, nicht anhand von equals. Zwei Strings, die die natürliche Reihenfolge als unterschiedlich einstuft, ein Comparator aber als gleich, werden zu einem einzigen Element zusammengeführt. Das ist fast immer das, was man möchte — aber es ist eine scharfe Kante, wenn man es nicht weiß.

Die NavigableSet-API

Ein TreeSet bietet Operationen, die ein einfaches Set nicht kann:

TreeSet<Integer> t = new TreeSet<>(List.of(10, 20, 30, 40, 50));
t.first();          // 10  — smallest
t.last();           // 50  — largest
t.lower(30);        // 20  — strictly less than 30
t.floor(30);        // 30  — ≤ 30
t.higher(30);       // 40  — strictly greater than 30
t.ceiling(30);      // 30  — ≥ 30
t.pollFirst();      // 10, removes
t.pollLast();       // 50, removes
t.headSet(30);      // {10, 20}        — strictly less than 30
t.tailSet(30);      // {30, 40, 50}    — ≥ 30
t.subSet(20, 40);   // {20, 30}        — [20, 40)
t.descendingSet();  // a reverse-order view

Das sind die Operationen, die den O(log n)-Aufwand rechtfertigen: Ein HashSet kann keine davon ausführen, ohne zuerst das gesamte Set zu sortieren. Wenn du eine davon benötigst, ist TreeSet die richtige Wahl.

Keine Nulls

Ein TreeSet kann kein null halten, da es null mit den anderen Elementen vergleichen müsste und compareTo(null) eine NullPointerException auslöst. Das Set wirft beim ersten Einfügeversuch. Wenn du einen Platzhalter benötigst, verwende einen anderen Wert des Elementtyps — Integer.MIN_VALUE, einen leeren String oder einen dedizierten Marker in einem Enum.

Elemente zu mutieren ist verboten (dieselbe Falle wie bei HashSet)

TreeSet bestimmt die Baumposition bei der Einfügung, indem es compareTo (oder deinen Comparator) aufruft. Wenn du ein Element nach der Einfügung so mutierst, dass sich die Reihenfolge ändert, werden die Invarianten des Baums verletzt: contains durchsucht den falschen Teilbaum, remove kann lautlos fehlschlagen, und die Iteration kann dasselbe Element zweimal zurückgeben oder Elemente überspringen.

Die Regel, nochmals formuliert: Füge effektiv unveränderliche Elemente in ein TreeSet ein. Oder falls sich dein Element ändert, entferne es vor der Änderung und füge es danach wieder ein.

Wann TreeSet gewählt werden sollte

Entscheidungsfluss:

• Du benötigst sortierte Iteration oder Bereichsabfragen → TreeSet. Die einzige Wahl.
• Du benötigst schnelle Zugehörigkeitsprüfung und die Reihenfolge spielt keine Rolle → HashSet. O(1) gewinnt.
• Du benötigst schnelle Zugehörigkeitsprüfung und vorhersehbare Iterationsreihenfolge → LinkedHashSet. Einfügereihenfolge, nicht sortiert.
• Der Elementtyp ist ein Enum → EnumSet. Schneller als TreeSet und von Natur aus geordnet.

Ein nützliches Muster: Führe eine aufwändige HashSet-basierte Berechnung durch, wenn Geschwindigkeit wichtig ist, und dann einmalig new TreeSet<>(hashSet) am Ende, wenn du das Ergebnis geordnet präsentieren möchtest. Schnell bauen, sortiert präsentieren.

Ein ausgearbeitetes Beispiel: Bestenliste, Comparator und Bereichsabfragen

Das folgende Programm verwendet TreeSet, um eine nach Punktzahl sortierte Bestenliste (mit einem benutzerdefinierten Comparator) zu führen, demonstriert die Navigationsmethoden und zeigt, wie sich compareTo-basierte Gleichheit von equals-basierter Gleichheit unterscheidet.

Was aus der Ausführung zu entnehmen ist:

• Die Integer kamen in aufsteigender Reihenfolge zurück, ohne explizite Sortierung. Diese sortierte Invariante wird bei jedem add beibehalten — der Preis ist O(log n) pro Einfügung.
• Die Bestenliste verwendete einen zweistufigen Comparator: absteigend nach Punktzahl, dann aufsteigend nach Name, damit punktgleiche Spieler unterscheidbar bleiben. Füge immer einen Tie-Breaker ein, wenn Punktzahlen sich wiederholen können, sonst kollabiert TreeSet sie.
• Das case-insensitive Set lehnte "JAVA" ab, weil es laut Comparator gleich "Java" ist — auch wenn "JAVA".equals("Java") false ist. Comparator-Gleichheit, nicht equals-Gleichheit.
• null hat eine Ausnahme ausgelöst — es gibt keine sinnvolle Möglichkeit, es mit anderen Elementen zu vergleichen.

Was kommt als Nächstes

Set ist abgeschlossen; die andere Hälfte des Frameworks ist Map, die Schlüssel-Wert-Abstraktion. Ein Set kann man sich als Map vorstellen, bei der man sich nicht um den Wert kümmert. Das Kapitel über das Map-Interface kommt als Nächstes, und die parallele Struktur mit Set wird offensichtlich sein, sobald wir beginnen. TreeSet wird tatsächlich von einer TreeMap unterstützt, sodass die sortierten Map-Navigationsmethoden, die du hier gesehen hast, dort mit Schlüsseln statt Elementen wieder auftauchen.

Übungen