Lektion 2.5

AVL-Bäume: balancierte Suchbäume

45 min Lesezeit
Lesen anpassen

Nach dieser Lektion kannst du

  • Balancefaktoren berechnen und die AVL-Bedingung prüfen,

  • beweisen, dass ein AVL-Baum mit nn Knoten höchstens etwa 1,44log⁡2n1{,}44 \log_2 n hoch ist,

  • Links-, Rechts- und Doppelrotationen ausführen und erklären, warum sie die Suchbaumeigenschaft erhalten,

  • eine Einfügefolge in einen AVL-Baum vollständig durchspielen und jeden Fall erkennen,

  • AVL-Bäume mit Rot-Schwarz-Bäumen und B-Bäumen vergleichen.

Vorausgesetzt: Binäre Suchbäume, Laufzeit messen: Operationen zählen und O-Notation

Ein binärer Suchbaum kostet je Operation O(h)O(h), aber die Höhe hh hängt von der Einfügereihenfolge ab. Fortlaufende Bestellnummern erzeugen eine Kette mit h=n−1h = n - 1, und jede Suche wird linear. Wir brauchen eine Garantie: h∈O(log⁡n)h \in O(\log n), egal in welcher Reihenfolge eingefügt und gelöscht wird.

Der naheliegende Wunsch, den Baum immer so flach wie möglich zu halten, ist zu teuer. Verlangt man etwa, dass alle Ebenen bis auf die letzte voll sind und die letzte von links gefüllt ist, dann ist die Form des Baums durch nn festgelegt. Fehlt unten nur noch der Platz ganz rechts, und kommt ein neuer kleinster Schlüssel hinzu, dann muss der neue Knoten an diesen Platz, der in der Inorder-Folge ganz hinten liegt. Jeder Schlüssel rückt in der sortierten Folge eine Stelle weiter, also bekommt jeder vorhandene Knoten einen anderen Schlüssel: Θ(n)\Theta(n) Arbeit für eine Einfügung.

Adelson-Velski und Landis schlugen 1962 eine schwächere Bedingung vor: An jedem Knoten unterscheiden sich die Höhen des linken und des rechten Teilbaums höchstens um 11. Sie lässt genug Spielraum, um nach jeder Änderung mit wenigen lokalen Umbauten auszukommen, und hält die Höhe trotzdem logarithmisch.

Vermute zuerst

Ein binärer Suchbaum mit 77 Knoten erfüllt an jedem Knoten die Regel „Höhen der beiden Teilbäume unterscheiden sich höchstens um 11“ (ein fehlender Teilbaum hat Höhe −1-1). Wie hoch kann er höchstens sein?

Definition

Balancefaktor, AVL-Baum

Für einen Knoten vv sei hoehe(v)\mathrm{hoehe}(v) die Höhe seines Teilbaums, mit hoehe(NIL)=−1\mathrm{hoehe}(\texttt{NIL}) = -1. Der Balancefaktor von vv ist

bal(v)=hoehe(v.rechts)−hoehe(v.links)\mathrm{bal}(v) = \mathrm{hoehe}(v.\mathrm{rechts}) - \mathrm{hoehe}(v.\mathrm{links}).

Ein AVL-Baum ist ein binärer Suchbaum, in dem für jeden Knoten bal(v)∈{−1,0,1}\mathrm{bal}(v) \in \{-1, 0, 1\} gilt. Ein Knoten mit bal(v)=±2\mathrm{bal}(v) = \pm 2 heißt unausgeglichen. Jeder Knoten speichert seine Höhe, damit Balancefaktoren in O(1)O(1) berechnet werden können. (Manche Bücher nehmen links minus rechts; dann kehren sich alle Vorzeichen um.)

Beispiel

Ein AVL-Baum und ein Gegenbeispiel

Der Baum aus der Vermutung, 50(30(20, 40(35, –)), 70(–, 80)), mit Höhen und Balancefaktoren:

Knotenlinkes Kindrechtes KindHöhebal
5030703−1-1
3020402+1+1
20––000
4035–1−1-1
35––000
70–801+1+1
80––000

Zum Beispiel ist bal(50)=hoehe(70)−hoehe(30)=1−2=−1\mathrm{bal}(50) = \mathrm{hoehe}(70) - \mathrm{hoehe}(30) = 1 - 2 = -1 und bal(40)=−1−0=−1\mathrm{bal}(40) = -1 - 0 = -1. Alle Werte liegen in {−1,0,1}\{-1, 0, 1\}.

