AVL-boom - AVL tree

AVL-boom
Type	boom
uitgevonden	1962
Uitgevonden door	Georgy Adelson-Velsky en Evgenii Landis
Tijdcomplexiteit in grote O-notatie
Algoritme Gemiddeld Het slechtste geval Ruimte ${\displaystyle {\text{Θ}}(n)}$ ${\displaystyle {\text{O}}(n)}$ Zoeken ${\displaystyle {\text{Θ}}(\log n)}$ ${\displaystyle {\text{O}}(\log n)}$ Invoegen ${\displaystyle {\text{Θ}}(\log n)}$ ${\displaystyle {\text{O}}(\log n)}$ Verwijderen ${\displaystyle {\text{Θ}}(\log n)}$ ${\displaystyle {\text{O}}(\log n)}$

Animatie die het invoegen van verschillende elementen in een AVL-boom toont. Het omvat links, rechts, links-rechts en rechts-links rotaties.

Fig. 1: AVL-boom met balansfactoren (groen)

In de informatica , een AVL boom (vernoemd naar de uitvinders A delson- V elsky en L Andis) is een self-balancing binaire zoekboom . Het was de eerste dergelijke datastructuur die werd uitgevonden. In een AVL-boom verschillen de hoogten van de twee onderliggende subbomen van elk knooppunt met maximaal één; als ze op enig moment met meer dan één verschillen, wordt er een herbalancering uitgevoerd om deze eigenschap te herstellen. Opzoeken, invoegen en verwijderen nemen allemaal O (log n ) tijd in zowel de gemiddelde als de slechtste gevallen, waarbij het aantal knooppunten in de boomstructuur voorafgaand aan de bewerking is. Invoegingen en verwijderingen kunnen vereisen dat de boom opnieuw in evenwicht wordt gebracht door een of meer boomrotaties . ${\displaystyle n}$

De AVL-boom is vernoemd naar zijn twee Sovjet- uitvinders, Georgy Adelson-Velsky en Evgenii Landis , die het in 1962 publiceerden in hun paper "An algorithm for the organization of information".

AVL-bomen worden vaak vergeleken met rood-zwarte bomen omdat beide dezelfde reeks bewerkingen ondersteunen en tijd vergen voor de basisbewerkingen. Voor zoekintensieve toepassingen zijn AVL-bomen sneller dan rood-zwarte bomen omdat ze strikter in balans zijn. Net als bij roodzwarte bomen, zijn AVL-bomen in hoogte uitgebalanceerd. Beide zijn over het algemeen voor niemand uitgebalanceerd of uitgebalanceerd ; dat wil zeggen, zusterknooppunten kunnen enorm verschillende aantallen nakomelingen hebben. ${\displaystyle {\text{O}}(\log n)}$${\displaystyle \mu}$${\displaystyle \mu \leq {\tfrac {1}{2}}}$

Definitie

Balansfactor

In een binaire boom wordt de balansfactor van een knoop X gedefinieerd als het hoogteverschil

${\displaystyle {\text{BF}}(X):={\text{Hoogte}}({\text{RightSubtree}}(X))-{\text{Hoogte}}({\text{LeftSubtree}} (X))}$

van zijn twee onderliggende sub-bomen. Een binaire boom wordt gedefinieerd als een AVL-boom als de invariant

${\displaystyle {\text{BF}}(X)\in {\{-1,0,1\}}}$

geldt voor elk knooppunt X in de boom.

Een knoop X met heet "links-zwaar", een met wordt "rechts-zwaar" genoemd en een met wordt soms gewoon "gebalanceerd" genoemd. ${\displaystyle {\text{BF}}(X)<0}$${\displaystyle {\text{BF}}(X)>0}$${\displaystyle {\text{BF}}(X)=0}$

Eigendommen

Balansfactoren kunnen up-to-date worden gehouden door de vorige balansfactoren en de hoogteverandering te kennen – het is niet nodig om de absolute hoogte te kennen. Om de AVL-balansinformatie op de traditionele manier vast te houden, zijn twee bits per node voldoende. Later onderzoek toonde echter aan dat als de AVL-boom wordt geïmplementeerd als een rank-balanced tree met delta-rangen toegestaan ​​van 1 of 2, met de betekenis "wanneer je omhoog gaat, is er een extra toename in hoogte van één of twee", dit kan worden gedaan met één beetje.

