EMZETT.TreeSet (Sortierte Menge)
Kurz: Eine Menge, die ihre Elemente automatisch in sortierter Reihenfolge hält — jedes Einfügen platziert das neue Element sofort an der richtigen Stelle.
Genauer: Intern meist als balancierter Suchbaum implementiert, wodurch Einfügen, Suchen und Entfernen deutlich schneller bleiben als bei einer sortierten Liste, aber etwas langsamer als bei einem unsortierten HashSet. Die passende Wahl, wenn die Elemente beim Durchlaufen immer in aufsteigender (oder definierter) Reihenfolge gebraucht werden.
Im Detail
menge = neue SortierteMenge()
menge.hinzufuegen(5)
menge.hinzufuegen(1)
menge.hinzufuegen(3)
fuer wert in menge:
drucke(wert) # gibt 1, 3, 5 aus - automatisch sortiert, egal in welcher
# Reihenfolge eingefügt wurdeDer Grund, warum eine sortierte Menge trotz automatischer Sortierung effizient bleibt, liegt in der internen Struktur: Ein balancierter Suchbaum (z. B. ein Rot-Schwarz-Baum) hält seine Elemente so an, dass jeder Knoten höchstens doppelt so “tief” verschachtelt ist wie jeder andere — dadurch bleiben Einfügen, Suchen und Entfernen bei O(log n) statt der O(n) einer sortierten Liste, bei der jedes Einfügen im Zweifel alle nachfolgenden Elemente verschieben müsste.
Eine sortierte Menge eignet sich besonders für Fälle, in denen man regelmäßig Bereichsabfragen braucht (“alle Werte zwischen 10 und 50”) oder immer das kleinste/größte Element schnell finden will — beides ist bei einer unsortierten HashSet entweder gar nicht oder nur mit einem vollständigen Durchlauf aller Elemente möglich, während der sortierte Baum diese Fragen dank seiner Struktur viel gezielter beantworten kann.
Der Kompromiss gegenüber HashSet: Reines Einfügen/Suchen/Entfernen (ohne Sortierungsbedarf) ist bei einem HashSet im Durchschnitt noch etwas schneller (O(1) statt O(log n)) — eine sortierte Menge lohnt sich also nur, wenn die Sortierreihenfolge tatsächlich gebraucht wird, nicht standardmäßig als Ersatz für ein einfaches HashSet.