Interaktive Mathe- und Wissenschafts-Lektionen

BST-/AVL-Baum-Visualizer

Füge Werte ein und beobachte, wie der Baum wächst. Wechsle in den AVL-Modus, um automatisches Ausbalancieren zu sehen.

Interaktive Simulation wird geladen...

Sortierte Eingabe ist die schlechteste Eingabe 🖖

Ein binärer Suchbaum bezieht seine Geschwindigkeit aus seiner Form, und die Form entsteht ausschließlich aus der Einfügereihenfolge. Gibt man diesem Werkzeug 10, 20, 30, 40, 50, 60, 70 in dieser Reihenfolge, ist jeder Schlüssel größer als der vorige und hängt daher rechts an seinem Vorgänger: der Baum wird eine gerade Kette der Höhe 7. Das ist eine verkettete Liste mit dem Zusatzaufwand von Baumzeigern, und die 70 zu finden kostet sieben Vergleiche statt drei. An den Daten war nichts pathologisch — sie waren lediglich schon sortiert, und so treffen Daten meistens ein. Schaltet man dieselben sieben Werte in den AVL-Modus, drücken Rotationen die Höhe zurück auf 3. Das ist das gesamte Argument für selbstbalancierende Bäume.

Jeder Schritt verwirft die Hälfte 🖖

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.

Der Goldene Schnitt steckt in AVL-Bäumen 🖖

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.

BST- UND AVL-BÄUME — DIESELBEN WERTE, VIER VERSCHIEDENE BÄUME

Welchen Baum ergibt deine Einfügereihenfolge?

Die Form eines binären Suchbaums entscheidet sich nicht daran, welche Werte er enthält, sondern in welcher Reihenfolge sie eingetroffen sind — und diese Form ist der gesamte Preis: Jede Suche, jedes Einfügen und jedes Löschen läuft von der Wurzel bis zu einem Blatt, also kostet die Höhe. Zwei Fragen klären, in welchem Fall du bist: Kamen die Werte schon sortiert an, und dreht etwas sie wieder ins Gleichgewicht?

Ausgeglichener BST — die Reihenfolge griff ineinander h = 3 = ⌈log₂(n + 1)⌉
Entarteter BST — sortierte Eingabe, nichts gleicht aus h = n = 7 ⇒ O(n)
AVL-Ausgleich — die Rotation ist lokal und billig |hL − hR| > 1 → ↻, h = 3
AVL mit sortierter Eingabe — der Fall, für den Rotationen da sind ↻ × 4 ⇒ h = 3 < 7

01

Ausgeglichener BST — die Reihenfolge griff ineinander

Was du weißt: Reiner BST-Modus, keine Rotationen. Die Werte kommen von der Mitte her: Jeder neue Schlüssel fällt in einen noch flachen Teilbaum, und keine Seite läuft der anderen voraus.

Was es kostet: h = 3 = ⌈log₂(n + 1)⌉

Rechenbeispiel: 50, 30, 70, 20, 40, 60, 80 → Wurzel 50, 7 Knoten, Höhe 3 — genau das Ideal ⌈log₂(7+1)⌉ = 3, die tiefste Suche kostet also 3 Vergleiche

Diesen Fall öffnen: Ausgeglichen
Ausgeglichener BST — die Reihenfolge griff ineinander. Sieben Knoten auf drei Ebenen: jedes Blatt gleich weit von der Wurzel — besser geht es nicht. Reiner BST-Modus, keine Rotationen. Die Werte kommen von der Mitte her: Jeder neue Schlüssel fällt in einen noch flachen Teilbaum, und keine Seite läuft der anderen voraus.
Sieben Knoten auf drei Ebenen: jedes Blatt gleich weit von der Wurzel — besser geht es nicht.

02

Entarteter BST — sortierte Eingabe, nichts gleicht aus

Was du weißt: Wieder reiner BST-Modus, aber die Werte kommen aufsteigend an. Jeder ist größer als alles Gespeicherte und geht deshalb nach rechts — jedes Mal.

Was es kostet: h = n = 7 ⇒ O(n)

Rechenbeispiel: 10, 20, 30, 40, 50, 60, 70 → Wurzel 10, 7 Knoten, Höhe 7 statt 3; 70 zu finden kostet 7 Vergleiche, und das Werkzeug nennt das Ergebnis eine verkettete Liste

Diesen Fall öffnen: Entartet
Entarteter BST — sortierte Eingabe, nichts gleicht aus. Jeder Knoten hat ein Kind: Eine Suche läuft alle sieben Ebenen ab, nicht schneller als ein Array-Durchlauf. Wieder reiner BST-Modus, aber die Werte kommen aufsteigend an. Jeder ist größer als alles Gespeicherte und geht deshalb nach rechts — jedes Mal.
Jeder Knoten hat ein Kind: Eine Suche läuft alle sieben Ebenen ab, nicht schneller als ein Array-Durchlauf.

03

AVL-Ausgleich — die Rotation ist lokal und billig

Was du weißt: AVL-Modus. Nach jedem Einfügen läuft der Baum zur Wurzel zurück, und der erste Knoten, dessen Teilbaumhöhen sich um mehr als 1 unterscheiden, wird rotiert. Die Abzeichen neben den Knoten zeigen linke Höhe minus rechte Höhe.

Was es kostet: |hL − hR| > 1 → ↻, h = 3

Rechenbeispiel: 30, 20, 10, 25, 35, 40 im AVL-Modus → das Einfügen von 10 kippt Knoten 30 auf +2, und eine Rechtsrotation hebt 20 an seine Stelle; das später eingefügte 40 kippt einen Knoten auf −2, eine Linksrotation richtet es. 2 Rotationen, 6 Knoten, Höhe 3.

