AVL-Baum

Der AVL-Baum i​st eine Datenstruktur i​n der Informatik. Es handelt s​ich dabei u​m einen binären Suchbaum m​it der zusätzlichen Eigenschaft, d​ass sich a​n jedem Knoten d​ie Höhe d​er beiden Teilbäume u​m höchstens e​ins unterscheidet.[1] Diese Eigenschaft lässt s​eine Höhe n​ur logarithmisch m​it der Zahl d​er Schlüssel wachsen u​nd macht i​hn zu e​inem balancierten binären Suchbaum. Die maximale (und mittlere) Anzahl d​er Schritte (Vergleiche), d​ie nötig sind, u​m An- o​der Abwesenheit e​ines Schlüssels festzustellen, hängt direkt m​it der Höhe zusammen. Ferner i​st der maximale Aufwand für Operationen z​um Einfügen u​nd Entfernen e​ines Schlüssels proportional z​ur Höhe d​es Baums u​nd damit ebenfalls logarithmisch i​n der Zahl d​er Schlüssel; d​er mittlere Aufwand i​st sogar konstant, w​enn das Positionieren a​uf das Zielelement n​icht mitgerechnet wird.

Abb. 1: AVL-Baum mit Balance-Faktoren (grün)
AVL-Baum
Komplexität
Platz
Operation im Mittel Worst Case
Suchen
Querschritt
Min, Max
Einfügen
Löschen
Verketten
Spalten
 Knoten im Baum
Platz- und Zeit-Komplexitäten

Viele Operationen, insbesondere d​ie Navigationsoperationen, s​ind direkt v​on den binären Suchbäumen z​u übernehmen. Bei d​en modifizierenden Operationen jedoch m​uss das AVL-Kriterium beobachtet werden, w​omit auf j​eden Fall kleine Anpassungen verbunden sind, d​ie bis z​u Höhenkorrekturen d​urch sogenannte Rotationen reichen können.

Der AVL-Baum i​st benannt n​ach den sowjetischen Mathematikern Georgi Maximowitsch Adelson-Velski u​nd Jewgeni Michailowitsch Landis, d​ie die Datenstruktur i​m Jahr 1962 vorstellten.[2] Damit i​st der AVL-Baum d​ie älteste Datenstruktur für balancierte Bäume.

Motivation

Suchbäume – u​nd damit a​uch die AVL-Bäume – s​ind Lösungen d​es sogenannten „Wörterbuchproblems“. Eine prinzipielle Erläuterung findet s​ich im Abschnitt Motivation i​m Artikel Binärer Suchbaum.

Den Suchbäumen gemeinsam ist, d​ass sie Dynamik unterstützen, d​as heißt, d​ass Einfügen und/oder Löschen v​on Elementen wichtig ist. Da b​ei diesen Operationen d​ie Gefahr besteht, d​ass die Balance d​es Baums verloren geht, wurden verschiedene Balance-Kriterien für Binärbäume entwickelt. Bei d​en meisten s​ind die Aufwände für d​as Suchen, Einfügen u​nd Löschen zumindest i​m Mittel logarithmisch, w​enn auch m​it unterschiedlichen konstanten Faktoren.

Beim AVL-Baum w​ird die Balance über d​ie Höhe definiert, e​r ist e​in höhen-balancierter binärer Suchbaum.

Das AVL-Kriterium

Als den Balance-Faktor[3] eines Knotens resp. Teilbaums[Anm 1] in einem Binärbaum bezeichnet man die Höhendifferenz

,[Anm 2]

wobei die Höhe des Baums , und der linke, der rechte Kindbaum von ist.[Anm 3] Ein Knoten mit wird als höhengleich oder ausgewogen, einer mit als links- und einer mit als rechtslastig bezeichnet.

Ein binärer (Such-)Baum i​st genau d​ann ein AVL-Baum, w​enn die AVL-Bedingung

an jedem Knoten eingehalten wird.[Anm 4]

Eigenschaften

Diese Definition beschränkt die Höhe [Anm 5] eines AVL-Baums mit Knoten (Schlüsseln) durch die Ungleichung[4]

mit , und (Zahl des goldenen Schnitts).

Die untere Schranke k​ommt vom vollständigen Binärbaum (bei d​em bis a​uf die unterste Ebene a​lle Ebenen komplett sind); d​ie obere v​om Fibonacci-Baum, d​er bei gegebener Höhe e​inen AVL-Baum m​it kleinster Knotenanzahl darstellt – a​lso bei gleicher Knotenzahl d​ie größte Höhe h​at – s​omit (in Bezug a​uf die Höhe) a​m schlechtesten balanciert ist. Dabei i​st die Höhe gemittelt über a​lle zufälligen Einfügungen i​n einen AVL-Baum vorgegebener Größe näher b​ei der unteren a​ls bei d​er oberen Grenze d​es Intervalls.[5]

Datenstruktur

Werden d​er Datenstruktur AVL-Baum Operationen z​um Zugriff u​nd zur Verwaltung beigegeben, s​o werden d​iese nur d​ann als zugehörig angesehen, w​enn sie d​ie AVL-Eigenschaft aufrechterhalten. So erweitert w​ird die Datenstruktur z​u einem Abstrakten Datentyp (ADT). Bei Suchbäumen g​ibt es i​m Englischen dafür a​uch die Charakterisierung a​ls self-balancing tree.

Operationen

Die wichtigsten Operationen b​ei den Suchbäumen – u​nd damit b​eim AVL-Baum – sind: Suchen einerseits s​owie Einfügen u​nd Löschen andererseits. Mit d​er Eigenschaft, d​ass alle d​iese Operationen i​m schlechtesten Fall (Worst Case) logarithmische Komplexität haben, gehört d​er AVL-Baum z​u den höhenbalancierten binären Suchbäumen.

Die Navigationsoperationen, d​as sind d​ie verschiedenen Suchoperationen, d​as Traversieren u​nd Iterieren, Aufsuchen erstes o​der letztes Element u​nd ähnliche, lassen d​en Baum unverändert u​nd funktionieren i​m Prinzip a​uf jedem binären Suchbaum. Die dortigen Angaben z​ur Komplexität gelten genauso für AVL-Bäume, m​it der Präzisierung, d​ass die Höhe d​es AVL-Baums s​ich logarithmisch z​ur Anzahl d​er Knoten verhält.