De hoogte (geteld als het maximale aantal niveaus) van een AVL-boom met knooppunten ligt in het interval: ${\displaystyle h}$${\displaystyle n}$

${\displaystyle \log _{2}(n+1)\leq h<\log _{\varphi }(n+2)+b}$

waar   is de gulden snede en dit komt omdat een AVL-boom van hoogte ten minste knooppunten bevat, waar is de Fibonacci-reeks met de zaadwaarden${\displaystyle \varphi :={\tfrac {1+{\sqrt {5}}}{2}}\circa 1.618}$${\displaystyle b:={\frac {\log _{2}5}{2\log _{2}\varphi }}-2\circa \;-0.3277.}$${\displaystyle h}$${\displaystyle F_{h+2}-1}$${\displaystyle \{F_{n}\}_{n\in \mathbb {N} }}$${\displaystyle F_{1}=F_{2}=1.}$

Activiteiten

Alleen-lezen bewerkingen van een AVL-boom omvatten het uitvoeren van dezelfde acties als zou worden uitgevoerd op een ongebalanceerde binaire zoekboom , maar wijzigingen moeten de hoogtebalans van de sub-bomen observeren en herstellen.

Zoeken

Zoeken naar een specifieke sleutel in een AVL-boom kan op dezelfde manier worden gedaan als in elke gebalanceerde of ongebalanceerde binaire zoekboom . Om het zoeken effectief te laten werken, moet het een vergelijkingsfunctie gebruiken die een totale bestelling (of op zijn minst een totale pre-order ) op de set sleutels vastlegt. Het aantal vergelijkingen dat nodig is voor succesvol zoeken wordt beperkt door de hoogte h en voor niet-succesvol zoeken is zeer dicht bij h , dus beide zijn in O(log n ) .

Traversal

Als een alleen-lezen bewerking werkt het doorlopen van een AVL-boom op dezelfde manier als op elke andere binaire boom. Door alle n knooppunten van de boom te verkennen, wordt elke link precies twee keer bezocht: één bezoek naar beneden om de subboom te betreden die door dat knooppunt is geworteld, een ander bezoek omhoog om de subboom van dat knooppunt te verlaten nadat deze is verkend.

Zodra een knooppunt is gevonden in een AVL-boom, kan het volgende of vorige knooppunt worden benaderd in afgeschreven constante tijd. Sommige gevallen van het verkennen van deze "nabijgelegen" knooppunten vereisen het doorlopen van tot h ∝ log( n ) links (vooral bij het navigeren van het meest rechtse blad van de linker subboom van de wortel naar de wortel of van de wortel naar het meest linkse blad van de rechter subboom van de wortel; in de AVL-boom van figuur 1, navigeren van knooppunt P naar het naast de rechter knooppunt Q duurt 3 stappen). Aangezien er n −1 schakels in een boom zijn, is de geamortiseerde kostprijs 2×( n −1)/ n , of ongeveer 2.

Invoegen

Bij het invoegen van een knooppunt in een AVL-boom, volgt u aanvankelijk hetzelfde proces als bij het invoegen in een binaire zoekboom . Als de boom leeg is, wordt het knooppunt ingevoegd als de wortel van de boom. In het geval dat de boom niet leeg is geweest, gaan we naar de wortel en gaan we recursief door de boom op zoek naar de locatie om het nieuwe knooppunt in te voegen. Deze verplaatsing wordt geleid door de vergelijkingsfunctie. In dit geval vervangt het knooppunt altijd een NULL-referentie (links of rechts) van een extern knooppunt in de boomstructuur, dwz dat het knooppunt ofwel een linker-kind of een rechter-kind van het externe knooppunt wordt.

Als na deze invoeging een boom uit balans raakt, zijn alleen de voorouders van de nieuw ingevoegde knoop uit balans. Dit komt omdat alleen die knooppunten hun sub-bomen hebben gewijzigd. Het is dus noodzakelijk om elk van de voorouders van het knooppunt te controleren op consistentie met de invarianten van AVL-bomen: dit wordt "retracing" genoemd. Dit wordt bereikt door rekening te houden met de balansfactor van elk knooppunt.