Diesen Fall öffnen: AVL-Ausgleich
AVL-Ausgleich — die Rotation ist lokal und billig. Die umringten Knoten wurden von einer Rotation angehoben; jedes Abzeichen liegt wieder in ±1. AVL-Modus. Nach jedem Einfügen läuft der Baum zur Wurzel zurück, und der erste Knoten, dessen Teilbaumhöhen sich um mehr als 1 unterscheiden, wird rotiert. Die Abzeichen neben den Knoten zeigen linke Höhe minus rechte Höhe.
Die umringten Knoten wurden von einer Rotation angehoben; jedes Abzeichen liegt wieder in ±1.

04

AVL mit sortierter Eingabe — der Fall, für den Rotationen da sind

Was du weißt: AVL-Modus, gefüttert mit genau den Werten, die zwei Fälle weiter oben die Kette ergaben. Jedes Einfügen landet am rechten Ende und drückt die Balance eines Vorfahren auf −2, also löst fast jedes Einfügen eine Korrektur aus.

Was es kostet: ↻ × 4 ⇒ h = 3 < 7

Rechenbeispiel: 10, 20, 30, 40, 50, 60, 70 im AVL-Modus → 4 Linksrotationen, und als Wurzel steht am Ende 40 statt 10. Höhe 3, nicht 7 — dieselbe Eingabe, dieselben sieben Knoten, weniger als die halbe Tiefe.

Diesen Fall öffnen: Sortiert in AVL
AVL mit sortierter Eingabe — der Fall, für den Rotationen da sind. Dieselben sortierten Werte wie in Fall 2, beim Ankommen auf drei Ebenen zurückgedreht. AVL-Modus, gefüttert mit genau den Werten, die zwei Fälle weiter oben die Kette ergaben. Jedes Einfügen landet am rechten Ende und drückt die Balance eines Vorfahren auf −2, also löst fast jedes Einfügen eine Korrektur aus.
Dieselben sortierten Werte wie in Fall 2, beim Ankommen auf drei Ebenen zurückgedreht.
Quellen (1)
  • Insight block 3 — the Fibonacci tree that sets the AVL height bound: D. E. Knuth, The Art of Computer Programming, Volume 3: Sorting and Searching, 2nd edition, §6.2.3. Addison-Wesley, 1998. ISBN 978-0-201-89685-5 — the sparsest legal AVL tree of each height, and the logφ bound that follows.

Aufgabe vollständig gelöst

  1. Ein Baum der Höhe sieben mit sieben Knoten 5 Schritte

    Sieben Knoten und ein Baum der Höhe sieben. Ein balancierter Baum hätte die Höhe 3. Ermitteln Sie, was die Eingabe bewirkt hat — und was das im großen Maßstab kostet.

    1. Die Standard-Schlüssel lauten 10, 20, 30, … — bereits sortiert. Folgt man der Einfügeregel, ist jeder neue Schlüssel größer als alles bisher im Baum Befindliche, sodass er jedes Mal nach rechts wandert.

    2. Das Ergebnis weist keinerlei Verzweigung auf. Jeder Knoten hat genau ein Kind, sodass die Struktur einer verketteten Liste entspricht, die zufällig als Baum gezeichnet ist, und die Höhe entspricht der Knotenanzahl.

    3. Die bestmögliche Höhe für sieben Knoten ist 3, da ein Baum der Höhe h höchstens 2ʰ − 1 Knoten enthält und 2³ − 1 = 7 genau aufgeht. Diese Eingabe erreicht den schlechtesten Fall, obwohl die balancierte Variante möglich gewesen wäre.

    4. Die Suche verläuft von der Wurzel aus, sodass die Kosten der Höhe entsprechen: hier 7 Vergleiche gegenüber 3.

    5. Das Verhältnis ist der eigentliche Punkt, und es wächst. Bei einer Million Knoten beträgt die balancierte Höhe 20, während die Höhe bei sortierter Eingabe eine Million beträgt.

    Antwort

    Das Werkzeug gibt eine Höhe von 7 für 7 Knoten aus, verglichen mit einem Ideal von 3. Die Lehre daraus ist, dass O(log n) nie eine Eigenschaft des binären Suchbaums war — es ist eine Eigenschaft der Einfügereihenfolge, und die natürlichste Reihenfolge, die ein Programmierer ihm jemals übergeben wird, nämlich sortierte Daten, ist genau diejenige, die ihn zerstört. Das ist der eigentliche Grund, warum AVL- und Rot-Schwarz-Bäume existieren: Sie kosten ein oder zwei Rotationen pro Einfügung, um die Garantie bedingungslos zu machen. Schalten Sie den Modus auf AVL um und beobachten Sie, wie sich dieselben sieben Schlüssel bei einer Höhe von 3 einpendeln.

· Aktualisiert

Anhand veröffentlichter Quellen geprüft. Korrekturen willkommen. Redaktionsrichtlinie · Korrekturen

Alle Lektionen: Informatik →

Beispielaufgaben

  • Ausgeglichen - Ausgeglichener BST: 7 Knoten, Höhe 3
  • Entartet - Sortierte Eingabe: BST streckt sich auf Höhe 7
  • AVL-Ausgleich - AVL gleicht sich mit 2 Rotationen aus
  • Sortiert in AVL - Dieselben sortierten Werte in AVL: Höhe 3 nach 4 Rotationen