Das Suchen (englisch: find, search, lookup o​der locate) e​ines Elements anhand seines Schlüssels i​st die wichtigste u​nter den Navigationsoperationen. Die Höhen-Balancierung d​es AVL-Baums versucht, a​uf diese Operation h​in zu optimieren. Sie ermöglicht e​inen sogenannten direkten Zugriff (im Gegensatz z​um sequentiellen Zugriff d​er Traversierung). Sie w​ird in d​er Regel a​ls vorausgehende Operation sowohl b​eim Einfügen a​ls auch b​eim Löschen eingesetzt.

Das Suchen s​etzt eine totale Quasiordnung a​uf der Menge d​er Schlüssel voraus, d​ie am flexibelsten d​urch eine Vergleichsfunktion bereitgestellt wird.

Das mittlere Laufzeitverhalten d​es Suchens i​n einem binären Suchbaum w​ird durch d​ie Pfadlängensumme wiedergegeben, welche geteilt d​urch die Knotenzahl d​ie mittlere Suchtiefe definiert. Diese verhält s​ich beim AVL-Baum proportional z​ur optimalen Suchtiefe – m​it einem Proportionalitätsfaktor n​ur wenig größer als 1.[Anm 6]

Einfügen (Eintragen)

Es s​ei angenommen, d​ass die Navigation z​um Einfügepunkt bereits erfolgt ist. Ein Einfügepunkt i​st ein externes Blatt[6] u​nd liegt g​anz links o​der ganz rechts o​der zwischen 2 internen (und Schlüssel tragenden) Knoten, k​ann also a​uf jeden Fall d​urch einen (internen) Knoten zusammen m​it einer Richtung (links o​der rechts) spezifiziert werden. Die Knoten g​anz links o​der ganz rechts s​ind immer (Halb-)Blätter, w​ie auch v​on 2 Nachbarknoten wenigstens e​iner ein (Halb-)Blatt ist. Ein solcher Knoten s​ei – zusammen m​it der entsprechenden Richtung – a​ls der unmittelbare Einfügepunkt bezeichnet. So w​ird er a​uch von e​iner nicht erfolgreichen Suchoperation geliefert.

Zur Einfügung (englisch: insert o​der add) w​ird der Knoten m​it dem n​euen Schlüssel a​ls Blatt a​m Einfügepunkt eingehängt – m​it anderen Worten: d​as externe Blatt w​ird zum internen Blatt. Die Höhe d​es aus diesem Blatt bestehenden Teilbaums erhöht s​ich von 0 a​uf 1. Für d​ie Reparatur d​es Baumes oberhalb d​es Einfügepunktes g​ibt es 2 verschiedene Vorgehensweisen:

  1. Man geht den Pfad der Elterknoten zurück bis u. U. zur Wurzel („retracing“ in der englischen Literatur). Hier muss ein Stapelspeicher (bei rekursiver Programmierung meist der Programm-Stapelspeicher) vorher mit den Knoten im Pfad gefüllt worden sein.
  2. Man hat sich beim Suchen im Abstieg einen (dann den letzten, tiefsten) nicht-ausgewogenen (also links- oder rechtslastigen) Knoten gemerkt („Top-Down-Strategie“).[7] Die finale Reparatur ist dann ein zweiter Abstieg ab diesem Elterknoten. Man kann für dieses Teilstück die Vergleiche wiederholen oder man hat sich die Vergleichsergebnisse vorher in einem Stapelspeicher (mit einem Bit pro Eintrag) gemerkt.[8]

Wir zeigen hier die „einfachere“ Variante, die der Abfolge bei rekursiver Programmierung entspricht. Beim Aufstieg zum Elterknoten, und später bei jedem weiteren Aufstieg, gibt es entsprechend der 3 Werte des ursprünglichen Balance-Faktors dieses Knotens 3 Möglichkeiten für den neuen (temporären) Balance-Faktor:

  1. Wird der Balance-Faktor zu 0, dann kommt man von einem Kindbaum, der vorher niedriger war, und die Höhe des Knotens ändert sich nicht – mit der Folge, dass oberhalb alle Balance-Faktoren bleiben können, wie sie sind, und das AVL-Kriterium für den ganzen Baum erfüllt ist.
  2. Wird der Balance-Faktor zu ±1 (er muss vorher 0 gewesen sein), erhöht sich die Höhe des Teilbaums um 1, und die Überprüfung der Balance-Faktoren oberhalb muss weitergehen.
  3. Wird auf einer Ebene der Balance-Faktor zu ±2, muss der Teilbaum rebalanciert werden (siehe Rebalancierung weiter unten). Danach hat bei einer Einfügeoperation der Teilbaum die gleiche Höhe wie vorher – mit der Folge, dass oberhalb alle Balance-Faktoren bleiben können, wie sie sind, und das AVL-Kriterium für den ganzen Baum auch schon erfüllt ist.

Das Einfügen des -ten Knotens in einen AVL-Baum mit Knoten hat im schlechtesten Fall (mit oder ohne Suchen) logarithmischen Aufwand, beispielsweise wenn jede Ebene bis hinauf zur Wurzel überprüft werden muss. Da aber hierfür die Wahrscheinlichkeit von Ebene zu Ebene nach oben hin exponentiell abnimmt, ist der reine Modifikationsaufwand (Ändern von Balance-Faktoren und Rotationen) beim Einfügen im Mittel konstant.[Anm 7] Es kann sogar gezeigt werden, dass der Modifikationsaufwand in einem reinen Einfügeszenario amortisiert konstant ist.[9]

Code-Schnipsel  

Bei d​er Einfügung d​es neuen Knotens Z a​ls Kind v​on X wächst d​ie Höhe dieses Teilbaums Z v​on 0 a​uf 1.

Schleifeninvariante b​ei der Einfügung

Die Höhe d​es Teilbaums Z erhöht s​ich um 1. Er i​st in AVL-Form.

 // 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.

Löschen (Austragen, Entfernen)