Gegenbeispiel: In 50(30(20(10, –), –), 70(–, 80(–, 90))) ist die Wurzel perfekt ausgeglichen, bal(50)=2−2=0\mathrm{bal}(50) = 2 - 2 = 0. Trotzdem ist es kein AVL-Baum: bal(30)=−1−1=−2\mathrm{bal}(30) = -1 - 1 = -2 und bal(70)=1−(−1)=+2\mathrm{bal}(70) = 1 - (-1) = +2. Die Bedingung muss an jedem Knoten gelten, nicht nur an der Wurzel.

Kurz geprüft

Welchen Balancefaktor hat die Wurzel von 8(4(2, 6(5, 7)), 10)?

Satz

AVL-Bäume haben logarithmische Höhe

Sei N(h)N(h) die kleinste Knotenzahl eines AVL-Baums der Höhe hh. Dann gilt N(0)=1N(0) = 1, N(1)=2N(1) = 2 und für h≥2h \ge 2

N(h)=N(h−1)+N(h−2)+1N(h) = N(h-1) + N(h-2) + 1.

hh01234567
N(h)N(h)124712203354

Mit dem goldenen Schnitt φ=1+52≈1,618\varphi = \frac{1 + \sqrt{5}}{2} \approx 1{,}618 ist N(h)≥φhN(h) \ge \varphi^h. Für jeden AVL-Baum mit n≥1n \ge 1 Knoten und Höhe hh folgt

h  ≤  log⁡φn  =  log⁡2nlog⁡2φ  ≈  1,4404⋅log⁡2nh \;\le\; \log_{\varphi} n \;=\; \frac{\log_2 n}{\log_2 \varphi} \;\approx\; 1{,}4404 \cdot \log_2 n
Kurz geprüft

Wie hoch kann ein AVL-Baum mit 1212 Knoten höchstens sein?

Definition

Rotation

Eine Rechtsrotation an einem Knoten yy mit linkem Kind xx hebt xx nach oben. Sind AA, BB und CC Teilbäume (auch leere), so wird

y(x(A, B), C) zu x(A, y(B, C)).

Der mittlere Teilbaum BB wechselt dabei von xx zu yy. Die Linksrotation an xx ist das Spiegelbild: x(A, y(B, C)) wird zu y(x(A, B), C).

ZeileEinrückungAnweisung
10rotiereRechts(y):\texttt{rotiereRechts(y):}
21x = y.links\texttt{x = y.links}
31y.links = x.rechts\texttt{y.links = x.rechts}
41x.rechts = y\texttt{x.rechts = y}
51aktualisiere(y)\texttt{aktualisiere(y)}
61aktualisiere(x)\texttt{aktualisiere(x)}
71return x\texttt{return x}

aktualisiere(v)\texttt{aktualisiere(v)} setzt v.h=1+max⁡(hoehe(v.links),hoehe(v.rechts))v.h = 1 + \max(\mathrm{hoehe}(v.\mathrm{links}), \mathrm{hoehe}(v.\mathrm{rechts})); yy zuerst, weil yy jetzt unter xx hängt. Der Aufrufer schreibt den zurückgegebenen Knoten dorthin, wo vorher yy hing.

Die Suchbaumeigenschaft bleibt erhalten: Vor und nach der Rotation lautet die Inorder-Folge „AA, xx, BB, yy, CC“. Jeder Schlüssel in BB ist größer als xx (er lag rechts von xx) und kleiner als yy (er lag links von yy), steht also auch nach der Rotation auf der richtigen Seite von beiden. Für die Knoten in AA, BB, CC und für alle Vorfahren ändert sich die Menge der Schlüssel unter ihnen nicht. Eine Rotation ändert drei Verweise und zwei Höhen, kostet also O(1)O(1).

Beispiel

Die vier Fälle beim Einfügen

Nach dem Einfügen wie im binären Suchbaum geht man den Weg vom neuen Blatt zurück nach oben, aktualisiert die Höhen und repariert am ersten unausgeglichenen Knoten zz von unten. Wo der neue Knoten unter zz liegt, entscheidet über die Reparatur:

Fallneuer Knoten liegt imerkennbar anReparatur
LLlinken Teilbaum des linken Kindesbal(z)=−2\mathrm{bal}(z) = -2, linkes Kind −1-1Rechtsrotation an zz
RRrechten Teilbaum des rechten Kindesbal(z)=+2\mathrm{bal}(z) = +2, rechtes Kind +1+1Linksrotation an zz
LRrechten Teilbaum des linken Kindesbal(z)=−2\mathrm{bal}(z) = -2, linkes Kind +1+1Linksrotation am linken Kind, dann Rechtsrotation an zz
RLlinken Teilbaum des rechten Kindesbal(z)=+2\mathrm{bal}(z) = +2, rechtes Kind −1-1Rechtsrotation am rechten Kind, dann Linksrotation an zz

