AVL-Baum

Suchbäume – und damit auch die AVL-Bäume – sind Lösungen des sogenannten „Wörterbuchproblems“. Eine prinzipielle Erläuterung findet sich im Abschnitt Motivation im Artikel Binärer Suchbaum.

Den Suchbäumen gemeinsam ist, dass sie Dynamik unterstützen, das heißt, dass Einfügen und/oder Löschen von Elementen wichtig ist. Da bei diesen Operationen die Gefahr besteht, dass die Balance des Baums verloren geht, wurden verschiedene Balance-Kriterien für Binärbäume entwickelt. Bei den meisten sind die Aufwände für das Suchen, Einfügen und Löschen zumindest im Mittel logarithmisch, wenn auch mit unterschiedlichen konstanten Faktoren.

Beim AVL-Baum wird die Balance über die Höhe definiert, er ist ein höhen-balancierter binärer Suchbaum.

Als den Balance-Faktor[3] ${\displaystyle \mathrm {BF} (t)}$ eines Knotens resp. Teilbaums[Anm 1] ${\displaystyle t}$ in einem Binärbaum bezeichnet man die Höhendifferenz

${\displaystyle \mathrm {BF} (t):=\mathrm {Height} (t_{r})-\mathrm {Height} (t_{l})}$,[Anm 2]

wobei ${\displaystyle \mathrm {Height} (t)}$ die Höhe des Baums ${\displaystyle t}$, und ${\displaystyle t_{l}}$ der linke, ${\displaystyle t_{r}}$ der rechte Kindbaum von ${\displaystyle t}$ ist.[Anm 3] Ein Knoten ${\displaystyle t}$ mit ${\displaystyle \mathrm {BF} (t)=0}$ wird als höhengleich oder ausgewogen, einer mit ${\displaystyle \mathrm {BF} (t)<0}$ als links- und einer mit ${\displaystyle \mathrm {BF} (t)>0}$ als rechtslastig bezeichnet.

Ein binärer (Such-)Baum ist genau dann ein AVL-Baum, wenn die AVL-Bedingung

${\displaystyle -1\;\leq \;\mathrm {BF} (t)\;\leq \;+1}$

an jedem Knoten ${\displaystyle t}$ eingehalten wird.[Anm 4]

Die wichtigsten Operationen bei den Suchbäumen – und damit beim AVL-Baum – sind: Suchen einerseits sowie Einfügen und Löschen andererseits. Mit der Eigenschaft, dass alle diese Operationen im schlechtesten Fall (Worst Case) logarithmische Komplexität haben, gehört der AVL-Baum zu den höhenbalancierten binären Suchbäumen.

 // Schleife vom Blatt bis möglicherweise zur Wurzel:
 for (X = Z->parent; X != null; X = Z->parent) {
     if (Z == X->childR) { // Der rechte Teilbaum ist es, der höher wird.
         if (X->BF <= 0) {    // X ist nicht rechtslastig
             if (X->BF < 0) { // X ist linkslastig
                 X->BF = 0; // Z’s Höhenzunahme aufgefangen bei X
                 break; // Verlassen der Schleife
             }
             X->BF = +1;
             Z = X; // Height(Z) wird höher um 1
             continue;
         }
         else {              // X ist rechtslastig
             // ===> X->BF temporär == +2
             // ===> Rebalancierung erforderlich
             G = X->parent; // Retten X->parent vor Rotation
             if (Z->BF < 0)                 // Rechts-Links-Situation   (s. Abbildung 3)
                 N = rotate_RightLeft(X,Z); // Doppelrotation: Right(Z) dann Left(X)
             else                           // Rechts-Rechts-Situation  (s. Abbildung 2)
                 N = rotate_Left(X,Z);      // Einfachrotation Left(X)
         }
     }
     else { // Z == X->childL: der linke Teilbaum wird höher
         if (X->BF >= 0) {    // X ist nicht linkslastig
             if (X->BF > 0) { // X ist rechtslastig
                 X->BF = 0; // Z’s Höhenzunahme aufgefangen bei X
                 break; // Verlassen der Schleife
             }
             X->BF = –1;
             Z = X; // Height(Z) wird höher um 1
             continue;
         }
         else {               // X ist linkslastig
             // ===> X->BF temporär == –2
             // ===> Rebalancierung erforderlich
             G = X->parent; // Retten X->parent vor Rotation
             if (Z->BF > 0)      // Links-Rechts-Situation
                 N = rotate_LeftRight(X,Z); // Doppelrotation: Left(Z) dann Right(X)
             else                           // Links-Links-Situation
                 N = rotate_Right(X,Z);     // Einfachrotation Right(X)
         }
     }
     // Nach der Rotation die Anpassung der Verknüpfung N<->G:
     // N ist die neue Wurzel des rebalancierten Teilbaums
     // Höhe ändert sich nicht: Height(N) == alte Height(X)
     N->parent = G;
     if (G != null) {
         if (X == G->childL)
             G->childL = N;
         else
             G->childR = N;
     }
     else
         tree->root = N; // N ist die neue Wurzel des ganzen Baums
     break;

     // Da ist kein fall thru, nur break; oder continue;
 }
 // Wird die Schleife nicht durch ein break; beendet,
 //   dann wird der ganze Baum um 1 höher.

 // Schleife vom Blatt bis möglicherweise zur Wurzel:
 for (X = N->parent; X != null; X = G) {
     G = X->parent; // Retten X->parent vor Rotation
     if (N == X->childL) { // Der linke Teilbaum ist es, der niedriger wird.
         if (X->BF <= 0) {    // X ist nicht rechtslastig
             if (X->BF < 0) { // X ist linkslastig
                 X->BF = 0;
                 N = X;       // Height(N) wird niedriger um 1
                 continue;
             } // X->BF == 0
             X->BF = +1;      // N’s Höhenabnahme aufgefangen bei X
             break; // Verlassen der Schleife
         }
         else { // X ist rechtslastig
             // ===> X->BF temporär == +2
             // ===> Rebalancierung erforderlich
             Z = X->childR; // das Geschwister von N (höher um 2)
             b = Z->BF;
             if (b < 0)                     // Rechts-Links-Situation   (s. Abbildung 3)
                 N = rotate_RightLeft(X,Z); // Doppelrotation: Right(Z) dann Left(X)
             else                           // Rechts-Rechts-Situation  (s. Abbildung 2)
                 N = rotate_Left(X,Z);      // Einfachrotation Left(X)
         }
     }
     else { // (N == X->childR): Der rechte Teilbaum wird niedriger
         if (X->BF >= 0) {    // X ist nicht linkslastig
             if (X->BF > 0) { // X ist rechtslastig
                 X->BF = 0;
                 N = X;       // Height(N) wird niedriger um 1
                 continue;
             } // X->BF == 0
             X->BF = –1;      // N’s Höhenabnahme aufgefangen bei X
             break; // Verlassen der Schleife
         }
         else { // X ist linkslastig
             // ===> X->BF temporär == –2
             // ===> Rebalancierung erforderlich
             Z = X->childL; // das Geschwister von N (höher um 2)
             b = Z->BF;
             if (b > 0)                     // Links-Rechts-Situation
                 N = rotate_LeftRight(X,Z); // Doppelrotation: Left(Z) dann Right(X)
                else                        // Links-Links-Situation
                 N = rotate_Right(X,Z);     // Einfachrotation Right(X)
         }
     }
     // Nach der Rotation die Anpassung der Verknüpfung N<->G:
     // N ist die neue Wurzel des rebalancierten Teilbaums
     N->parent = G;
     if (G != null) {
         if (X == G->childL)
             G->childL = N;
         else
             G->childR = N;
     }
     else
         tree->root = N; // N ist die neue Wurzel des ganzen Baums

     if (b == 0) // der in Abbildung 2 blass gehaltene Fall
         break;  // Die Höhe ändert sich nicht: Verlassen der Schleife.

     // Height(N) wird niedriger um 1 (== alte Height(X)-1)
 }
 // Wird die Schleife durch (N->parent == null) beendet,
 //   dann verringert sich die Höhe des ganzen Baums um 1.