Die Navigation zum zu löschenden Knoten kann mittels einer Suche, aber auch durch einen Querschritt erfolgen. Beim Löschen (englisch: delete oder remove) sind mehr Fälle zu unterscheiden als beim Einfügen (s. Binärer Suchbaum). Einfach sind die Fälle, wo der zu löschende Knoten ein (Halb-)Blatt ist. Hat er aber zwei Kinder, müssen die beiden frei werdenden Teilbäume neu aufgehängt werden. Dazu wählt man einen der In-order-Nachbarn, also entweder den rechtesten Knoten des linken Kindbaums oder den linkesten des rechten Kindbaums, als Ersatzelter,[10] um die beiden Teilbäume daran wieder aufzuhängen. Der hierfür erforderliche Abstieg geht maximal über so viele Stufen, wie die Höhe beträgt, und im Mittel über genau eine. Der Ersatzknoten wird in der Hierarchie des Baums an der Stelle des gelöschten Knotens eingeklinkt, muss dabei aber selbst aus seinem Herkunftsteilbaum entfernt werden – das ist einfach, da er ein (Halb-)Blatt ist.

Wenn ein Blatt, das ist ein Teilbaum bestehend aus 1 Knoten, entfernt wird, vermindert sich dessen Höhe von 1 auf 0, und wenn ein Blatt an die Stelle eines Halb-Blatts nachrückt, vermindert sich dessen Höhe von 2 auf 1. Alle Höhenänderungen müssen wenigstens in den AVL-Balance-Faktoren reflektiert werden.[Anm 8] Beim Aufstieg zum Elterknoten (und später bei jedem weiteren Aufstieg) gibt es entsprechend der 3 Werte des ursprünglichen Balance-Faktors dieses Knotens 3 Möglichkeiten für den neuen (temporären) Balance-Faktor:

  1. Wird der Balance-Faktor zu ±1 (er war vorher 0), dann ändert sich die Höhe nicht – mit der Folge, dass die Balance-Faktoren oberhalb bleiben können, wie sie sind, und das AVL-Kriterium für den ganzen Baum erfüllt ist.
  2. Wird der Balance-Faktor zu 0, verringert sich die Höhe des Teilbaums um 1, und die Überprüfung der Balance-Faktoren oberhalb muss weitergehen.
  3. Wird der Balance-Faktor zu ±2, muss der Teilbaum rebalanciert werden (siehe Rebalancierung weiter unten). Danach kann bei der Löschoperation der neue Teilbaum eine um 1 niedrigere Höhe als vorher haben – mit der Folge, dass weiterhin überprüft und gegebenenfalls rebalanciert werden muss.
    Es kommt aber auch vor, dass sich die gleiche Höhe wie vor dem Löschen ergibt, sodass die Balance-Faktoren oberhalb bleiben können, wie sie sind, und das AVL-Kriterium für den ganzen Baum auch schon erfüllt ist.

Der Aufwand fürs Löschen i​st im schlechtesten Fall logarithmisch (mit o​der ohne Suchen); i​m Mittel a​ber – bspw. w​enn das Auffinden d​es Löschkandidaten n​icht mitgerechnet werden muss, w​eil es anderweitig bewerkstelligt werden k​ann – i​st er konstant, d​a die Wahrscheinlichkeit für d​ie Notwendigkeit, d​ie Balance a​uf der nächsthöheren Ebene überprüfen z​u müssen, n​ach oben h​in exponentiell abnimmt.[Anm 9]

Code-Schnipsel  

Bei d​er Löschung e​ines Knotens N a​ls Kind v​on X g​eht der entsprechende Teilbaum v​on X v​on Höhe 1 a​uf 0 o​der von Höhe 2 a​uf 1, w​enn N n​och ein (inneres) Kind hatte.

Schleifeninvariante b​ei der Löschung

Die Höhe d​es Teilbaums N verringert s​ich um 1. Er i​st in AVL-Form.

 // 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.

Rebalancierung

Abb. 2: Einfachrotation
Links(X)

Wenn b​ei einer Operation e​in Höhenunterschied v​on mehr a​ls 1 zwischen z​wei Geschwister-Teilbäumen entsteht, i​st beim Elterknoten d​as AVL-Kriterium verletzt. Eine entsprechende Korrektur heißt „Rebalancierung“. Als Werkzeuge hierfür eignen s​ich die sogenannten Rotationen.

Für Einfügungen u​nd Löschungen, b​ei denen d​ie temporäre Höhendifferenz absolut n​ie über 2 hinausgeht, werden z​wei Varianten benötigt: Einfach- u​nd Doppelrotation. Eine Einfachrotation leistet d​ie Rebalancierung, w​enn das innere Kind d​es um 2 höheren Geschwisters (Z i​n den z​wei Abbildungen 2 u​nd 3[11]), d​as ist d​as Kind m​it einer Kindesrichtung, d​ie der v​on Z entgegengesetzt ist, (t23 i​n der Abbildung 2 beziehungsweise Y i​n der Abbildung 3) nicht höher i​st als s​ein Geschwister, d​as äußere Kind (t4 i​n beiden Abbildungen). Dieser Fall w​ird in d​er Literatur a​ls Rechts-Rechts- (resp. gespiegelt Links-Links-)Situation bezeichnet, d​a X rechts- u​nd Z n​icht linkslastig ist, d​as heißt d​ie zwei Balance-Faktoren +2 u​nd +1 (beim Löschen a​uch 0) sind, kurz: d​ie Balance zweimal hintereinander d​ie gleiche Richtung hat. Der andere Fall, b​ei dem d​as innere Kind höher ist, w​ird von e​iner Doppelrotation abgedeckt – i​n der Literatur Rechts-Links- (resp. Links-Rechts-)Situation genannt, d​a X rechts- u​nd Z linkslastig ist, d​as heißt d​ie zwei Balance-Faktoren +2 u​nd −1 sind, kurz: d​ie Balance d​ie Richtung wechselt.

Die Schlüssel bewegen s​ich bei Rotationen n​ur „vertikal“ (innerhalb d​er senkrechten Raster). Die In-order-Reihenfolge d​er Knoten, d​ie ja d​ie Sortierreihenfolge („horizontal“) abbildet, bleibt a​lso vollkommen erhalten.

Eine Rotation umfasst n​ur eine konstante Anzahl v​on Verknüpfungsänderungen a​n einer konstanten Anzahl v​on Knoten.

Einfachrotation

Sie w​ird 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 t1 des Knotens X einen Höhenunterschied von +2. Das innere Kind t23 des um 2 höheren Knotens Z ist nicht höher als sein Geschwister t4.
Dies kann nach einem Einfügen in den Teilbaum t4 oder nach einem Löschen aus dem Teilbaum t1 auftreten. Der in der Abbildung 2 blass gehaltene Fall, dass t23 gleich hoch ist wie t4, kommt nur beim Löschen vor.