LR und RL heißen Doppelrotationen. Als Pseudocode, aufgerufen in Zeile 7 von einfuegen\texttt{einfuegen} (statt return v\texttt{return v} steht dort return ausgleichen(v)\texttt{return ausgleichen(v)}):

ZeileEinrückungAnweisung
10ausgleichen(v):\texttt{ausgleichen(v):}
21aktualisiere(v)\texttt{aktualisiere(v)}
31if bal(v) == -2:\texttt{if bal(v) == -2:}
42if bal(v.links) == 1: v.links = rotiereLinks(v.links)\texttt{if bal(v.links) == 1: v.links = rotiereLinks(v.links)}
52return rotiereRechts(v)\texttt{return rotiereRechts(v)}
61if bal(v) == 2:\texttt{if bal(v) == 2:}
72if bal(v.rechts) == -1: v.rechts = rotiereRechts(v.rechts)\texttt{if bal(v.rechts) == -1: v.rechts = rotiereRechts(v.rechts)}
82return rotiereLinks(v)\texttt{return rotiereLinks(v)}
91return v\texttt{return v}

Weil die Rekursion von unten nach oben zurückkehrt, kommt der tiefste unausgeglichene Knoten zuerst dran.

Beispiel LR: In 30(10(–, 20), –) hat die 3030 den Balancefaktor −2-2 und ihr linkes Kind 1010 den Wert +1+1. Linksrotation an 1010 ergibt 30(20(10, –), –), das ist jetzt ein LL-Fall; die Rechtsrotation an 3030 ergibt 20(10, 30). Der mittlere Schlüssel der drei landet oben.

Satz

Eine Reparatur genügt beim Einfügen

Nach der Rotation (einfach oder doppelt) am tiefsten unausgeglichenen Knoten zz hat der reparierte Teilbaum wieder dieselbe Höhe wie vor dem Einfügen. Deshalb sind danach alle Vorfahren ausgeglichen, und ein Einfügen kostet O(log⁡n)O(\log n) Schritte mit höchstens einer Einfach- oder Doppelrotation.

Beispiel

Eine Einfügefolge vollständig durchgespielt

Wir fügen 10,20,30,25,28,27,5,410, 20, 30, 25, 28, 27, 5, 4 in einen leeren AVL-Baum ein. Die zweite Spalte nennt den tiefsten unausgeglichenen Knoten nach dem Einfügen.

eingefügtunausgeglichenFallReparaturBaum danach
10–––10
20–––10(–, 20)
3010, bal +2+2RRlinks an 1020(10, 30)
25–––20(10, 30(25, –))
2830, bal −2-2LRlinks an 25, rechts an 3020(10, 28(25, 30))
2720, bal +2+2RLrechts an 28, links an 2025(20(10, –), 28(27, 30))
520, bal −2-2LLrechts an 2025(10(5, 20), 28(27, 30))
4–––25(10(5(4, –), 20), 28(27, 30))

Genauer bei der 2828: Sie landet rechts unter der 2525, also 20(10, 30(25(–, 28), –)). Von unten: bal(25)=+1\mathrm{bal}(25) = +1, bal(30)=−1−1=−2\mathrm{bal}(30) = -1 - 1 = -2. Das linke Kind 2525 hat +1+1, also Fall LR. Linksrotation an 2525 ergibt 30(28(25, –), –), Rechtsrotation an 3030 ergibt 28(25, 30). Die Wurzel 2020 hatte vor der Reparatur ebenfalls +2+2, danach +1+1, wie der Satz verspricht.

Der fertige Baum:

Knotenlinkes Kindrechtes KindHöhebal
2510283−1-1
105202−1-1
54–1−1-1
4––000
20––000
282730100
27––000
30––000

Ohne Ausgleich ergäbe dieselbe Folge den Baum 10(5(4, –), 20(–, 30(25(–, 28(27, –)), –))) mit Höhe 55. Der AVL-Baum hat Höhe 33, die kleinstmögliche für 88 Knoten.

Kurz geprüft

In den fertigen Baum 25(10(5(4, –), 20), 28(27, 30)) wird die 33 eingefügt. Was passiert?

Häufige Fehler

Einfachrotation im Zickzack-Fall