Aangezien met een enkele invoeging de hoogte van een AVL-subboom niet met meer dan één kan toenemen, zal de tijdelijke balansfactor van een knooppunt na een invoeging in het bereik [-2,+2] liggen. Voor elk aangevinkt knooppunt, als de tijdelijke balansfactor binnen het bereik van –1 tot +1 blijft, dan is alleen een update van de balansfactor en geen rotatie nodig. Als de tijdelijke balansfactor echter kleiner wordt dan –1 of groter dan +1, is de substructuur die op dit knooppunt is geworteld, AVL ongebalanceerd en is een rotatie nodig. Met invoeging zoals de onderstaande code laat zien, brengt de juiste rotatie de boom onmiddellijk perfect in evenwicht .

In figuur 1 wordt door het invoegen van de nieuwe knoop Z als een kind van knoop X de hoogte van die subboom Z vergroot van 0 naar 1.

Invariant van de traceerlus voor een insertie

De hoogte van de subboom die door Z is geroot, is met 1 toegenomen. Hij heeft al een AVL-vorm.

for (X = parent(Z); X != null; X = parent(Z)) { // Loop (possibly up to the root)
    // BF(X) has to be updated:
    if (Z == right_child(X)) { // The right subtree increases
        if (BF(X) > 0) { // X is right-heavy
            // ==> the temporary BF(X) == +2
            // ==> rebalancing is required.
            G = parent(X); // Save parent of X around rotations
            if (BF(Z) < 0)                  // Right Left Case  (see figure 3)
                N = rotate_RightLeft(X, Z); // Double rotation: Right(Z) then Left(X)
            else                            // Right Right Case (see figure 2)
                N = rotate_Left(X, Z);      // Single rotation Left(X)
            // After rotation adapt parent link
        } else {
            if (BF(X) < 0) {
                BF(X) = 0; // Z’s height increase is absorbed at X.
                break; // Leave the loop
            }
            BF(X) = +1;
            Z = X; // Height(Z) increases by 1
            continue;
        }
    } else { // Z == left_child(X): the left subtree increases
        if (BF(X) < 0) { // X is left-heavy
            // ==> the temporary BF(X) == -2
            // ==> rebalancing is required.
            G = parent(X); // Save parent of X around rotations
            if (BF(Z) > 0)                  // Left Right Case
                N = rotate_LeftRight(X, Z); // Double rotation: Left(Z) then Right(X)
            else                            // Left Left Case
                N = rotate_Right(X, Z);     // Single rotation Right(X)
            // After rotation adapt parent link
        } else {
            if (BF(X) > 0) {
                BF(X) = 0; // Z’s height increase is absorbed at X.
                break; // Leave the loop
            }
            BF(X) = -1;
            Z = X; // Height(Z) increases by 1
            continue;
        }
    }
    // After a rotation adapt parent link:
    // N is the new root of the rotated subtree
    // Height does not change: Height(N) == old Height(X)
    parent(N) = G;
    if (G != null) {
        if (X == left_child(G))
            left_child(G) = N;
        else
            right_child(G) = N;
    } else
        tree->root = N; // N is the new root of the total tree
    break;
    // There is no fall thru, only break; or continue;
}
// Unless loop is left via break, the height of the total tree increases by 1.

Om de balansfactoren van alle knooppunten bij te werken, moet u eerst vaststellen dat alle knooppunten die moeten worden gecorrigeerd, van kind naar ouder liggen langs het pad van het ingevoegde blad. Als de bovenstaande procedure wordt toegepast op knooppunten langs dit pad, beginnend bij het blad, dan heeft elk knooppunt in de boom opnieuw een balansfactor van -1, 0 of 1.

Het traceren kan stoppen als de balansfactor 0 wordt, wat inhoudt dat de hoogte van die subboom ongewijzigd blijft.

Als de balansfactor ±1 wordt, neemt de hoogte van de subboom met één toe en moet het natrekken doorgaan.

Als de balansfactor tijdelijk ±2 wordt, moet dit worden gerepareerd door een geschikte rotatie, waarna de subboom dezelfde hoogte heeft als voorheen (en zijn wortel de balansfactor 0).