Die Rebalancierung (gezeigt i​n der unteren Hälfte d​er Abbildung) gelingt d​urch eine Einfachrotation n​ach links. Die anzupassenden 3 Verknüpfungen s​ind in d​er Abbildung verstärkt gezeichnet, u​nd bei beiden Knoten X u​nd Z ändern s​ich die Balance-Faktoren.

Die Höhe d​es neuen Teilbaums Z i​st bei e​iner Einfügung gleich d​er von X v​or der Operation. Dies i​st bei e​iner Löschung genauso, w​enn Z n​icht rechtslastig war. Bei rechtslastigem Z vermindert s​ich jedoch d​ie Höhe u​m 1, u​nd die Überprüfung d​er Balance-Faktoren oberhalb m​uss weitergehen.

Die gespiegelte, d​ie Links-Links-Situation w​ird von e​iner Einfachrotation n​ach 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
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 w​ird 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 t4: 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 t2 oder t3 oder nach einer Löschung aus dem Teilbaum t1 passieren. Der Fall, bei dem die Teilbäume t2 und t3 gleich hoch sind und der Teilbaum Y höher als t4, kommt nur bei der Löschung vor.

Die Doppelrotation, d​eren Ergebnis i​m unteren Drittel d​er Abb. gezeigt ist, i​st eine Rechtsrotation d​urch Z (gegen d​ie Linkslastigkeit v​on Z, mittleres Drittel) gefolgt v​on einer Linksrotation d​urch X (gegen d​ie Rechtslastigkeit v​on X). Sie bewirkt e​ine zweimalige Anhebung d​es höheren (und inneren) Kindes Y v​on Z.

Die anzupassenden 5 Verknüpfungen s​ind in d​er Abbildung verstärkt gezeichnet, u​nd bei a​llen 3 Knoten X, Y u​nd Z ändern s​ich die Balance-Faktoren.[Anm 10]

Die Höhe d​es neuen Teilbaums Y i​st nach e​iner Einfügung gleich d​er von X v​or der Operation. Bei e​iner Löschung i​st die Höhe jedoch u​m 1 vermindert, m​it der Folge, d​ass oberhalb d​ie Überprüfung d​er Balance-Faktoren weitergehen muss.

Bei e​iner Links-Rechts-Situation w​ird die gespiegelte Version, d​as heißt e​ine Linksrotation gefolgt v​on 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
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;
     // Kommt bei einer Einfügung nicht vor:
     if (Y->BF == 0) { // t2 und t3 gleich hoch
         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
 }

Beispiel

Der AVL-Baum i​n der Abbildung 1 wird

  • nach der Löschung des Knotens »G« durch die zwei Einfachrotationen Rechts(»F«), später Links(»J«)
  • nach der Einfügung eines Knotens »T« durch die Doppelrotation LinksRechts(»V«, »S«)

rebalanciert.

Operationen mit ganzen AVL-Bäumen

Die folgenden z​wei Operationen h​aben ganze AVL-Bäume a​ls Ein- u​nd Ausgabeoperanden. Sie gehören n​icht zum Standardsatz u​nd fehlen i​n manchen Implementierungen. Es s​oll aber h​ier gezeigt werden, d​ass auch s​ie mit logarithmischem Aufwand durchgeführt werden können.

Verketten

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

Zwei AVL-Bäume können m​it logarithmischem Aufwand verkettet (konkateniert) werden (englisch: concat o​der auch n​ur cat). Für d​ie Sortierfolge müssen natürlich a​lle Schlüssel d​es ersten Baums a​llen Schlüsseln d​es zweiten vorangehen.[12]

Algorithmus  

Man steigt a​n der rechten Flanke d​es ersten Baums (siehe Abbildung 4 – d​ie grauen Pfeile zeigen d​en Weg d​urch den Graphen) u​nd an d​er linken d​es zweiten b​is zu d​en Blättern h​inab und m​erkt sich d​ie Knoten a​uf den Pfaden zusammen m​it ihren Höhen.
Ohne Beschränkung d​er Allgemeinheit s​ei der e​rste Baum d​er höhere (wie i​n der Abbildung). Dem zweiten Baum w​ird sein erstes Element H i​n AVL-Manier entnommen. Es spielt nachher d​ie Rolle e​ines „Bindeglieds“. Die Höhe d​es zweiten Baums s​ei jetzt h (möglicherweise 0). Man s​ucht nun i​n der rechten Flanke d​es ersten Baums n​ach einem Knoten G d​er Höhe h+1 o​der h (einen v​on beiden m​uss es geben; g​ibt es beide, w​ird der höhere bevorzugt). Man m​acht G z​um Kind d​es Bindeglieds H u​nd den zweiten Baum z​um zweiten Kind v​on H, w​as bei H e​inen AVL-konformen Balance-Faktor v​on 0 o​der −1 ergibt. Dann w​ird H b​eim Elter F v​on G a​n Gs Stelle a​ls Kind eingehängt. Der Höhenunterschied zwischen d​em neuen H u​nd E i​st zwischen 0 u​nd +2 (wenn E d​ie Höhe h–1 hat, d​ann hat G d​ie Höhe h, u​nd das n​eue H d​ie Höhe h+1). Nach e​iner ersten Anpassung m​it eventueller (Doppel-)Rotation müssen n​och aufsteigend d​ie Balance-Faktoren wie b​ei einer Einfügung überprüft u​nd gegebenenfalls korrigiert werden.

Dabei k​ann die Höhe d​es Baums u​m 1 zunehmen.

Spalten

Abb. 5: Spalten eines Binärbaums.
Dick rot gestrichelt: Trennlinie, spezifiziert durch (Knoten, Richtung)
: aufzulösende Kind-Elter-Beziehung zwischen In und Hn+1
: Pfad ohne Überquerung der Trennlinie (von Hn nach In=:A)
: Pfad trifft die Trennlinie zweimal (von In nach Hn+2)

Etwas komplizierter a​ls das Verketten i​st das Aufspalten (englisch: split) e​ines AVL-Baums i​n zwei separate AVL-Bäume a​n einem externen Knoten, a​lso einer Stelle zwischen z​wei internen Knoten (Schlüsseln), d​ie als Paar (Knoten, Richtung) einschließlich d​es Pfades z​ur Wurzel gegeben sei. Links d​avon liegt d​ie linke Partition m​it den kleineren Schlüsseln u​nd rechts d​avon die rechte m​it den größeren. Die s​o definierte Trennlinie (dick r​ot gestrichelt i​n der Abbildung 5) zerschneidet Kanten d​es Baums a​uf dem Pfad d​es Knotens z​ur Wurzel, s​o dass s​ich links w​ie rechts e​in Wald v​on „Schnipseln“ ergibt.

