Ein einfacher BST kann sich in eine verkettete Liste (O(n) Operationen) abbauen, wenn Schlüssel in sortierter Reihenfolge ankommen. Selbstausgleichende BSTs — wie AVL und Rot-Schwarz-Bäume — rotieren automatisch Knoten nach Einfügungen/Löschungen, um die Höhe ~log n zu halten und O(log n) Operationen zu garantieren.
Unbalanced (insert 1,2,3,4): Balanced after rotations:
1 2
\ / \
2 1 3
\ \
3 4
height ~ n (BAD) height ~ log n (GOOD)
| AVL-Baum | Rot-Schwarz-Baum | |
|---|---|---|
| Ausgleichsstrenge | streng (höhenausgewogen) | lockerer |
| Suche | schneller (kürzer) | etwas langsamer |
| Einfügen/Löschen | mehr Rotationen | weniger Rotationen |
| Best für | Lesekräftige Arbeitslasten | Schreibintensive Arbeitslasten |
| Operation | Zeit |
|---|---|
| Suche | O(log n) |
| Einfügen | O(log n) |
| Löschen | O(log n) |
Beiden erhalten das Gleichgewicht durch Rotationen — lokale O(1)-Umstrukturierungen, die die BST-Ordnung bewahren und die Höhe verringern.
Ausgeglichene Bäume unterstützen geordnete Maps und Sets in Standardbibliotheken (z. B. Java TreeMap, C++ std::map verwenden Rot-Schwarz-Bäume), was sortierte Iteration plus garantierte logarithmische Operationen bietet.
Sie sind die Antwort, wenn Sie die Sortierung eines BST und eine harte Leistungsgarantie gegen gegnerische Eingaben benötigen.