De benodigde tijd is O(log n ) voor het opzoeken, plus een maximum van O(log n ) retracing-niveaus ( gemiddeld O(1) ) op de weg terug naar de root, zodat de bewerking kan worden voltooid in O(log n). ) tijd.

Verwijderen

De voorbereidende stappen voor het verwijderen van een knooppunt worden beschreven in de sectie Binaire zoekboom#Verwijderen . Daar verlaagt de effectieve verwijdering van het onderwerpknooppunt of het vervangende knooppunt de hoogte van de overeenkomstige onderliggende boom van 1 naar 0 of van 2 naar 1, als dat knooppunt een kind had.

Vanaf deze subboom is het noodzakelijk om elk van de voorouders te controleren op consistentie met de invarianten van AVL-bomen. Dit wordt "retracing" genoemd.

Aangezien met een enkele verwijdering de hoogte van een AVL-subboom niet met meer dan één kan afnemen, zal de tijdelijke balansfactor van een knooppunt in het bereik van -2 tot +2 liggen. Als de balansfactor binnen het bereik van −1 tot +1 blijft, kan deze worden aangepast in overeenstemming met de AVL-regels. Als het ±2 wordt, is de subboom uit balans en moet deze worden geroteerd. (In tegenstelling tot invoeging waarbij een rotatie altijd de boom in evenwicht houdt, kan er na verwijdering BF(Z) ≠ 0 zijn (zie afbeeldingen 2 en 3), zodat na de juiste enkele of dubbele rotatie de hoogte van de opnieuw gebalanceerde subboom met één betekenis afneemt dat de boom opnieuw in evenwicht moet worden gebracht op het eerstvolgende hogere niveau.) De verschillende gevallen van rotaties worden beschreven in de sectie Opnieuw in evenwicht brengen .

Invariant van de traceerlus voor een verwijdering

De hoogte van de subboom met wortel N is met 1 afgenomen. Hij heeft al een AVL-vorm.

for (X = parent(N); X != null; X = G) { // Loop (possibly up to the root)
    G = parent(X); // Save parent of X around rotations
    // BF(X) has not yet been updated!
    if (N == left_child(X)) { // the left subtree decreases
        if (BF(X) > 0) { // X is right-heavy
            // ==> the temporary BF(X) == +2
            // ==> rebalancing is required.
            Z = right_child(X); // Sibling of N (higher by 2)
            b = BF(Z);
            if (b < 0)                      // Right Left Case  (see figure 3)
                N = rotate_RightLeft(X, Z); // Double rotation: Right(Z) then Left(X)
            else                            // Right Right Case (see figure 2)
                N = rotate_Left(X, Z);      // Single rotation Left(X)
            // After rotation adapt parent link
        } else {
            if (BF(X) == 0) {
                BF(X) = +1; // N’s height decrease is absorbed at X.
                break; // Leave the loop
            }
            N = X;
            BF(N) = 0; // Height(N) decreases by 1
            continue;
        }
    } else { // (N == right_child(X)): The right subtree decreases
        if (BF(X) < 0) { // X is left-heavy
            // ==> the temporary BF(X) == -2
            // ==> rebalancing is required.
            Z = left_child(X); // Sibling of N (higher by 2)
            b = BF(Z);
            if (b > 0)                      // Left Right Case
                N = rotate_LeftRight(X, Z); // Double rotation: Left(Z) then Right(X)
            else                            // Left Left Case
                N = rotate_Right(X, Z);     // Single rotation Right(X)
            // After rotation adapt parent link
        } else {
            if (BF(X) == 0) {
                BF(X) = -1; // N’s height decrease is absorbed at X.
                break; // Leave the loop
            }
            N = X;
            BF(N) = 0; // Height(N) decreases by 1
            continue;
        }
    }
    // After a rotation adapt parent link:
    // N is the new root of the rotated subtree
    parent(N) = G;
    if (G != null) {
        if (X == left_child(G))
            left_child(G) = N;
        else
            right_child(G) = N;
    } else
        tree->root = N; // N is the new root of the total tree
 
    if (b == 0)
        break; // Height does not change: Leave the loop
 
    // Height(N) decreases by 1 (== old Height(X)-1)
}
// If (b != 0) the height of the total tree decreases by 1.

