AVL-Bäume: balancierte Suchbäume
Lesen anpassen
Nach dieser Lektion kannst du
Balancefaktoren berechnen und die AVL-Bedingung prüfen,
beweisen, dass ein AVL-Baum mit Knoten höchstens etwa 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 , aber die Höhe hängt von der Einfügereihenfolge ab. Fortlaufende Bestellnummern erzeugen eine Kette mit , und jede Suche wird linear. Wir brauchen eine Garantie: , 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 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: 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 . Sie lässt genug Spielraum, um nach jeder Änderung mit wenigen lokalen Umbauten auszukommen, und hält die Höhe trotzdem logarithmisch.
Ein binärer Suchbaum mit Knoten erfüllt an jedem Knoten die Regel „Höhen der beiden Teilbäume unterscheiden sich höchstens um “ (ein fehlender Teilbaum hat Höhe ). Wie hoch kann er höchstens sein?
Balancefaktor, AVL-Baum
Für einen Knoten sei die Höhe seines Teilbaums, mit . Der Balancefaktor von ist
.
Ein AVL-Baum ist ein binärer Suchbaum, in dem für jeden Knoten gilt. Ein Knoten mit heißt unausgeglichen. Jeder Knoten speichert seine Höhe, damit Balancefaktoren in berechnet werden können. (Manche Bücher nehmen links minus rechts; dann kehren sich alle Vorzeichen um.)
Ein AVL-Baum und ein Gegenbeispiel
Ein AVL-Baum und ein Gegenbeispiel
Der Baum aus der Vermutung, 50(30(20, 40(35, –)), 70(–, 80)), mit Höhen und Balancefaktoren:
| Knoten | linkes Kind | rechtes Kind | Höhe | bal |
|---|---|---|---|---|
| 50 | 30 | 70 | 3 | |
| 30 | 20 | 40 | 2 | |
| 20 | – | – | 0 | |
| 40 | 35 | – | 1 | |
| 35 | – | – | 0 | |
| 70 | – | 80 | 1 | |
| 80 | – | – | 0 |
Zum Beispiel ist und . Alle Werte liegen in .
Gegenbeispiel: In 50(30(20(10, –), –), 70(–, 80(–, 90))) ist die Wurzel perfekt ausgeglichen, . Trotzdem ist es kein AVL-Baum: und . Die Bedingung muss an jedem Knoten gelten, nicht nur an der Wurzel.
Welchen Balancefaktor hat die Wurzel von 8(4(2, 6(5, 7)), 10)?
AVL-Bäume haben logarithmische Höhe
Sei die kleinste Knotenzahl eines AVL-Baums der Höhe . Dann gilt , und für
.
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | |
|---|---|---|---|---|---|---|---|---|
| 1 | 2 | 4 | 7 | 12 | 20 | 33 | 54 |
Mit dem goldenen Schnitt ist . Für jeden AVL-Baum mit Knoten und Höhe folgt
Beweisidee: Ein möglichst dünner AVL-Baum hat unter der Wurzel einen möglichst dünnen Baum der Höhe und einen der Höhe ; das wächst wie die Fibonacci-Zahlen, also exponentiell in .
wächst: Ein AVL-Baum der Höhe hat ein Kind der Wurzel, dessen Teilbaum Höhe hat und selbst ein AVL-Baum ist, und mindestens einen Knoten mehr. Also .
Rekurrenz: Ein AVL-Baum der Höhe hat einen Teilbaum der Höhe unter der Wurzel. Wegen an der Wurzel hat der andere Höhe oder , also mindestens Knoten, denn wächst. Mit der Wurzel sind das mindestens Knoten. Gleichheit wird erreicht: Hängt man unter eine Wurzel einen kleinsten AVL-Baum der Höhe und einen der Höhe (mit passenden Schlüsseln), entsteht ein AVL-Baum der Höhe mit genau so vielen Knoten. und sind klar.
Abschätzung: Es gilt (nachrechnen: ). Durch Induktion: , , und für ist .
Folgerung: Ein AVL-Baum der Höhe mit Knoten hat . Logarithmieren zur Basis ergibt , und .
Wie hoch kann ein AVL-Baum mit Knoten höchstens sein?
Rotation
Eine Rechtsrotation an einem Knoten mit linkem Kind hebt nach oben. Sind , und Teilbäume (auch leere), so wird
y(x(A, B), C) zu x(A, y(B, C)).
Der mittlere Teilbaum wechselt dabei von zu . Die Linksrotation an ist das Spiegelbild: x(A, y(B, C)) wird zu y(x(A, B), C).
| Zeile | Einrückung | Anweisung |
|---|---|---|
| 1 | 0 | |
| 2 | 1 | |
| 3 | 1 | |
| 4 | 1 | |
| 5 | 1 | |
| 6 | 1 | |
| 7 | 1 |
setzt ; zuerst, weil jetzt unter hängt. Der Aufrufer schreibt den zurückgegebenen Knoten dorthin, wo vorher hing.
Die Suchbaumeigenschaft bleibt erhalten: Vor und nach der Rotation lautet die Inorder-Folge „, , , , “. Jeder Schlüssel in ist größer als (er lag rechts von ) und kleiner als (er lag links von ), steht also auch nach der Rotation auf der richtigen Seite von beiden. Für die Knoten in , , 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 .
Die vier Fälle beim Einfügen
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 von unten. Wo der neue Knoten unter liegt, entscheidet über die Reparatur:
| Fall | neuer Knoten liegt im | erkennbar an | Reparatur |
|---|---|---|---|
| LL | linken Teilbaum des linken Kindes | , linkes Kind | Rechtsrotation an |
| RR | rechten Teilbaum des rechten Kindes | , rechtes Kind | Linksrotation an |
| LR | rechten Teilbaum des linken Kindes | , linkes Kind | Linksrotation am linken Kind, dann Rechtsrotation an |
| RL | linken Teilbaum des rechten Kindes | , rechtes Kind | Rechtsrotation am rechten Kind, dann Linksrotation an |
LR und RL heißen Doppelrotationen. Als Pseudocode, aufgerufen in Zeile 7 von (statt steht dort ):
| Zeile | Einrückung | Anweisung |
|---|---|---|
| 1 | 0 | |
| 2 | 1 | |
| 3 | 1 | |
| 4 | 2 | |
| 5 | 2 | |
| 6 | 1 | |
| 7 | 2 | |
| 8 | 2 | |
| 9 | 1 |
Weil die Rekursion von unten nach oben zurückkehrt, kommt der tiefste unausgeglichene Knoten zuerst dran.
Beispiel LR: In 30(10(–, 20), –) hat die den Balancefaktor und ihr linkes Kind den Wert . Linksrotation an ergibt 30(20(10, –), –), das ist jetzt ein LL-Fall; die Rechtsrotation an ergibt 20(10, 30). Der mittlere Schlüssel der drei landet oben.
Eine Reparatur genügt beim Einfügen
Nach der Rotation (einfach oder doppelt) am tiefsten unausgeglichenen Knoten hat der reparierte Teilbaum wieder dieselbe Höhe wie vor dem Einfügen. Deshalb sind danach alle Vorfahren ausgeglichen, und ein Einfügen kostet Schritte mit höchstens einer Einfach- oder Doppelrotation.
Wir zeigen LL und LR; RR und RL sind spiegelbildlich. Sei das linke Kind von und der rechte Teilbaum von . Vor dem Einfügen war ausgeglichen und hatte nachher , also ist der linke Teilbaum um eine Ebene gewachsen: Vorher hatte Höhe und Höhe , also Höhe . Jetzt hat Höhe und ist ausgeglichen (sonst wäre der tiefste unausgeglichene Knoten). Seien und die Teilbäume von .
LL: Der neue Knoten liegt in , und ist auf Höhe gewachsen. hat Höhe : Wäre ebenfalls , hätte schon vorher Höhe gehabt. Nach der Rechtsrotation x(A, y(B, C)) mit hat die Teilbäume und der Höhe , also Höhe und Balance ; hat und , beide Höhe , also Höhe und Balance . Das ist die alte Höhe von .
LR: Der neue Knoten liegt in , hat jetzt Höhe und Höhe (dasselbe Argument). Sei die Wurzel von mit Teilbäumen , der Höhen höchstens . Die Doppelrotation ergibt w(x(A, ), z(, C)). Alle vier Teilbäume haben Höhe oder , mindestens und haben Höhe . Also haben und Höhe mit Balance in bzw. , und hat Höhe mit Balance , wieder die alte Höhe.
Laufzeit: Der Weg nach unten und zurück hat Länge nach dem vorigen Satz, an jedem Knoten fällt Arbeit an.
Eine Einfügefolge vollständig durchgespielt
Eine Einfügefolge vollständig durchgespielt
Wir fügen in einen leeren AVL-Baum ein. Die zweite Spalte nennt den tiefsten unausgeglichenen Knoten nach dem Einfügen.
| eingefügt | unausgeglichen | Fall | Reparatur | Baum danach |
|---|---|---|---|---|
| 10 | – | – | – | 10 |
| 20 | – | – | – | 10(–, 20) |
| 30 | 10, bal | RR | links an 10 | 20(10, 30) |
| 25 | – | – | – | 20(10, 30(25, –)) |
| 28 | 30, bal | LR | links an 25, rechts an 30 | 20(10, 28(25, 30)) |
| 27 | 20, bal | RL | rechts an 28, links an 20 | 25(20(10, –), 28(27, 30)) |
| 5 | 20, bal | LL | rechts an 20 | 25(10(5, 20), 28(27, 30)) |
| 4 | – | – | – | 25(10(5(4, –), 20), 28(27, 30)) |
Genauer bei der : Sie landet rechts unter der , also 20(10, 30(25(–, 28), –)). Von unten: , . Das linke Kind hat , also Fall LR. Linksrotation an ergibt 30(28(25, –), –), Rechtsrotation an ergibt 28(25, 30). Die Wurzel hatte vor der Reparatur ebenfalls , danach , wie der Satz verspricht.
Der fertige Baum:
| Knoten | linkes Kind | rechtes Kind | Höhe | bal |
|---|---|---|---|---|
| 25 | 10 | 28 | 3 | |
| 10 | 5 | 20 | 2 | |
| 5 | 4 | – | 1 | |
| 4 | – | – | 0 | |
| 20 | – | – | 0 | |
| 28 | 27 | 30 | 1 | |
| 27 | – | – | 0 | |
| 30 | – | – | 0 |
Ohne Ausgleich ergäbe dieselbe Folge den Baum 10(5(4, –), 20(–, 30(25(–, 28(27, –)), –))) mit Höhe . Der AVL-Baum hat Höhe , die kleinstmögliche für Knoten.
In den fertigen Baum 25(10(5(4, –), 20), 28(27, 30)) wird die eingefügt. Was passiert?
Einfachrotation im Zickzack-Fall
Einfachrotation im Zickzack-Fall
In 30(10(–, 20), –) ist die mit unausgeglichen. Eine einfache Rechtsrotation an scheint naheliegend. Sie ergibt aber 10(–, 30(20, –)): Jetzt ist die mit unausgeglichen. Der mittlere Teilbaum (hier die ) ist von der einen Seite auf die andere gewandert, und die Schieflage hat nur die Richtung gewechselt.
Vor der Rotation das Vorzeichen des Kindes prüfen. Zeigen und sein Kind in verschiedene Richtungen ( und oder und ), braucht es die Doppelrotation: erst am Kind, sodass beide in dieselbe Richtung zeigen, dann an . Ergebnis hier: 20(10, 30).
Löschen, kurz
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 auf, wie beim Einfügen. Ist dort das Kind auf der schwereren Seite ausgeglichen (), genügt eine Einfachrotation; der Pseudocode oben behandelt das schon richtig.
Beispiel: Aus 25(10(5(4, –), 20), 28(27, 30)) wird die gelöscht. Dann ist und , also eine Rechtsrotation an : 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 auf ). Dann kann weiter oben ein neuer unausgeglichener Knoten entstehen. Im schlechtesten Fall wird auf jeder Ebene rotiert, das sind Rotationen; die Laufzeit bleibt .
Zusammenfassung
Im AVL-Baum ist an jedem Knoten .
, also .
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 .
Beim Löschen kann auf mehreren Ebenen rotiert werden, die Kosten bleiben .
Rot-Schwarz-Bäume rotieren seltener; B-Bäume speichern viele Schlüssel je Knoten.
Übungen
Welchen Balancefaktor hat der Knoten im AVL-Baum 25(10(5(4, –), 20), 28(27, 30))?
Du fügst in einen leeren AVL-Baum ein. Wie wird nach der repariert?
Du fügst aufsteigend in einen leeren AVL-Baum ein. Welcher Schlüssel steht danach in der Wurzel?
Wie hoch kann ein AVL-Baum mit Knoten höchstens sein?
Wie viele Knoten hat ein Fibonacci-Baum (ein AVL-Baum mit kleinstmöglicher Knotenzahl) der Höhe ?
Im Fall LR ist das linke Kind von und das rechte Kind von . Zeige, dass die Doppelrotation nach oben bringt, mit links und rechts darunter, und dass die Suchbaumeigenschaft erhalten bleibt.
Zeige, dass jeder AVL-Baum der Höhe mindestens Knoten hat, und folgere daraus ohne den goldenen Schnitt, dass gilt.