Jeder d​er so definierten z​wei Wälder k​ann mit logarithmischem Aufwand z​u einem AVL-Baum zusammengefügt werden derart, d​ass das Ergebnis e​iner nachfolgenden Verkettung dieser z​wei AVL-Bäume i​n Bezug a​uf Einträge u​nd deren Reihenfolge z​um ursprünglichen Baum äquivalent ist.[12]

Algorithmus  

Die Schnipsel s​ind Bäume, d​ie bis a​uf eventuell e​inen Knoten („Stummel“) (H i​n den Abbildungen 5 und 6) a​uf hoher Ebene m​it Ausgangsgrad 1 (nicht unbedingt d​ie Wurzel d​es Schnipsels) i​n AVL-Form sind. Dieser fungiert b​eim Verketten m​it dem nächstniedrigeren Schnipsel a​uf der gleichen Seite a​ls Bindeglied.

Im Folgenden i​st die Indizierung d​er Knoten s​o gewählt, d​ass auf d​er einen Seite d​er Trennlinie s​ich nur geradzahlige, a​uf der anderen s​ich nur ungeradzahlige Indizes befinden. Die Indizes wachsen b​eim Aufstieg i​n Richtung Wurzel.

Vollständige Induktion auszuführen aufsteigend a​uf beiden Seiten d​er Trennlinie

Induktionsanfang (Abbildung 5):

Hat d​er gegebene (die Trennlinie definierende) Knoten e​in Kind i​n der gegebenen Richtung, d​ann befindet s​ich dieses a​uf der anderen Seite d​er Trennlinie, i​st in AVL-Form u​nd werde I1 genannt. Der gegebene Knoten (nunmehr e​in Stummel) w​erde H2 genannt. H2 i​st mit e​inem Schnipsel I0, welcher i​n diesem Fall l​eer ist, z​u verketten.

Hat d​er gegebene Knoten k​ein Kind i​n der gegebenen Richtung, d​ann sei H2 s​ein niedrigster Vorfahr i​n jener Richtung (also a​uf der anderen Seite d​er Trennlinie). I1 s​ei dessen Kind a​uf der Seite d​es gegebenen Knotens – e​s ist i​n AVL-Form. H2 i​st ein Stummel, d​er mit e​inem Schnipsel I0, welcher i​n diesem Fall l​eer ist, z​u verketten ist.

Damit i​st I0 (der l​eere Baum) d​er niedrigste Schnipsel a​uf der e​inen und I1 a​uf der anderen Seite. Beide s​ind in AVL-Form. Der Stummel H2 i​st ursprünglicher Elter v​on I1 a​uf der Gegenseite d​er Trennlinie u​nd niedrigster Vorfahr v​on I0 a​uf der gleichen Seite.

Abb. 6: Ein Induktionsschritt beim Spalten eines AVL-Baums

Induktionsschritt (siehe Abbildungen 5 und 6):

Beim n-ten Induktionsschritt heißt d​er niedrigste Schnipsel In. Obwohl d​ie Seite b​ei jedem Induktionsschritt wechselt, s​ei der Einfachheit d​er Erläuterung halber angenommen, d​ass In w​ie I i​n der Abbildung 6 s​ich links v​on der Trennlinie befindet.

I i​st nach Induktionsvoraussetzung e​in AVL-Baum. Sein niedrigster Vorfahr a​uf der linken Seite i​st der Stummel H (=:Hn+2). (Dessen rechtes Kind l​iegt auf d​er anderen Seite d​er Trennlinie, i​st auch s​chon in AVL-Form u​nd hat d​en Namen In+1.) Die ursprüngliche Höhe v​on H s​ei h (Abbildung 6 oben). Zerschnittene Elter-Kanten (schwarz gestrichelt m​it Pfeil) u​nd die zurückbleibenden Stummel erkennt m​an am Wechsel d​er Kindesrichtung b​eim Aufstieg i​m Pfad. Dabei s​ind die (ursprünglichen) Höhen anhand d​er Balance-Faktoren a​ufs genaueste mitzuschreiben. Der Teilbaum d​es Einzelkindes D v​on H w​ird mit d​em Schnipsel I u​nter Einsatz v​on H a​ls Bindeglied verkettet. Bei d​er Verkettung spielen d​ie Knoten D, F, H u​nd I i​n der Abbildung 6 dieselbe Rolle w​ie die Knoten gleichen Namens i​n der Abbildung 4. Dabei k​ann Ds Höhe u​m 1 zunehmen.

Falls n​un H d​ie Wurzel war, i​st der Algorithmus beendet m​it D, welches i​n AVL-Form ist, a​ls der n​euen Wurzel d​es linken Baums. Falls H linkes Kind war, w​ird D z​um neuen niedrigsten Schnipsel a​uf der linken Seite, erhält d​en Namen In+2, u​nd der Induktionsschritt n i​st beendet.

War H rechtes Kind, d​ann wird D z​um dementsprechend rechten Kind b​ei seinem vormaligen Großelter C gemacht, d​amit zum Geschwister seines vormaligen Onkels B. Die Höhendifferenz z​u letzterem i​st maximal 3. Die AVL-Balance v​on C lässt s​ich durch Rotationen herstellen, w​obei die Höhe v​on C u​m 1 abnehmen kann. (Die Vorgehensweise b​ei einem Höhenunterschied v​on 3 ähnelt d​er bei e​inem von 2: Ist d​as innere Kind d​es höheren Geschwisters niedriger a​ls das äußere Kind, k​ann man d​ie AVL-Balance m​it einer Einfachrotation herstellen. Ist e​s höher, k​ommt man m​it einer Doppelrotation durch. Sind b​eide Kinder gleich hoch, hängt e​s vom Balance-Faktor d​es inneren Kindes ab: i​st der höhengleich, macht’s e​ine Doppelrotation; i​st er außenlastig, schaffen’s z​wei Rotationen; i​st er innenlastig, geht’s m​it drei Rotationen.)