Abb. 2: Einfachrotation
Links(X)

Wenn bei einer Operation ein Höhenunterschied von mehr als 1 zwischen zwei Geschwister-Teilbäumen entsteht, ist beim Elterknoten das AVL-Kriterium verletzt. Eine entsprechende Korrektur heißt „Rebalancierung“. Als Werkzeuge hierfür eignen sich die sogenannten Rotationen.

Für Einfügungen und Löschungen, bei denen die temporäre Höhendifferenz absolut nie über 2 hinausgeht, werden zwei Varianten benötigt: Einfach- und Doppelrotation. Eine Einfachrotation leistet die Rebalancierung, wenn das innere Kind des um 2 höheren Geschwisters (Z in den zwei Abbildungen 2 und 3[11]), das ist das Kind mit einer Kindesrichtung, die der von Z entgegengesetzt ist, (t₂₃ in der Abbildung 2 beziehungsweise Y in der Abbildung 3) nicht höher ist als sein Geschwister, das äußere Kind (t₄ in beiden Abbildungen). Dieser Fall wird in der Literatur als Rechts-Rechts- (resp. gespiegelt Links-Links-)Situation bezeichnet, da X rechts- und Z nicht linkslastig ist, das heißt die zwei Balance-Faktoren +2 und +1 (beim Löschen auch 0) sind, kurz: die Balance zweimal hintereinander die gleiche Richtung hat. Der andere Fall, bei dem das innere Kind höher ist, wird von einer Doppelrotation abgedeckt – in der Literatur Rechts-Links- (resp. Links-Rechts-)Situation genannt, da X rechts- und Z linkslastig ist, das heißt die zwei Balance-Faktoren +2 und −1 sind, kurz: die Balance die Richtung wechselt.

Die Schlüssel bewegen sich bei Rotationen nur „vertikal“ (innerhalb der senkrechten Raster). Die In-order-Reihenfolge der Knoten, die ja die Sortierreihenfolge („horizontal“) abbildet, bleibt also vollkommen erhalten.

Eine Rotation umfasst nur eine konstante Anzahl von Verknüpfungsänderungen an einer konstanten Anzahl von Knoten.

Einfachrotation

Sie wird im Original Малое вращение (kleine Drehung) genannt.

Die obenstehende Abbildung 2 zeigt eine Rechts-Rechts-Situation. In der oberen Hälfte haben die beiden Teilbäume Z und t₁ des Knotens X einen Höhenunterschied von +2. Das innere Kind t₂₃ des um 2 höheren Knotens Z ist nicht höher als sein Geschwister t₄.
Dies kann nach einem Einfügen in den Teilbaum t₄ oder nach einem Löschen aus dem Teilbaum t₁ auftreten. Der in der Abbildung 2 blass gehaltene Fall, dass t₂₃ gleich hoch ist wie t₄, kommt nur beim Löschen vor.

Die Rebalancierung (gezeigt in der unteren Hälfte der Abbildung) gelingt durch eine Einfachrotation nach links. Die anzupassenden 3 Verknüpfungen sind in der Abbildung verstärkt gezeichnet, und bei beiden Knoten X und Z ändern sich die Balance-Faktoren.

Die Höhe des neuen Teilbaums Z ist bei einer Einfügung gleich der von X vor der Operation. Dies ist bei einer Löschung genauso, wenn Z nicht rechtslastig war. Bei rechtslastigem Z vermindert sich jedoch die Höhe um 1, und die Überprüfung der Balance-Faktoren oberhalb muss weitergehen.

Die gespiegelte, die Links-Links-Situation wird von einer Einfachrotation nach rechts behandelt.

Code-Beispiel rotate_Left