In 30(10(–, 20), –) ist die 3030 mit −2-2 unausgeglichen. Eine einfache Rechtsrotation an 3030 scheint naheliegend. Sie ergibt aber 10(–, 30(20, –)): Jetzt ist die 1010 mit bal=+2\mathrm{bal} = +2 unausgeglichen. Der mittlere Teilbaum (hier die 2020) ist von der einen Seite auf die andere gewandert, und die Schieflage hat nur die Richtung gewechselt.

Richtig ist

Vor der Rotation das Vorzeichen des Kindes prüfen. Zeigen zz und sein Kind in verschiedene Richtungen (−2-2 und +1+1 oder +2+2 und −1-1), braucht es die Doppelrotation: erst am Kind, sodass beide in dieselbe Richtung zeigen, dann an zz. Ergebnis hier: 20(10, 30).

Beispiel

Löschen, kurz

Gelöscht wird wie im binären Suchbaum (Blatt, ein Kind oder Nachfolger). Danach ruft man auf dem Rückweg zur Wurzel an jedem Knoten ausgleichen\texttt{ausgleichen} auf, wie beim Einfügen. Ist dort das Kind auf der schwereren Seite ausgeglichen (bal=0\mathrm{bal} = 0), genügt eine Einfachrotation; der Pseudocode oben behandelt das schon richtig.

Beispiel: Aus 25(10(5(4, –), 20), 28(27, 30)) wird die 2020 gelöscht. Dann ist bal(10)=−1−1=−2\mathrm{bal}(10) = -1 - 1 = -2 und bal(5)=−1\mathrm{bal}(5) = -1, also eine Rechtsrotation an 1010: Es entsteht 25(5(4, 10), 28(27, 30)).

Anders als beim Einfügen kann der reparierte Teilbaum danach niedriger sein als vorher (hier von Höhe 22 auf 11). Dann kann weiter oben ein neuer unausgeglichener Knoten entstehen. Im schlechtesten Fall wird auf jeder Ebene rotiert, das sind O(log⁡n)O(\log n) Rotationen; die Laufzeit bleibt O(log⁡n)O(\log n).

Zusammenfassung

  • Im AVL-Baum ist an jedem Knoten bal=hoehe(rechts)−hoehe(links)∈{−1,0,1}\mathrm{bal} = \mathrm{hoehe}(\text{rechts}) - \mathrm{hoehe}(\text{links}) \in \{-1, 0, 1\}.

  • N(h)=N(h−1)+N(h−2)+1≥φhN(h) = N(h-1) + N(h-2) + 1 \ge \varphi^h, also h≤1,4404log⁡2nh \le 1{,}4404 \log_2 n.

  • Eine Rotation ändert drei Verweise und erhält die Inorder-Folge.

  • Repariert wird am tiefsten unausgeglichenen Knoten: LL und RR einfach, LR und RL doppelt.

  • Beim Einfügen genügt eine Reparatur, Kosten O(log⁡n)O(\log n).

  • Beim Löschen kann auf mehreren Ebenen rotiert werden, die Kosten bleiben O(log⁡n)O(\log n).

  • Rot-Schwarz-Bäume rotieren seltener; B-Bäume speichern viele Schlüssel je Knoten.

Übungen

Aufgabe 1Numerisch

Welchen Balancefaktor hat der Knoten 1010 im AVL-Baum 25(10(5(4, –), 20), 28(27, 30))?

Aufgabe 2Multiple Choice

Du fügst 10,30,2010, 30, 20 in einen leeren AVL-Baum ein. Wie wird nach der 2020 repariert?

Aufgabe 3Numerisch

Du fügst 1,2,3,4,5,6,71, 2, 3, 4, 5, 6, 7 aufsteigend in einen leeren AVL-Baum ein. Welcher Schlüssel steht danach in der Wurzel?

Aufgabe 4Numerisch

Wie hoch kann ein AVL-Baum mit 5050 Knoten höchstens sein?

Aufgabe 5Numerisch

Wie viele Knoten hat ein Fibonacci-Baum (ein AVL-Baum mit kleinstmöglicher Knotenzahl) der Höhe 88?

Aufgabe 6Freitext

Im Fall LR ist xx das linke Kind von zz und ww das rechte Kind von xx. Zeige, dass die Doppelrotation ww nach oben bringt, mit xx links und zz rechts darunter, und dass die Suchbaumeigenschaft erhalten bleibt.

Aufgabe 7Freitext

Zeige, dass jeder AVL-Baum der Höhe hh mindestens 2⌊h/2⌋2^{\lfloor h/2 \rfloor} Knoten hat, und folgere daraus ohne den goldenen Schnitt, dass h≤2log⁡2n+1h \le 2 \log_2 n + 1 gilt.