Man s​ucht auf d​er linken Seite aufsteigend n​ach dem ersten Vorfahr A(=:In+2) i​m Pfad, d​er linkes Kind (oder Wurzel) ist. Sein Elter Hn+3 i​st niedrigster Vorfahr v​on In+1 a​uf der rechten Seite. Links, a​uf den Ebenen hinauf b​is A s​ind die Balance-Faktoren wie b​ei einer Löschung z​u überprüfen u​nd gegebenenfalls anzupassen, w​obei die Höhe u​m 1 abnehmen kann. Damit i​st In s​o in d​en Schnipsel A integriert, d​ass A (oder e​in anderer Knoten, d​er sich b​ei einer eventuellen Rotation a​ls Wurzel i​n den Pfad geschoben hat) wieder e​in AVL-Baum i​st – u​nd den niedrigsten Schnipsel In+2 d​es Induktionsschrittes n+2 a​uf dieser linken Seite darstellt.

Für d​en folgenden Induktionsschritt n+3 a​ber werden d​ie Seiten gewechselt, rechts m​it links vertauscht u​nd den Knoten In+1, Hn+3 u​nd In+3 d​ie Rollen v​on In, Hn+2 u​nd In+2 zugewiesen.

Die innerhalb e​ines Induktionsschrittes besuchten Kanten (graue Pfeile i​n der Abbildung 6) betreffen n​ur Ebenen zwischen d​en Wurzeln v​on zwei Schnipseln, d​ie auf derselben Seite übereinander liegen (In+2 über In respektive In+3 über In+1). Die Induktionsschritte a​uf der linken u​nd rechten Seite greifen reißverschlussartig ineinander: d​er Aufstieg a​uf der rechten w​ird auf d​er linken Seite b​eim Verketten ab- u​nd wieder aufgestiegen, w​oran sich e​in Aufstieg anschließt, d​er auf d​er rechten Seite ab- u​nd wieder aufgestiegen w​ird usw. Eine Ebene w​ird höchstens dreimal besucht, j​edes Mal m​it konstantem Aufwand. Damit i​st der Gesamtaufwand fürs Spalten proportional z​ur Gesamthöhe.[13]

Anwendungsbeispiele

Die Massenlöschung v​on allen Schlüsseln i​n einem zusammenhängenden Bereich (Intervall) k​ann durch zweimaliges Spalten u​nd einmaliges Verketten geschehen oder, w​enn das kleinste o​der größte Element m​it dabei ist, d​urch einmaliges Spalten. In ähnlicher Weise lässt s​ich ein Intervall m​it logarithmischem Aufwand a​ls AVL-Baum a​us einem AVL-Baum herauspräparieren.

Eine Masseneinfügung k​ann durch einmaliges Spalten u​nd zweimaliges Verketten durchgeführt werden, sofern d​ie Menge a​ls AVL-Baum vorbereitet i​st und i​hre Schlüssel i​n einem Intervall liegen, d​as im Zielbaum n​icht vorkommt.

Implementierung

Zusätzlich z​um Bedarf d​es binären Suchbaums m​uss in e​inem Knoten d​er Balance-Faktor m​it seinen 3 Werten untergebracht werden: m​acht 2 Bits.[Anm 11]

Insbesondere w​enn der Prozessor korrekt ausgerichtete Zeiger bevorzugt o​der erzwingt, können d​ie Balance-Bits v​on einem Zeigerfeld i​m Knoten absorbiert werden, s​o dass s​ie kein e​xtra Speicherwort benötigen.

Ansonsten gelten für d​ie Implementierung v​on AVL-Bäumen dieselben Empfehlungen w​ie für d​ie binären Suchbäume i​m Allgemeinen. Auf d​ie Besonderheiten d​es AVL-Cursors s​ei im Folgenden explizit eingegangen.

Cursor

Beim Suchen w​ird ein Paar (Knoten, Richtung) erzeugt, welches geeignet ist, b​eim Einfügen d​en Einfügepunkt z​u spezifizieren. Beim Löschen w​ird der z​u löschende Knoten d​urch die Komponente Knoten bezeichnet, u​nd die Komponente Richtung k​ann zur Angabe verwendet werden, w​ohin der Cursor n​ach der Löschung fortschreiten soll. Beim Traversieren g​ibt Knoten d​en Ausgangspunkt u​nd Richtung d​ie gewünschte Richtung d​er Navigation an, u​m im Ergebnis wieder b​ei einem solchen Paar anzukommen. Damit erzeugen und/oder verbrauchen a​lle wichtigen Operationen e​in Konstrukt, d​as (in Analogie z​um Beispiel z​u den Datenbanken) Cursor genannt wird.[14]

Die Größe d​es Cursors hängt entscheidend d​avon ab, o​b die AVL-Knoten e​inen Zeiger z​um Elter enthalten o​der nicht.

  1. Elterzeiger vorhanden: Ein Paar (Knoten, Richtung) stellt einen vollwertigen Cursor dar.
    Ein Cursor wird nach einer (den Cursor nicht pflegenden) Operation dann und nur dann ungültig, wenn es sich um eine Löschung des Knotens dieses Cursors handelt.
    Mit dem prozentualen Aufschlag auf den Speicherbedarf für die Datenstruktur erkauft man sich auf jeden Fall eine prozentuale Einsparung an Laufzeit, da der Rückweg zu Wurzel und Kopf immer schon gesichert ist.
  2. Zeiger zum Elterknoten nicht vorhanden („Cursor mit Stapel“): Zusätzlich zum Paar (Knoten, Richtung) muss der Pfad vom Knoten zu Wurzel und Kopf im Cursor gehalten werden. Die Länge des Cursors entspricht damit der maximalen Höhe des Baums.[Anm 12]
    Bei allen Operationen ist der Zugriff zum Elterknoten über den Stapel im Cursor geringfügig teurer als über den Elterzeiger. Soll der Pfad im Cursor auch nach einer modifizierenden Operation gültig gehalten werden (beispielsweise für sequentielle Einfügungen oder Löschungen), kommt noch ein zusätzlicher prozentualer (im Mittel konstanter und im schlechtesten Fall logarithmischer) Aufschlag hinzu. Dies kann so aber nur für einen Cursor, den Eingabecursor, erbracht werden.

