🌳 Binärer Suchbaum — Einfügen, Suchen & Balancieren

Der Balance-Faktor (bf) eines Knotens ist definiert als die Höhe seines linken Teilbaums minus die Höhe seines rechten Teilbaums. In einem AVL-Baum muss bf bei jedem Knoten −1, 0 oder +1 sein. Der Simulator zeigt „bf:x“ unter jedem Knoten an. Ein Knoten mit bf = +2 hat eine linkslastige Unwucht und benötigt eine Rechtsrotation (oder eine Links-Rechts-Doppelrotation, wenn das Kind rechtslastig ist).

Werden Elemente in streng aufsteigender oder absteigender Reihenfolge eingefügt — etwa 1, 2, 3, 4, 5 — wird der BST zu einer rechten (oder linken) Kette mit Höhe n−1, strukturell identisch mit einer verketteten Liste. Jede Suche erfordert dann das Besuchen aller n Knoten, was O(n) Zeit ergibt. Versuche, sortierte Werte in diesem Simulator einzufügen, und vergleiche die Höhe mit einer zufällig geordneten Einfügung derselben Werte.

Das Löschen eines Knotens in einem BST hat drei Fälle: (1) der Knoten ist ein Blatt — einfach entfernen; (2) der Knoten hat ein Kind — das Kind an seine Stelle setzen; (3) der Knoten hat zwei Kinder — den Wert des Knotens durch den kleinsten Wert in seinem rechten Teilbaum ersetzen (den Inorder-Nachfolger), dann diesen Nachfolgerknoten löschen, der garantiert in Fall 1 oder 2 fällt. Dieser Simulator implementiert alle drei Fälle.

Datenbankmanagementsysteme verwenden B-Bäume (eine Verallgemeinerung von BSTs mit mehreren Schlüsseln pro Knoten) für ihre plattenbasierten Indizes und ermöglichen so O(log n)-Zeilensuchen über Millionen von Datensätzen. Der Linux-Kernel nutzt Rot-Schwarz-Bäume (eine weitere selbstbalancierende BST-Variante) zur Aufgabenplanung und Verwaltung virtueller Speicherbereiche. C++s std::map und std::set werden typischerweise als Rot-Schwarz-Bäume implementiert und garantieren O(log n)-Worst-Case-Operationen.

Beide sind baumbasierte Datenstrukturen, aber mit unterschiedlichen Ordnungseigenschaften. Ein BST erzwingt die Ordnung „linkes Kind kleiner als Elternteil“ im gesamten Baum, was die Suche effizient macht. Ein Heap erzwingt die Heap-Eigenschaft nur zwischen einem Elternteil und seinen unmittelbaren Kindern (Max-Heap: Elternteil ≥ Kinder), was das Finden des Minimums oder Maximums zu O(1) macht, aber beliebige Suche zu O(n). Heaps sind optimal für Prioritätswarteschlangen; BSTs sind optimal für sortierte Wörterbücher.

Für einen perfekt balancierten BST mit n Knoten gilt Höhe h = ⌊log₂ n⌋. Ein AVL-Baum garantiert eine Höhe von höchstens 1,44 × log₂(n+2), was immer noch O(log n) ist. Ein Rot-Schwarz-Baum garantiert eine Höhe von höchstens 2 × log₂(n+1). Diese Schranken sorgen dafür, dass alle Operationen selbst bei ungünstigsten Einfügereihenfolgen O(log n) bleiben.

Standard-BST-Definitionen schließen Duplikate aus, aber reale Implementierungen behandeln sie auf eine von drei Arten: (1) Duplikate ignorieren (wie in diesem Simulator); (2) Duplikate im rechten Teilbaum zulassen (Wert ≤ Elternteil geht nach rechts); (3) einen Zähler zusammen mit jedem Knotenwert speichern. Die Wahl beeinflusst die Löschlogik und die Durchlauf-Semantik und wird daher meist beim Entwurf festgelegt, passend zu den Anforderungen der Anwendung.