Het traceren kan stoppen als de balansfactor ±1 wordt (het moet 0 zijn geweest), wat betekent dat de hoogte van die subboom ongewijzigd blijft.

Als de balansfactor 0 wordt (het moet ±1) zijn geweest, dan neemt de hoogte van de subboom met één af en moet het traceren doorgaan.

Als de balansfactor tijdelijk ±2 wordt, moet dit worden gerepareerd door een geschikte rotatie. Het hangt af van de balansfactor van de broer of zus Z (de hogere kindboom in figuur 2) of de hoogte van de deelboom met één afneemt – en het natrekken moet doorgaan – of niet verandert (als Z de balansfactor 0 heeft) en de hele boom is in AVL-vorm.

De benodigde tijd is O(log n ) voor het opzoeken, plus een maximum van O(log n ) retracing-niveaus ( gemiddeld O(1) ) op de weg terug naar de root, zodat de bewerking kan worden voltooid in O(log n). ) tijd.

Bewerkingen en bulkbewerkingen instellen

Naast de invoeg-, verwijder- en opzoekbewerkingen met één element, zijn er verschillende setbewerkingen gedefinieerd op AVL-bomen: unie , intersectie en stel verschil . Vervolgens kunnen op basis van deze ingestelde functies snelle bulkbewerkingen op invoegingen of verwijderingen worden geïmplementeerd. Deze set-operaties zijn afhankelijk van twee helper-operaties, Split en Join . Met de nieuwe operaties kan de implementatie van AVL-bomen efficiënter en beter parallel worden uitgevoerd.

De functie Samenvoegen op twee AVL-bomen t ₁ en t ₂ en een toets k geeft een boom terug die alle elementen in t ₁ , t ₂ en k bevat . Het vereist dat k groter is dan alle sleutels in t ₁ en kleiner dan alle sleutels in t ₂ . Als de twee bomen hoogstens één in hoogte verschillen, maakt Join eenvoudig een nieuwe knoop met linker subboom t ₁ , wortel k en rechter subboom t ₂ . Stel anders dat t ₁ hoger is dan t ₂ voor meer dan één (het andere geval is symmetrisch). Join volgt de rechter ruggengraat van t ₁ tot een knoop c die in evenwicht is met t ₂ . Op dit moment een nieuw knooppunt linkerkind c , wortel k en rechterkind t ₂ is gemaakt c vervangen. Het nieuwe knooppunt voldoet aan de AVL-invariant en de hoogte is één groter dan c . De toename in hoogte kan de hoogte van zijn voorouders vergroten, waardoor de AVL-invariant van die knooppunten mogelijk ongeldig wordt. Dit kan worden opgelost met een dubbele rotatie als deze ongeldig is bij de ouder of een enkele rotatie naar links als deze hoger in de boom ongeldig is, in beide gevallen wordt de hoogte voor eventuele verdere voorouderknooppunten hersteld. Join vereist daarom maximaal twee rotaties. De kosten van deze functie zijn het hoogteverschil tussen de twee invoerbomen.