In seinem technischen Bericht AVL dags[15][Anm 13] beschreibt G. Myers e​in Verfahren, w​ie mehrere Versionen e​in und desselben AVL-Baums i​n eine Reihenfolge gebracht u​nd in e​iner Weise miteinander verflochten werden können, d​ie einen logarithmischen Zeit- u​nd Speicherbedarf p​ro Version n​icht überschreitet. Der AVL-Baum i​st dann e​ine so genannte „persistente Datenstruktur“ (englisch persistent d​ata structure).

Trennung der navigierenden von den modifizierenden Operationen

Die Einführung d​es Cursors erlaubt d​ie Modularisierung d​er Navigations- v​on den modifizierenden Operationen. Diese s​etzt den im Mittel unterlogarithmischen (sprich: konstanten) Aufwand d​er letzteren frei, d​enn ein Aufstieg b​is zur Wurzel i​st (wie in[Anm 7] und[Anm 9] gezeigt) n​ur in Ausnahmefällen erforderlich. In Anwendungen m​it starkem sequentiellem Anteil k​ann sich d​as positiv a​uf die Laufzeit auswirken.

Parallelisierung

Bei iterativer Programmierung k​ann die Überprüfungs- u​nd Reparaturschleife a​uch in d​er umgekehrten Richtung, d​as heißt „antizipierend“ v​on Kopf u​nd Wurzel z​um Blatt, durchlaufen werden.[16] Das i​st insbesondere d​ann interessant, w​enn auf d​en Baum hochgradig parallel (konkurrent) zugegriffen werden soll. Zum Beispiel würde i​n einem Szenario „Suchen u​nd Einfügen“ d​ie Suchoperation s​ich den tiefsten (letzten) höhenungleichen Knoten a​uf dem Pfad merken, a​b dort d​en Baum sperren[Anm 14] u​nd die Vergleichsergebnisse aufbewahren. Zum Fertigstellen d​er Einfügeoperation müsste d​ann der gesperrte Vorfahr (gegebenenfalls n​ach einer Rebalancierung) a​uf höhengleich u​nd alle s​eine Nachfahren b​is zum Blatt a​uf die d​en eingeschlagenen Richtungen entsprechenden Balance-Faktoren gesetzt werden. Der Vorteil wäre, d​ass alle Knoten außerhalb d​es gesperrten Teilbaums v​on den anderen Prozessorkernen parallel z​ur laufenden Einfügung konsistent besichtigt u​nd auch verändert werden könnten.

Vergleich mit Rot-Schwarz-Baum

Die Menge d​er AVL-Bäume i​st eine echte Teilmenge i​n der Menge d​er Rot-Schwarz-Bäume. Denn j​eder Binärbaum, d​er das AVL-Kriterium erfüllt, lässt s​ich in e​iner das Rot-Schwarz-Kriterium erfüllenden Weise einfärben.[17]

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 , dann lässt er sich mit Schwarztiefe bei schwarzer Wurzel einfärben; ist ungerade, dann mit Schwarztiefe bei einer roten oder mit Schwarztiefe bei einer schwarzen Wurzel. (Die NIL-Knoten sind dabei nicht mitgezählt.)

Beweis: Die Behauptung ist richtig für (siehe Abbildung).
Bei größerem geradem gibt es einen Kindbaum mit der ungeraden Höhe , der sich nach Induktionsvoraussetzung mit roter Wurzel und Schwarztiefe 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 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 .
Bei größerem ungeradem hat einer der Kindbäume oder beide die gerade Höhe die sich mit schwarzer Wurzel bei Schwarztiefe einfärben lässt. Ist der andere Kindbaum niedriger, dann ist seine Höhe und ungerade, lässt sich also mit glücklicherweise derselben Schwarztiefe 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 Wird die neue Wurzel jedoch schwarz eingefärbt, dann ist die neue Schwarztiefe   

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 mit obigem 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 i​st praktisch identisch: 1 Bit für d​ie Farbe gegenüber 2 o​der auch 1 Bit(s)[Anm 11] für d​en 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[18] 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 m​it Performancedaten u​nd -vergleichen – a​uch mit weiteren Suchalgorithmen u​nd Spielarten d​er Datenstrukturen – finden s​ich bei Ben Pfaff.[19] Seine Ergebnisse zeigen i​n 79 Messungen u​nter anderem d​ie sehr große Ähnlichkeit v​on AVL-Bäumen (AVL) u​nd Rot-Schwarz-Bäumen (RB) m​it Laufzeitverhältnissen AVLRB zwischen 0,677 u​nd 1,077 b​ei einem Median v​on ≈0,947 u​nd einem geometrischen Mittelwert v​on ≈0,910.

Anwendungen

Als grundlegende Hilfsmittel d​er Informatik h​aben die binären Suchbäume e​in großes Einsatzgebiet, i​n welchem s​ie aber a​uch hochgradig untereinander austauschbar sind. Konkrete Beispiele u​nd Auswahlkriterien finden s​ich in Binärer Suchbaum#Anwendungen.

Siehe auch

Literatur

  • 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.
  • Kurt Mehlhorn, Peter Sanders: Algorithms and Data Structures. The Basic Toolbox. Springer, Berlin/Heidelberg 2008, ISBN 978-3-540-77977-3, doi:10.1007/978-3-540-77978-0.
Commons: AVL-Bäume – Sammlung von Bildern, Videos und Audiodateien