Eingabe: X = Wurzel des Teilbaums, der nach links rotiert werden soll Z = sein rechtes Kind, nicht linkslastig     mit Höhe ${\displaystyle \mathrm {Height} (Z)==\mathrm {Height} (X\to {\text{childL}})+2}$ Rückgabewert: die neue Wurzel des rebalancierten Teilbaums node* rotate_Left(node* X,node* Z) { // Z is um 2 höher als sein Geschwister t23 = Z->childL; // das innere Kind von Z X->childR = t23; if (t23 != null) t23->parent = X; Z->childL = X; X->parent = Z; // Kommt bei einer Einfügung nicht vor: if (Z->BF == 0) { // t23 war gleich hoch wie t4 X->BF = +1; // t23 jetzt höher Z->BF = –1; // t4 jetzt niedriger als X } else // Ende: Nicht bei Einfügung { X->BF = 0; Z->BF = 0; } return Z; // return neue Wurzel des rebalancierten Teilbaums }

Doppelrotation

Abb. 3: Doppelrotation
RechtsLinks(X, Z) = Rechts(Z) + Links(X)

Sie wird im Original Большое вращение (große Drehung) genannt.

Die in der Abbildung 3 gezeigte Situation unterscheidet sich von der in Abbildung 2 darin, dass der mittlere Kindbaum (mit Wurzel Y), das ist das innere Kind des um 2 höheren Knotens Z, höher ist als sein Geschwister t₄: eine Rechts-Links-Situation, da X rechts- und Z linkslastig ist.
Das kann nach der Einfügung des Knotens Y oder einer Einfügung in einen der Teilbäume t₂ oder t₃ oder nach einer Löschung aus dem Teilbaum t₁ passieren. Der Fall, bei dem die Teilbäume t₂ und t₃ gleich hoch sind und der Teilbaum Y höher als t₄, kommt nur bei der Löschung vor.

Die Doppelrotation, deren Ergebnis im unteren Drittel der Abb. gezeigt ist, ist eine Rechtsrotation durch Z (gegen die Linkslastigkeit von Z, mittleres Drittel) gefolgt von einer Linksrotation durch X (gegen die Rechtslastigkeit von X). Sie bewirkt eine zweimalige Anhebung des höheren (und inneren) Kindes Y von Z.

Die anzupassenden 5 Verknüpfungen sind in der Abbildung verstärkt gezeichnet, und bei allen 3 Knoten X, Y und Z ändern sich die Balance-Faktoren.[Anm 10]

Die Höhe des neuen Teilbaums Y ist nach einer Einfügung gleich der von X vor der Operation. Bei einer Löschung ist die Höhe jedoch um 1 vermindert, mit der Folge, dass oberhalb die Überprüfung der Balance-Faktoren weitergehen muss.

Bei einer Links-Rechts-Situation wird die gespiegelte Version, das heißt eine Linksrotation gefolgt von einer Rechtsrotation, benötigt.

Code-Beispiel rotate_RightLeft

Eingabe: X = Wurzel des Teilbaums, der rotiert werden soll Z = sein rechtes Kind, linkslastig     mit Höhe ${\displaystyle \mathrm {Height} (Z)==\mathrm {Height} (X\to {\text{childL}})+2}$ Rückgabewert: die neue Wurzel des rebalancierten Teilbaums node* rotate_RightLeft(node* X,node* Z) { // Z is um 2 höher als das Geschwister Y = Z->childL; // das innere Kind von Z // Y is um 1 höher als das Geschwister t3 = Y->childR; Z->childL = t3; if (t3 != null) t3->parent = Z; Y->childR = Z; Z->parent = Y; t2 = Y->childL; X->childR = t2; if (t2 != null) t2->parent = X; Y->childL = X; X->parent = Y; if (Y->BF == 0) { // t2 und t3 gleich hoch // (beide null im Fall der Einfügung von Y) X->BF = 0; Z->BF = 0; } else // Ende: Nicht bei Einfügung if (Y->BF > 0) { // t3 war höher X->BF = –1; // t1 jetzt höher Z->BF = 0; } else { // t2 war höher X->BF = 0; Z->BF = +1; // t4 jetzt höher } Y->BF = 0; return Y; // return neue Wurzel des rebalancierten Teilbaums }

Die folgenden zwei Operationen haben ganze AVL-Bäume als Ein- und Ausgabeoperanden. Sie gehören nicht zum Standardsatz und fehlen in manchen Implementierungen. Es soll aber hier gezeigt werden, dass auch sie mit logarithmischem Aufwand durchgeführt werden können.

Verketten

Abb. 4: Verkettung von 2 AVL-Bäumen

Zwei AVL-Bäume können mit logarithmischem Aufwand verkettet (konkateniert) werden (englisch: concat oder auch nur cat). Für die Sortierfolge müssen natürlich alle Schlüssel des ersten Baums allen Schlüsseln des zweiten vorangehen.[12]

Algorithmus

Man steigt an der rechten Flanke des ersten Baums (siehe Abbildung 4 – die grauen Pfeile zeigen den Weg durch den Graphen) und an der linken des zweiten bis zu den Blättern hinab und merkt sich die Knoten auf den Pfaden zusammen mit ihren Höhen. Ohne Beschränkung der Allgemeinheit sei der erste Baum der höhere (wie in der Abbildung). Dem zweiten Baum wird sein erstes Element H in AVL-Manier entnommen. Es spielt nachher die Rolle eines „Bindeglieds“. Die Höhe des zweiten Baums sei jetzt h (möglicherweise 0). Man sucht nun in der rechten Flanke des ersten Baums nach einem Knoten G der Höhe h+1 oder h (einen von beiden muss es geben; gibt es beide, wird der höhere bevorzugt). Man macht G zum Kind des Bindeglieds H und den zweiten Baum zum zweiten Kind von H, was bei H einen AVL-konformen Balance-Faktor von 0 oder −1 ergibt. Dann wird H beim Elter F von G an Gs Stelle als Kind eingehängt. Der Höhenunterschied zwischen dem neuen H und E ist zwischen 0 und +2 (wenn E die Höhe h–1 hat, dann hat G die Höhe h, und das neue H die Höhe h+1). Nach einer ersten Anpassung mit eventueller (Doppel-)Rotation müssen noch aufsteigend die Balance-Faktoren wie bei einer Einfügung überprüft und gegebenenfalls korrigiert werden. Dabei kann die Höhe des Baums um 1 zunehmen.

Spalten

Abb. 5: Spalten eines Binärbaums.
Dick rot gestrichelt: Trennlinie, spezifiziert durch (Knoten, Richtung)
${\displaystyle I-\to -H}$: aufzulösende Kind-Elter-Beziehung zwischen I_n und H_n+1
${\displaystyle H\!\cdot \!\cdot \!\cdot \!\cdot \!\cdot \!\cdot I}$: Pfad ohne Überquerung der Trennlinie (von H_n nach I_n=:A)
${\displaystyle I\!\cdot \;\cdot \;\cdot \;\cdot H}$: Pfad trifft die Trennlinie zweimal (von I_n nach H_n+2)

Etwas komplizierter als das Verketten ist das Aufspalten (englisch: split) eines AVL-Baums in zwei separate AVL-Bäume an einem externen Knoten, also einer Stelle zwischen zwei internen Knoten (Schlüsseln), die als Paar (Knoten, Richtung) einschließlich des Pfades zur Wurzel gegeben sei. Links davon liegt die linke Partition mit den kleineren Schlüsseln und rechts davon die rechte mit den größeren. Die so definierte Trennlinie (dick rot gestrichelt in der Abbildung 5) zerschneidet Kanten des Baums auf dem Pfad des Knotens zur Wurzel, so dass sich links wie rechts ein Wald von „Schnipseln“ ergibt.

Jeder der so definierten zwei Wälder kann mit logarithmischem Aufwand zu einem AVL-Baum zusammengefügt werden derart, dass das Ergebnis einer nachfolgenden Verkettung dieser zwei AVL-Bäume in Bezug auf Einträge und deren Reihenfolge zum ursprünglichen Baum äquivalent ist.[12]

Algorithmus

Die Schnipsel sind Bäume, die bis auf eventuell einen Knoten („Stummel“) (H in den Abbildungen 5 und 6) auf hoher Ebene mit Ausgangsgrad 1 (nicht unbedingt die Wurzel des Schnipsels) in AVL-Form sind. Dieser fungiert beim Verketten mit dem nächstniedrigeren Schnipsel auf der gleichen Seite als Bindeglied. Im Folgenden ist die Indizierung der Knoten so gewählt, dass auf der einen Seite der Trennlinie sich nur geradzahlige, auf der anderen sich nur ungeradzahlige Indizes befinden. Die Indizes wachsen beim Aufstieg in Richtung Wurzel. Vollständige Induktion auszuführen aufsteigend auf beiden Seiten der Trennlinie Induktionsanfang (Abbildung 5): Hat der gegebene (die Trennlinie definierende) Knoten ein Kind in der gegebenen Richtung, dann befindet sich dieses auf der anderen Seite der Trennlinie, ist in AVL-Form und werde I1 genannt. Der gegebene Knoten (nunmehr ein Stummel) werde H2 genannt. H2 ist mit einem Schnipsel I0, welcher in diesem Fall leer ist, zu verketten. Hat der gegebene Knoten kein Kind in der gegebenen Richtung, dann sei H2 sein niedrigster Vorfahr in jener Richtung (also auf der anderen Seite der Trennlinie). I1 sei dessen Kind auf der Seite des gegebenen Knotens – es ist in AVL-Form. H2 ist ein Stummel, der mit einem Schnipsel I0, welcher in diesem Fall leer ist, zu verketten ist. Damit ist I0 (der leere Baum) der niedrigste Schnipsel auf der einen und I1 auf der anderen Seite. Beide sind in AVL-Form. Der Stummel H2 ist ursprünglicher Elter von I1 auf der Gegenseite der Trennlinie und niedrigster Vorfahr von I0 auf der gleichen Seite. Abb. 6: Ein Induktionsschritt beim Spalten eines AVL-Baums Induktionsschritt (siehe Abbildungen 5 und 6): Beim n-ten Induktionsschritt heißt der niedrigste Schnipsel In. Obwohl die Seite bei jedem Induktionsschritt wechselt, sei der Einfachheit der Erläuterung halber angenommen, dass In wie I in der Abbildung 6 sich links von der Trennlinie befindet. I ist nach Induktionsvoraussetzung ein AVL-Baum. Sein niedrigster Vorfahr auf der linken Seite ist der Stummel H (=:Hn+2). (Dessen rechtes Kind liegt auf der anderen Seite der Trennlinie, ist auch schon in AVL-Form und hat den Namen In+1.) Die ursprüngliche Höhe von H sei h (Abbildung 6 oben). Zerschnittene Elter-Kanten (schwarz gestrichelt mit Pfeil) und die zurückbleibenden Stummel erkennt man am Wechsel der Kindesrichtung beim Aufstieg im Pfad. Dabei sind die (ursprünglichen) Höhen anhand der Balance-Faktoren aufs genaueste mitzuschreiben. Der Teilbaum des Einzelkindes D von H wird mit dem Schnipsel I unter Einsatz von H als Bindeglied verkettet. Bei der Verkettung spielen die Knoten D, F, H und I in der Abbildung 6 dieselbe Rolle wie die Knoten gleichen Namens in der Abbildung 4. Dabei kann Ds Höhe um 1 zunehmen. Falls nun H die Wurzel war, ist der Algorithmus beendet mit D, welches in AVL-Form ist, als der neuen Wurzel des linken Baums. Falls H linkes Kind war, wird D zum neuen niedrigsten Schnipsel auf der linken Seite, erhält den Namen In+2, und der Induktionsschritt n ist beendet. War H rechtes Kind, dann wird D zum dementsprechend rechten Kind bei seinem vormaligen Großelter C gemacht, damit zum Geschwister seines vormaligen Onkels B. Die Höhendifferenz zu letzterem ist maximal 3. Die AVL-Balance von C lässt sich durch Rotationen herstellen, wobei die Höhe von C um 1 abnehmen kann. (Die Vorgehensweise bei einem Höhenunterschied von 3 ähnelt der bei einem von 2: Ist das innere Kind des höheren Geschwisters niedriger als das äußere Kind, kann man die AVL-Balance mit einer Einfachrotation herstellen. Ist es höher, kommt man mit einer Doppelrotation durch. Sind beide Kinder gleich hoch, hängt es vom Balance-Faktor des inneren Kindes ab: ist der höhengleich, macht’s eine Doppelrotation; ist er außenlastig, schaffen’s zwei Rotationen; ist er innenlastig, geht’s mit drei Rotationen.) Man sucht auf der linken Seite aufsteigend nach dem ersten Vorfahr A(=:In+2) im Pfad, der linkes Kind (oder Wurzel) ist. Sein Elter Hn+3 ist niedrigster Vorfahr von In+1 auf der rechten Seite. Links, auf den Ebenen hinauf bis A sind die Balance-Faktoren wie bei einer Löschung zu überprüfen und gegebenenfalls anzupassen, wobei die Höhe um 1 abnehmen kann. Damit ist In so in den Schnipsel A integriert, dass A (oder ein anderer Knoten, der sich bei einer eventuellen Rotation als Wurzel in den Pfad geschoben hat) wieder ein AVL-Baum ist – und den niedrigsten Schnipsel In+2 des Induktionsschrittes n+2 auf dieser linken Seite darstellt. Für den folgenden Induktionsschritt n+3 aber werden die Seiten gewechselt, rechts mit links vertauscht und den Knoten In+1, Hn+3 und In+3 die Rollen von In, Hn+2 und In+2 zugewiesen. Die innerhalb eines Induktionsschrittes besuchten Kanten (graue Pfeile in der Abbildung 6) betreffen nur Ebenen zwischen den Wurzeln von zwei Schnipseln, die auf derselben Seite übereinander liegen (In+2 über In respektive In+3 über In+1). Die Induktionsschritte auf der linken und rechten Seite greifen reißverschlussartig ineinander: der Aufstieg auf der rechten wird auf der linken Seite beim Verketten ab- und wieder aufgestiegen, woran sich ein Aufstieg anschließt, der auf der rechten Seite ab- und wieder aufgestiegen wird usw. Eine Ebene wird höchstens dreimal besucht, jedes Mal mit konstantem Aufwand. Damit ist der Gesamtaufwand fürs Spalten proportional zur Gesamthöhe.[13]

Zusätzlich zum Bedarf des binären Suchbaums muss in einem Knoten der Balance-Faktor mit seinen 3 Werten untergebracht werden: macht 2 Bits.[Anm 11]

Insbesondere wenn der Prozessor korrekt ausgerichtete Zeiger bevorzugt oder erzwingt, können die Balance-Bits von einem Zeigerfeld im Knoten absorbiert werden, so dass sie kein extra Speicherwort benötigen.

Ansonsten gelten für die Implementierung von AVL-Bäumen dieselben Empfehlungen wie für die binären Suchbäume im Allgemeinen. Auf die Besonderheiten des AVL-Cursors sei im Folgenden explizit eingegangen.

Die Menge der AVL-Bäume ist eine echte Teilmenge in der Menge der Rot-Schwarz-Bäume. Denn jeder Binärbaum, der das AVL-Kriterium erfüllt, lässt sich in einer das Rot-Schwarz-Kriterium erfüllenden Weise einfärben.[18]

Beweis

4 kleine AVL-Bäume in Rot-Schwarz-Färbung. Bei den geteilten Knoten gehen beide Farben. Behauptung: Hat der AVL-Baum eine gerade Höhe ${\displaystyle h}$, dann lässt er sich mit Schwarztiefe ${\displaystyle {\tfrac {h}{2}}}$ bei schwarzer Wurzel einfärben; ist ${\displaystyle h}$ ungerade, dann mit Schwarztiefe ${\displaystyle {\tfrac {h-1}{2}}}$ bei einer roten oder mit Schwarztiefe ${\displaystyle {\tfrac {h+1}{2}}}$ bei einer schwarzen Wurzel. (Die NIL-Knoten sind dabei nicht mitgezählt.) Beweis: Die Behauptung ist richtig für ${\displaystyle h\leq 1}$ (siehe Abbildung). Bei größerem geradem ${\displaystyle h}$ gibt es einen Kindbaum mit der ungeraden Höhe ${\displaystyle h-1}$, der sich nach Induktionsvoraussetzung mit roter Wurzel und Schwarztiefe ${\displaystyle {\tfrac {h-2}{2}}}$ einfärben lässt. Hat der andere Kindbaum dieselbe Höhe, so gilt für ihn dasselbe. Ist er niedriger, dann ist seine Höhe ${\displaystyle h-2}$ und gerade; er lässt sich also mit der gleichen Schwarztiefe (bei schwarzer Wurzel) einfärben. Nachdem die neue Wurzel schwarz eingefärbt ist, ist die Schwarztiefe im zusammengesetzten Baum ${\displaystyle {\tfrac {h}{2}}.}$ Bei größerem ungeradem ${\displaystyle h}$ hat einer der Kindbäume oder beide die gerade Höhe ${\displaystyle h-1,}$ die sich mit schwarzer Wurzel bei Schwarztiefe ${\displaystyle {\tfrac {h-1}{2}}}$ einfärben lässt. Ist der andere Kindbaum niedriger, dann ist seine Höhe ${\displaystyle h-2}$ und ungerade, lässt sich also mit glücklicherweise derselben Schwarztiefe ${\displaystyle {\tfrac {h-1}{2}}}$ bei schwarzer Wurzel einfärben. Alle Kindbäume haben schwarze Wurzeln, also kann die neue Wurzel rot eingefärbt werden und es ergibt sich eine Schwarztiefe von ${\displaystyle {\tfrac {h-1}{2}}.}$ Wird die neue Wurzel jedoch schwarz eingefärbt, dann ist die neue Schwarztiefe ${\displaystyle {\tfrac {h+1}{2}}.}$   ■

Kein AVL-Baum

Es gibt aber Rot-Schwarz-Bäume, die das AVL-Kriterium nicht erfüllen. Die nebenstehende Abb. zeigt zum Beispiel einen Rot-Schwarz-Baum mit 6 (inneren) Knoten und der externen Pfadlängensumme 21, während 20 die größte externe Pfadlängensumme bei AVL-Bäumen (und zugleich die kleinstmögliche für alle Binärbäume) dieser Größe ist. Konsequenterweise ist auch die Worst-Case-Höhe des AVL-Baums kleiner als die des Rot-Schwarz-Baums, und zwar um den Faktor ${\displaystyle {\frac {c}{2}}\approx 0{,}720}$ mit obigem ${\displaystyle c:={\frac {1}{\log _{2}\Phi }}}$ und dem Faktor 2 aus dem Höhenbeweis des Rot-Schwarz-Baums. Allgemein werden AVL-Bäume als besser balanciert und ihr Suchzeitverhalten als günstiger angesehen.

Der Speicherplatzbedarf ist praktisch identisch: 1 Bit für die Farbe gegenüber 2 oder auch 1 Bit(s)[Anm 11] für den Balance-Faktor.

Der Platzbedarf und das Laufzeitverhalten für die angeführten Operationen ist im Mittel und im Worst Case identisch. Das gilt auch für die amortisiert konstanten Modifikationskosten beim Einfügen.[9] Zwar bietet der Rot-Schwarz-Baum amortisiert konstante Modifikationskosten auch beim Löschen[19] und der AVL-Baum dort nur[Anm 15] im Mittel konstante. Anwendungen von binären Suchbäumen, die nur Sequenzen von Einfügungen und Löschungen – ganz ohne intervenierende Suchoperationen – enthalten, gehen am Zweck des Suchbaums vorbei. Sieht man also von dieser Art Anwendungen ab, ist das Gesamtverhalten einer Mischung von Suchen und Modifikation bei beiden Datenstrukturen amortisiert, im Mittel und im Worst Case logarithmisch.

Realistische Anwendungssituationen mit Performancedaten und -vergleichen – auch mit weiteren Suchalgorithmen und Spielarten der Datenstrukturen – finden sich bei Ben Pfaff.[20] Seine Ergebnisse zeigen in 79 Messungen unter anderem die sehr große Ähnlichkeit von AVL-Bäumen (AVL) und Rot-Schwarz-Bäumen (RB) mit Laufzeitverhältnissen ^AVL⁄_RB zwischen 0,677 und 1,077 bei einem Median von ≈0,947 und einem geometrischen Mittelwert von ≈0,910.

Als grundlegende Hilfsmittel der Informatik haben die binären Suchbäume ein großes Einsatzgebiet, in welchem sie aber auch hochgradig untereinander austauschbar sind. Konkrete Beispiele und Auswahlkriterien finden sich in Binärer Suchbaum#Anwendungen.

• Binärbaum
• Binärer Suchbaum
• Balancierter Baum
• Rot-Schwarz-Baum
• Splay-Baum
• Gewichteter binärer Suchbaum
• Fibonacci-Baum

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein: Introduction to Algorithms. 2. Auflage. MIT Press, Cambridge MA 2001, ISBN 0-262-03293-7.
• Ralf Hartmut Güting, Stefan Dieker: Datenstrukturen und Algorithmen. Stuttgart 2004, ISBN 978-3-519-22121-0.
• Donald E. Knuth: The Art of Computer Programming. 2. Auflage. Band 3: Sorting and Searching. Addison-Wesley, 1998, ISBN 0-201-89685-0, 6.2.3 Balanced Trees, S. 458–478.
• Udi Manber: Introduction to Algorithms – A Creative Approach. Addison-Wesley Publishing Company 1989, Kapitel 4.3.4, S. 75ff.
• Kurt Mehlhorn: Datenstrukturen und effiziente Algorithmen. Teubner Stuttgart 1988, ISBN 3-519-12255-3.
• Bernhard Wagner: Effiziente höhenbalancierte Binärbäume: Die neuen Algorithmen mit Beweis ihrer Korrektheit, 1 Auflage 2022, ISBN 979-8-35722559-7.

Commons: AVL-Bäume – Sammlung von Bildern, Videos und Audiodateien

• Paul E. Black: AVL tree. In: Dictionary of Algorithms and Data Structures. National Institute of Standards and Technology (NIST), 7. Juli 2014, abgerufen am 27. Juli 2016 (englisch).
• Algorithmenvisualisierung unter anderem für AVL-Bäume
• Kurz gehaltene Beschreibung der Rotationen
• AvlTree.cs vom 10. August 2012
• Ben Pfaff: An Introduction to Binary Search Trees and Balanced Trees. Free Software Foundation, Boston 2004, gnu.org (PDF gzip; 1675 kB).
• Ben Pfaff: Performance Analysis of BSTs in System Software. Stanford University, 2004, stanford.edu (PDF; 316 kB).

1. Da einem Knoten in umkehrbar eindeutiger Weise der von ihm gewurzelte maximale Unterbaum, „sein“ Teilbaum, zugeordnet werden kann, sollen der Kürze halber Eigenschaften wie Höhe, Balance, Elter-Kind-und-Geschwister-Beziehung usw. einem Knoten und einem solchen Teilbaum in gleicher Weise zukommen. Spielt dabei die Beziehung zum Elter eine Rolle, so sei noch spezifischer vom linken (oder rechten) Kindbaum die Rede.
   Umgekehrt fungiert, zum Beispiel beim Umhängen eines Teilbaums, dessen Wurzel als „Henkel“.
2. Im Prinzip kann man auch die gespiegelte Differenz nehmen. Der Text folgt Knuth und vielen weiteren Autoren.
3. Die Rekursionsgleichung für die Höhe ist

   ${\displaystyle \mathrm {Height} (t):=1+\max(\mathrm {Height} (t_{r}),\mathrm {Height} (t_{l}))}$.

4. Aus den Balance-Faktoren (≤ 2 Bits pro Knoten) lassen sich alle relevanten Daten für Einfügen und Löschen berechnen, es bedarf nicht der Kenntnis der absoluten Höhen.
5. gemäß der Definition Binärer Suchbaum#Abb1A, bei der die Knotenebenen gezählt werden und der nur aus der Wurzel bestehende Baum die Höhe 1 hat
6. Strebt beim Fibonacci-Baum die Anzahl ${\displaystyle n}$ der Knoten gegen unendlich, dann verhält sich seine mittlere Suchtiefe asymptotisch wie

   ${\displaystyle a\log _{2}n}$     mit     ${\displaystyle a:={\frac {c\Phi }{\sqrt {5}}}={\frac {\Phi }{{\sqrt {5}}\;\log _{2}\Phi }}\approx 1{,}042298}$,

   weicht also nur um etwa 4 Prozent von der idealen eines vollständigen Binärbaums ab. (Allerdings sind hinsichtlich der Suchtiefe nicht notwendigerweise die Fibonacci-Bäume am schlechtesten balanciert; bspw. gibt es einen AVL-Baum der Höhe 5 mit 20 Knoten (linker Teilbaum vollständig der Höhe 4, rechter Fibonacci der Höhe 3) und der externen Pfadlängensumme 97, im Vergleich zu 96 beim Fibonacci-Baum der Höhe 6 mit gleicher Knotenzahl. Diese AVL-Bäume sind aber schwieriger zu charakterisieren als die Fibonacci-Bäume.)
7. Sei ${\displaystyle G}$ die Anzahl der Knoten, die nicht Blätter sind und die zwei Kindbäume gleicher Höhe haben, und ${\displaystyle U}$ die Anzahl der Knoten mit verschieden hohen Kindbäumen, dann ist ${\displaystyle u:={\tfrac {U}{G+U}}\in [0,1]}$ der Anteil der höhenungleichen. (Nur die Fibonacci-Bäume und die anderen dünnsten AVL-Bäume erreichen exakt ${\displaystyle u=1.}$ Dagegen kommen nur die vollständigen Binärbäume (mit ${\displaystyle 2^{h-1}-1}$ inneren Knoten) auf exakt ${\displaystyle u=0.}$ Der Mittelwert über alle möglichen Formen von AVL-Bäumen liegt bei ${\displaystyle u\approx 0{,}3}$.)
   Von folgender Situation sei rekursiv ausgegangen: Bei einer Einfügung habe sich ergeben, dass die Höhe des Teilbaums, in dem die Einfügung stattfand, um 1 zugenommen hat. Ferner sei angenommen, dass es sich um einen rechten Kindbaum handelt (dazu passen die Abbildungen 2 und 3; die gespiegelte Alternative linker Kindbaum sei dem Leser überlassen, sie führt zu denselben Werten). Bei der Überprüfung der Lage im Elterknoten dieses Teilbaums sind die folgenden Fälle zu unterscheiden:

   BF vor Einfügung		Häufigkeit	vorläu- figer BF	Rebalan- cierung erforderlich	BF da- nach	Teilbaum wird höher um	Ebene ober- halb zu überprüfen
   −1	links höher	${\displaystyle {\tfrac {u}{2}}}$	0	Nein		0	Nein
   0	höhengleich	${\displaystyle 1-u}$	+1	Nein		1	Ja
   +1	rechts höher	${\displaystyle {\tfrac {u}{2}}}$	+2	Ja	0	0	Nein
   Tab. 2: Nach dem Einfügen: Die neuen Balance-Faktoren (BF) in Abhängigkeit von den alten

   Die Wahrscheinlichkeit, bei einer Einfügung ausgehend von einer Ebene die nächsthöhere überprüfen zu müssen, ist also ${\displaystyle q:=1-u.}$ Unter der Annahme, dass diese Wahrscheinlichkeiten für alle Ebenen gleich sind, ist die Wahrscheinlichkeit, dass wenigstens ${\displaystyle n}$ Ebenen überprüft werden müssen, gleich ${\displaystyle q^{n}}$ und, dass genau ${\displaystyle n}$ Ebenen überprüft werden müssen, gleich ${\displaystyle q^{n}-q^{n+1}=(1-q)\,q^{n}.}$ Somit summiert sich die Anzahl der zu überprüfenden Ebenen im Mittel auf

   ${\displaystyle {\begin{aligned}(1-q)(q+2q^{2}+3q^{3}+...)\;&=\;q+q^{2}+q^{3}+...\;\\&=\;{\frac {q}{1-q}}\;=\;{\frac {1-u}{1-(1-u)}}\;=\;{\frac {1-u}{u}}.\end{aligned}}}$

   Diese Funktion in ${\displaystyle u}$ fällt monoton von ${\displaystyle +\infty }$ (für ${\displaystyle u=0}$ und vollständige Binärbäume) auf ${\displaystyle 0}$ (für ${\displaystyle u=1}$ und Fibonacci-Bäume). Nach dem Einfügen (mit Korrektur des Balance-Faktors) ist für ${\displaystyle u\in [0{,}25;0{,}5]}$ die mittlere Anzahl der nachträglich zu überprüfenden Ebenen zwischen 3 und 1.
8. Wie beim Einfügen kann der Baum auch beim Löschen von oben nach unten („top-down“) repariert werden. Der Einfachheit halber sei hier nur die Reparatur von unten nach oben („bottom-up“) erläutert. So spielt sie sich auch bei rekursiver Programmierung ab.
9. Über den Anteil der höhenungleichen Knoten seien dieselben Annahmen wie bei der Einfügung gemacht.
   Folgende Situation sei rekursiv angenommen: Nach einer Löschung habe sich die Höhe des Teilbaums, in dem die Löschung stattfand, um 1 vermindert. Ferner handele es sich ohne Beschränkung der Allgemeinheit um einen linken Kindbaum. Bei der Überprüfung der Lage im Elterknoten dieses Teilbaums sind die folgenden Fälle zu unterscheiden:

   BF vor Löschung		Häufigkeit		vorläu- figer BF	Rebalan- cierung erforderlich	BF da- nach	Teilbaum wird nied- riger um	Ebene ober- halb zu überprüfen
   −1	links höher	${\displaystyle {\tfrac {u}{2}}}$		0	Nein		1	Ja
   0	höhengleich	${\displaystyle 1-u}$		+1	Nein		0	Nein
   +1	rechts höher	${\displaystyle {\tfrac {u}{2}}}$	${\displaystyle {\tfrac {u}{2}}(1-u)}$	+2	Ja	+1	0 ⁠1	Nein
   			${\displaystyle {\tfrac {u}{2}}({\tfrac {u}{2}}+{\tfrac {u}{2}})}$			0	1 ⁠2	Ja
   1  Die vorletzte Zeile bezieht sich auf den Fall der Einfachrotation mit gleich hohen Kindern und 2  die letzte auf Rotationen mit nicht gleich hohen Kindern des höheren Knotens Z (s. Abb. 2 und 3), d. h.   Doppelrotation (linkes Kind Y höher) resp. Einfachrotation mit dem rechten Kind t4 höher.
   Tab. 3: Nach dem Löschen: Die neuen Balance-Faktoren (BF) in Abhängigkeit von den alten

   Bei einer Löschung ergibt sich eine Wahrscheinlichkeit ${\displaystyle q:={\tfrac {u}{2}}(1+u)}$ für das Erfordernis, die nächsthöhere Ebene überprüfen zu müssen. Unter der Annahme, dass diese Wahrscheinlichkeiten für alle Ebenen gleich sind, summiert sich die mittlere Anzahl der zu überprüfenden Ebenen auf

   ${\displaystyle {\frac {q}{1-q}}={\frac {u(1+u)}{(2+u)(1-u)}}}$.

   Diese Funktion in ${\displaystyle u}$ wächst monoton von ${\displaystyle 0}$ (für ${\displaystyle u=0}$ und vollständige Binärbäume) auf ${\displaystyle +\infty }$ (für ${\displaystyle u=1}$ und Fibonacci-Bäume). Nach dem Löschen (mit Korrektur des Balance-Faktors) muss für ${\displaystyle u<\Phi -1\approx 0{,}618}$ im Mittel weniger als ungefähr eine weitere Ebene überprüft werden.
10. Man beachte, dass im Fall eines rechtslastigen Y die erste Teilrotation einer Doppelrotation die Situation im betroffenen Teilbaum Y sogar verschlechtert; erst die zweite mit einer Rotationsachse außerhalb bringt die Sache in Ordnung. Somit entspricht, was die Balance-Faktoren angeht, weder die erste noch die zweite Teilrotation einer AVL-#Einfachrotation.
11. 1 Bit, wenn bei den Kindern aufgezeichnet. Wird dem Bit die Bedeutung „Höhensprung oberhalb“ gegeben, dann kann die Höhe im Pfad ohne Kenntnis der Kindesrichtung berechnet werden. Dennoch: es ist für die Modifikationsoperationen geschickter, die 2 Balance-Bits in einem Byte nebeneinander zu haben.
12. Als eine Datenstruktur, die im homogenen Arbeitsspeicher (Hauptspeicher) untergebracht ist, ist der AVL-Baum durch dessen Größe beschränkt, also auch die Höhe des Baums und die Längen der Pfade von Blatt zu Wurzel. Gängig sind Hauptspeicher mit 32 Bit und 64 Bit breiten 8-Bit-Byte-Adressen.
    

    Breite eines Zeigers in Bit	maximale Anzahl adressierbarer Bytes	minimale Knotenlänge (2 Zeiger+1 Byte +Nutzdaten ⁠1)	maxi- male Anzahl Knoten	Knotenzahl des nächstgrößeren Fibonacci-Baums …	… der Höhe
    32	4294967296	2·4+1+3 = 12	3,6·108	433494436	41
    64	18446744073709551616	2·8+1+7 = 24	7,7·1018	1100087778366101930	86
    1  inklusive Schlüssel. Bei mehr Nutzdaten und weniger Hauptspeicher  verringert sich die maximale Knotenzahl und Höhe entsprechend.
    Tab. 4: Maximale Höhe in Abhängigkeit von der Adressierungsbreite

    Fazit: Es ist bei AVL-Bäumen vertretbar, Cursor mit Stapeln bereitzustellen, die so groß sind, dass ein Überlauf nicht auftreten kann.
13. dag für „Directed Acyclic Graph“, deutsch: Gerichteter azyklischer Graph
14. Genau genommen bedarf es einer Kette mit den Gliedern Sperren(Kind) und Entsperren(Elter) bis zum ersten höhenungleichen Knoten, der zunächst gesperrt bleibt, bis er in ein neues Wechselspiel mit den Gliedern Sperren(höhenungleichen Knoten) und Entsperren(Vorfahr) eintritt. (Dabei bedeutet Sperren(Knoten) eigentlich Sperren(Teilbaum). Und: bei einer potentiellen Rebalancierung muss die Sperre sogar eine Ebene höher gehalten werden.) Ist der Einfügepunkt erreicht, kann auch schon mit der Korrektur- und Entsprerrschleife begonnen werden – für maximale Parallelität wieder in einer Kind-Elter-Kette.
    Wenn alle nebenläufigen Mitspieler diese Gerichtetheit des Sperrprotokolls einhalten, kann eine zirkuläre Abhängigkeit und damit eine Verklemmung (deadlock) nicht entstehen.
15. Bei einem vollständigen Binärbaum bedingt eine ${\displaystyle m}$-fache Schleife bestehend aus Einfügung eines zusätzlichen Knotens und Löschung desselben jedes Mal die Anpassung von ${\displaystyle h=\log _{2}(n+1)}$ Balance-Faktoren bis hinauf zur Wurzel und damit einen Aufwand in ${\displaystyle {\mathcal {O}}(m\log n)}$, also amortisiert ${\displaystyle {\mathcal {O}}(\log n)}$.