function JoinRightAVL(TL, k, TR)
    (l,k',c) = expose(TL)
    if (Height(c) <= Height(TR)+1)
       T'=Node(c,k,TR)
       if (Height(T') <= Height(l)+1) then return Node(l,k',T')
       else return rotateLeft(Node(l,k'rotateRight(T')))
    else 
        T' = JoinRightAVL(c,k,TR)
        T = Node(l,k',T')
        if (Height(T') <= Height(l)+1) return T
        else return rotateLeft(T)

function JoinLeftAVL(TL, k, TR)
  /* symmetric to JoinRightAVL */

function Join(TL, k, TR)
    if (Height(TL)>Height(TR)+1) return JoinRightAVL(TL, k, TR)
    if (Height(TR)>Height(TL)+1) return JoinLeftAVL(TL, k, TR)
    return Node(TL,k,TR)

Om een ​​AVL-boom in twee kleinere bomen te splitsen, die kleiner dan sleutel k , en die groter dan sleutel k , teken je eerst een pad vanaf de wortel door k in de AVL in te voegen . Na deze invoeging zullen alle waarden kleiner dan k aan de linkerkant van het pad worden gevonden en alle waarden groter dan k aan de rechterkant. Door Join toe te passen , worden alle subbomen aan de linkerkant van onder naar boven samengevoegd met behulp van toetsen op het pad als tussenknooppunten van onder naar boven om de linkerboom te vormen, en het rechtergedeelte is asymmetrisch. De kosten van Split zijn O(log n ) , volgorde van de hoogte van de boom.

function Split(T,k)
    if (T = nil) return (nil,false,nil)
    (L,m,R) = expose(T)
    if (k = m) return (L,true,R)
    if (k<m) 
       (L',b,R') = split(L,k)
       return (L',b,join(R',m,R))
    if (k>m) 
       (L',b,R') = split(R,k)
       return (join(L,m,L'),b,R'))

De vereniging van twee AVL bomen t ₁ en t ₂ vertegenwoordigen sets A en B , is een AVL t die aangeeft A ∪ B .

function Union(t1, t2):
    if t1 = nil:
        return t2
    if t2 = nil:
        return t1
    t<, t> ← split t2 on t1.root
    return join(t1.root,union(left(t1), t<),union(right(t1), t>))

Het algoritme voor intersectie of verschil is vergelijkbaar, maar vereist de Join2-helperroutine die hetzelfde is als Join, maar zonder de middelste toets. Op basis van de nieuwe functies voor unie, intersectie of verschil, kunnen één sleutel of meerdere sleutels worden ingevoegd in of verwijderd uit de AVL-boom. Aangezien Split Join aanroept maar niet rechtstreeks de balanceringscriteria van AVL-bomen behandelt, wordt een dergelijke implementatie meestal de "join-based" implementatie genoemd .

De complexiteit van elk van unie, intersectie en verschil is voor AVL-bomen van grootte en . Wat nog belangrijker is, aangezien de recursieve oproepen naar unie, intersectie of verschil onafhankelijk van elkaar zijn, kunnen ze parallel worden uitgevoerd met een parallelle diepte . When , de op joins gebaseerde implementatie heeft dezelfde rekenkundige DAG als het invoegen en verwijderen van één element. ${\displaystyle {\text{O}}\left(m\log \left({n \over m}+1\right)\right)}$${\displaystyle m}$${\ Displaystyle n \; (\ geq m)}$ ${\displaystyle {\text{O}}(\log m\log n)}$${\displaystyle m=1}$

Opnieuw in evenwicht brengen

Als tijdens een wijzigingshandeling het hoogteverschil tussen twee onderliggende subbomen verandert, kan dit, zolang het < 2 is, worden weerspiegeld door een aanpassing van de balansinformatie bij de ouder. Tijdens invoeg- en verwijderbewerkingen kan een (tijdelijk) hoogteverschil van 2 ontstaan, wat betekent dat de bovenliggende subboom "opnieuw gebalanceerd" moet worden. De gegeven reparatietools zijn de zogenaamde boomrotaties , omdat ze de sleutels alleen "verticaal" verplaatsen, zodat de ("horizontale") volgorde van de sleutels volledig behouden blijft (wat essentieel is voor een binaire zoekboom ).

Laat X de knoop zijn met een (tijdelijke) balansfactor van −2 of +2. De linker- of rechtersubboom is gewijzigd. Laat Z het hogere kind zijn (zie figuren 2 en 3). Merk op dat beide kinderen in AVL-vorm zijn volgens de inductiehypothese .

In het geval van insertie is deze insertie gebeurd met een van de kinderen van Z op een manier dat de lengte van Z is toegenomen. In het geval van deletie is deze deletie gebeurd met de broer of zus t ₁ van Z op een manier zodat de hoogte van t ₁ die al lager was, is afgenomen. (Dit is het enige geval waarin de balansfactor van Z ook 0 kan zijn.)

Er zijn vier mogelijke varianten van de overtreding:

En de herbalancering wordt anders uitgevoerd:

Daarbij worden de situaties aangeduid als CB , waarbij C (= kindrichting) en B (= balans) komen uit de verzameling { Links , Rechts } met Rechts  := − Links . De evenwichtsovertreding van geval C == B wordt hersteld door een eenvoudige rotatie rotate_(− C ), terwijl het geval C  != B wordt hersteld door een dubbele rotatie rotate_CB .

De kosten van een rotatie, eenvoudig of dubbel, zijn constant.

Eenvoudige rotatie

Figuur 2 toont een Rechts Rechts situatie. In de bovenste helft heeft knooppunt X twee onderliggende bomen met een balansfactor van +2 . Bovendien is de binnenste kind t ₂₃ Z (dwz linkerkind wanneer Z rechterkind resp. Rechterkind wanneer Z linkerkind) niet hoger is dan zijn grote broer t ₄ . Dit kan gebeuren door een hoogteverhoging van deelboom t ₄ of door een hoogtedaling van deelboom t ₁ . In het laatste geval ook de bleke situatie waarin t ₂₃ heeft dezelfde hoogte als t ₄ optreden.

Het resultaat van de rotatie naar links wordt weergegeven in de onderste helft van de figuur. Drie schakels (dikke randen in figuur 2) en twee balansfactoren moeten worden bijgewerkt.

Zoals de figuur laat zien, bevond de bladlaag zich voor een invoeging op niveau h+1, tijdelijk op niveau h+2 en na de rotatie weer op niveau h+1. Bij een deletie bevond de bladlaag zich op niveau h+2, waar hij weer is, toen t ₂₃ en t ₄ even hoog waren. Anders bereikt de bladlaag niveau h+1, waardoor de hoogte van de geroteerde boom afneemt.

Fig. 2: Eenvoudige rotatie
roteren_Links ( X , Z )

Codefragment van een eenvoudige rotatie naar links

node *rotate_Left(node *X, node *Z) {
    // Z is by 2 higher than its sibling
    t23 = left_child(Z); // Inner child of Z
    right_child(X) = t23;
    if (t23 != null)
        parent(t23) = X;
    left_child(Z) = X;
    parent(X) = Z;
    // 1st case, BF(Z) == 0,
    //   only happens with deletion, not insertion:
    if (BF(Z) == 0) { // t23 has been of same height as t4
        BF(X) = +1;   // t23 now higher
        BF(Z) = –1;   // t4 now lower than X
    } else
    { // 2nd case happens with insertion or deletion:
        BF(X) = 0;
        BF(Z) = 0;
    }
    return Z; // return new root of rotated subtree
}

Dubbele rotatie

Figuur 3 toont een Rechts Links situatie. In het bovenste derde deel heeft knooppunt X twee onderliggende bomen met een balansfactor van +2 . Maar in tegenstelling tot figuur 2 is het innerlijke kind Y van Z hoger dan zijn broer of zus t ₄ . Dit kan gebeuren door het invoegen van Y zelf of een hoogteverhoging van een van zijn deelbomen t ₂ of t ₃ (met als gevolg dat ze van verschillende hoogte zijn) of door een hoogtedaling van deelboom t ₁ . In het laatste geval kan het ook voorkomen dat t ₂ en t ₃ zijn van dezelfde hoogte.

Het resultaat van de eerste, de rechter, rotatie wordt weergegeven in het middelste derde deel van de figuur. (Met betrekking tot de balansfactoren is deze rotatie niet van dezelfde soort als de andere AVL enkele rotaties, omdat het hoogteverschil tussen Y en t ₄ slechts 1 is.) Het resultaat van de laatste rotatie naar links wordt getoond in het onderste derde deel van de figuur. Vijf schakels (dikke randen in figuur 3) en drie balansfactoren moeten worden bijgewerkt.

Zoals de figuur laat zien, bevond de bladlaag zich voor een insertie op niveau h+1, tijdelijk op niveau h+2 en na de dubbele rotatie weer op niveau h+1. Bij een deletie bevond de bladlaag zich op niveau h+2 en na de dubbele rotatie op niveau h+1, zodat de hoogte van de geroteerde boom afneemt.

Fig. 3: Dubbele rotatie roteren_RightLeft ( X , Z )
= roteren_Rechts rond Z gevolgd door
roteren_Links rond X

Codefragment van een rechts-links dubbele rotatie

node *rotate_RightLeft(node *X, node *Z) {
    // Z is by 2 higher than its sibling
    Y = left_child(Z); // Inner child of Z
    // Y is by 1 higher than sibling
    t3 = right_child(Y);
    left_child(Z) = t3;
    if (t3 != null)
        parent(t3) = Z;
    right_child(Y) = Z;
    parent(Z) = Y;
    t2 = left_child(Y);
    right_child(X) = t2;
    if (t2 != null)
        parent(t2) = X;
    left_child(Y) = X;
    parent(X) = Y;
    // 1st case, BF(Y) == 0,
    //   only happens with deletion, not insertion:
    if (BF(Y) == 0) {
        BF(X) = 0;
        BF(Z) = 0;
    } else
    // other cases happen with insertion or deletion:
        if (BF(Y) > 0) { // t3 was higher
            BF(X) = –1;  // t1 now higher
            BF(Z) = 0;
        } else {
            // t2 was higher
            BF(X) = 0;
            BF(Z) = +1;  // t4 now higher
        }
    BF(Y) = 0;
    return Y; // return new root of rotated subtree
}

Vergelijking met andere structuren

Zowel AVL-bomen als rood-zwart (RB) bomen zijn zelfbalancerende binaire zoekbomen en ze zijn wiskundig gerelateerd. Elke AVL-boom kan inderdaad rood-zwart worden gekleurd, maar er zijn RB-bomen die niet AVL-gebalanceerd zijn. Voor het onderhouden van de AVL resp. Bij de invarianten van de RB-boom spelen rotaties een belangrijke rol. In het ergste geval, zelfs zonder rotaties, vereisen AVL- of RB-inserties of -verwijderingen O(log n ) inspecties en/of updates van AVL-balansfactoren resp. RB-kleuren. RB-inserties en -deleties en AVL-inserties vereisen nul tot drie recursieve staartrotaties en lopen in afgeschreven O(1) -tijd, dus gemiddeld even constant. AVL-deleties die in het ergste geval O(log n ) -rotaties vereisen, zijn ook gemiddeld O(1) . RB-bomen vereisen het opslaan van één bit informatie (de kleur) in elk knooppunt, terwijl AVL-bomen meestal twee bits gebruiken voor de balansfactor, hoewel, wanneer opgeslagen bij de kinderen, één bit met de betekenis "lager dan broer of zus" voldoende is. Het grotere verschil tussen de twee datastructuren is hun hoogtelimiet.

Voor een boom van maat n ≥ 1

• de hoogte van een AVL-boom is maximaal

  ${\displaystyle {\begin{array}{ll}h&\leqq \;c\log _{2}(n+d)+b\\&<\;c\log _{2}(n+2)+ b\end{array}}}$

waar   de gulden snede , en  .${\displaystyle \varphi :={\tfrac {1+{\sqrt {5}}}{2}}\circa 1.618}$${\displaystyle c:={\tfrac {1}{\log _{2}\varphi }}\circa 1.440,}$   ${\displaystyle b:={\tfrac {c}{2}}\log _{2}5-2\circa \;-0.328,}$${\displaystyle d:=1+{\tfrac {1}{\varphi ^{4}{\sqrt {5}}}}\circa 1.065}$

• de hoogte van een RB-boom is maximaal

  ${\displaystyle {\begin{array}{ll}h&\leqq \;2\log _{2}(n+1)\end{array}}}$ .

AVL-bomen zijn steviger uitgebalanceerd dan RB-bomen met een asymptotische relatie AVL/RB ≈0.720 van de maximale hoogtes. Voor inserties en deleties toont Ben Pfaff in 79 metingen een relatie van AVL/RB tussen 0,677 en 1,077 met mediaan 0,947 en geometrisch gemiddelde ≈0,910.

Zie ook

• Bomen
• Boomrotatie
• WAVL-boom
• Rood-zwarte boom
• spreiden boom
• zondebok boom
• B-boom
• T-boom
• Lijst met datastructuren

Referenties

Verder lezen

• Donald Knut . De kunst van computerprogrammering , deel 3: sorteren en zoeken , derde editie. Addison-Wesley, 1997. ISBN  0-201-89685-0 . Pagina's 458-475 van sectie 6.2.3: Gebalanceerde bomen.

Externe links

•  Dit artikel bevat materiaal  uit het publieke domein van het  NIST- document:  Black, Paul E. "AVL Tree" . Woordenboek van algoritmen en datastructuren .