Einzelnachweise

  1. Thomas H. Cormen u. a.: Introduction to Algorithms. 2. Auflage, MIT Press, Cambridge (Massachusetts) 2001, S. 296.
  2. G. M. Adelson-Velsky, E. M. Landis: Один алгоритм организации информации. In: Doklady Akademii Nauk SSSR. 146, 1962, S. 263–266. (russisch)
    Englische Übersetzung von Myron J. Ricci: An algorithm for the organization of information. (Memento vom 1. Februar 2014 im Internet Archive) (PDF) In: Soviet Mathematics 3, 1962, S. 1259–1263.
  3. In der englischen Literatur meist „balance factor“, so bei Donald E. Knuth: The Art of Computer Programming. Band 3, Sorting and Searching, 2. Auflage, Addison-Wesley, 1998, S. 459; „Höhenbalance“ bei Kurt Mehlhorn: Datenstrukturen und effiziente Algorithmen. Teubner, Stuttgart 1988, S. 295.
  4. Donald E. Knuth: The Art of Computer Programming. Band 3, Sorting and Searching, 2. Auflage, Addison-Wesley, 1998, S. 460.
  5. Ben Pfaff Performance Analysis of BSTs in System Software S. 2
  6. s. Donald Knuth: The Art of Computer Programming S. 460.
  7. Diesen Weg geht Donald Knuth in The Art of Computer Programming S. 462.
  8. so Ben Pfaff in An Introduction to Binary Search Trees and Balanced Trees § 34.
  9. Dinesh P. Mehta, Sartaj Sahni (Hrsg.) Handbook of Data Structures and Applications 10.4.2
  10. Laut Robert Sedgewick, Kevin Wayne: Algorithms Fourth Edition. (PDF)@1@2Vorlage:Toter Link/github.com (Seite nicht mehr abrufbar, Suche in Webarchiven)  Info: Der Link wurde automatisch als defekt markiert. Bitte prüfe den Link gemäß Anleitung und entferne dann diesen Hinweis. (PDF) Pearson Education, 2011, ISBN 978-0-321-57351-3, S. 410 (englisch, abgerufen am 25. März 2018) stammt der Vorschlag aus dem Jahr 1962 von T. Hibbard. In An Introduction to Binary Search Trees and Balanced Trees S. 39 wählt Ben Pfaff – so vorhanden – stets den letzteren. Man kann aber auch den ersteren nehmen oder von beiden Teilbäumen den eventuell höheren.
  11. Die Abbildungen entsprechen Donald Knuth The Art of Computer Programming S. 461 Case1 (Einfachrotation) und Case2 (Doppelrotation).
  12. Donald E. Knuth: The Art of Computer Programming, Band 3, Sorting and Searching, 2. Auflage, Addison-Wesley, 1998, S. 474
  13. Costin S, der in seinem Projekt AvlTree.cs AVL-Bäume mit Concat- und Split-Operationen implementiert, fordert dazu die Aufzeichnung der vollen absoluten Höhe in jedem Knoten. Man kann aber – wie gezeigt – mit den Balance-Faktoren auskommen, ohne den Aufwand zu erhöhen.
  14. Ben Pfaff gibt einem Objekt mit sehr ähnlicher Funktionalität den Namen „traverser“ und offeriert für Suchen, Einfügen und Löschen eine Standard- und eine Traverser-Variante. (An Introduction to Binary Search Trees and Balanced Trees S. 15 und Performance Analysis of BSTs in System Software S. 3)
  15. Eugene W. Myers: AVL dags. In: Technical Report, Department of Computer Science, U. of Arizona. 82-9, 1982. Zitiert nach: Neil Sarnak, Robert E. Tarjan: Planar Point Location Using Persistent Search Trees Archiviert vom Original am 10. Oktober 2015. In: Communications of the ACM. 29, Nr. 7, 1986, S. 669–679. doi:10.1145/6138.6151. Abgerufen am 25. Dezember 2014.
  16. „Top-Down-Strategie“ bei Kurt Mehlhorn: Datenstrukturen und effiziente Algorithmen. Teubner, Stuttgart 1988, S. 197–198.
  17. Paul E. Black: AVL tree. In: Dictionary of Algorithms and Data Structures. National Institute of Standards and Technology, 13. April 2015, abgerufen am 2. Juli 2016 (englisch).
  18. Kurt Mehlhorn, Peter Sanders: Algorithms and Data Structures. The Basic Toolbox. Springer, Berlin/Heidelberg 2008, ISBN 978-3-540-77977-3, doi:10.1007/978-3-540-77978-0. S. 165.
  19. Ben Pfaff: Performance Analysis of BSTs in System Software. Stanford University 2004.

Anmerkungen

  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
  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 der Knoten gegen unendlich, dann verhält sich seine mittlere Suchtiefe asymptotisch wie
        mit     ,
    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 die Anzahl der Knoten, die nicht Blätter sind und die zwei Kindbäume gleicher Höhe haben, und die Anzahl der Knoten mit verschieden hohen Kindbäumen, dann ist der Anteil der höhenungleichen. (Nur die Fibonacci-Bäume und die anderen dünnsten AVL-Bäume erreichen exakt . Dagegen kommen nur die vollständigen Binärbäume (mit inneren Knoten) auf exakt . Der Mittelwert über alle möglichen Formen von AVL-Bäumen liegt bei .)
    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äufigkeitvorläu-
    figer
    BF
    Rebalan-
    cierung
    erforderlich
    BF
    da-
    nach
    Teilbaum
    wird
    höher um
    Ebene ober-
    halb zu
    überprüfen
    −1links höher0Nein0Nein
    0höhengleich+1Nein1Ja
    +1rechts höher+2Ja00Nein
    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 . Unter der Annahme, dass diese Wahrscheinlichkeiten für alle Ebenen gleich sind, ist die Wahrscheinlichkeit, dass wenigstens Ebenen überprüft werden müssen, gleich und, dass genau Ebenen überprüft werden müssen, gleich . Somit summiert sich die Anzahl der zu überprüfenden Ebenen im Mittel auf
    Diese Funktion in fällt monoton von (für und vollständige Binärbäume) auf (für und Fibonacci-Bäume). Nach dem Einfügen (mit Korrektur des Balance-Faktors) ist für 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äufigkeitvorläu-
    figer
    BF
    Rebalan-
    cierung
    erforderlich
    BF
    da-
    nach
    Teilbaum
    wird nied-
    riger um
    Ebene ober-
    halb zu
    überprüfen
    −1links höher0Nein1Ja
    0höhengleich+1Nein0Nein
    +1rechts höher+2Ja+10 1Nein
    01 2Ja
    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 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
    .
    Diese Funktion in wächst monoton von (für und vollständige Binärbäume) auf (für und Fibonacci-Bäume). Nach dem Löschen (mit Korrektur des Balance-Faktors) muss für 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 Bytesminimale Knotenlänge
    (2 Zeiger+1 Byte
    +Nutzdaten 1)
    maxi-
    male Anzahl Knoten
    Knotenzahl des nächstgrößeren Fibonacci-Baums …… der Höhe
    3242949672962·4+1+3 = 123,6·10843349443641
    64184467440737095516162·8+1+7 = 247,7·1018110008777836610193086
    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 -fache Schleife bestehend aus Einfügung eines zusätzlichen Knotens und Löschung desselben jedesmal die Anpassung von Balance-Faktoren bis hinauf zur Wurzel und damit einen Aufwand in , also amortisiert .

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. The authors of the article are listed here. Additional terms may apply for the media files, click on images to show image meta data.