BST-/AVL-Baum-Visualizer

Binäre Suchbäume erfordern eine strikte hierarchische Organisation und stellen sicher, dass die linken untergeordneten Knoten geringere Werte enthalten. AVL-Bäume verbessern dies, indem sie algorithmisch einen maximalen Höhenunterschied von eins zwischen Teilbäumen erzwingen. Dieser mathematische Selbstausgleich erfordert präzise Rotationstransformationen beim Einfügen oder Löschen. Solche strukturellen Einschränkungen stellen sicher, dass Such-, Einfügungs- und Löschvorgänge durch die zeitliche Komplexität von O(log n) begrenzt bleiben, wodurch ein schneller Datenabruf optimiert wird.

Ein binärer Suchbaum funktioniert wie das Nachschlagen eines Wortes im Wörterbuch: An jedem Knoten vergleichst du und verwirfst sofort die ganze Hälfte, die deinen Wert nicht enthalten kann. Deshalb findet ein gut geformter Baum unter einer Million Einträgen jeden Wert in etwa 20 Vergleichen. Doch die Form hängt ganz von der Einfügereihenfolge ab — gib die Werte einmal bereits sortiert ein (10, 20, 30, …) und sieh zu, wie der Baum zu einer einzigen schiefen Linie zusammenfällt, nicht schneller als das Durchsuchen einer Liste.

Wechsle in den AVL-Modus und frage: Wie hoch darf ein balancierter Baum bei gegebener Knotenzahl höchstens werden? Die Antwort verbirgt den Goldenen Schnitt. Der dünnste zulässige AVL-Baum jeder Höhe ist ein Fibonacci-Baum, zusammengesetzt aus zwei kleineren Fibonacci-Bäumen, sodass seine Knotenzahlen der Fibonacci-Folge folgen. Deshalb trägt die Höhenschranke die Konstante 1.44 — sie ist genau 1 / log₂(φ), mit φ ≈ 1.618, dem Goldenen Schnitt.