AVL-träd

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 23 oktober 2021; kontroller kräver 6 redigeringar .
AVL-träd
engelsk  A.V.L träd
Sorts sökträd
Uppfinningens år 1968
Författare Adelson-Velsky Georgy Maksimovich och Landis Evgeny Mikhailovich
Komplexitet i O-symboler
Medel Som värst
Minnesförbrukning På) På)
Sök O(log n) O(log n)
Föra in O(log n) O(log n)
Borttagning O(log n) O(log n)
 Mediafiler på Wikimedia Commons

Ett AVL-träd  är ett höjdbalanserat binärt sökträd : för vart och ett av dess hörn skiljer sig höjden på dess två underträd inte med mer än 1.

AVL är en förkortning som bildas av de första bokstäverna av skaparna (sovjetiska forskare) Adelson-Velsky Georgy Maksimovich och Landis Evgeny Mikhailovich .

Maximal höjd

Den maximala höjden på ett AVL-träd för ett givet antal noder [1] :

var:

(runda upp)

(avrunda nedåt)

(avrunda nedåt).

Antalet möjliga höjder är mycket begränsat i praktiken (med 32-bitars adressering är den maximala höjden 45, med 48-bitars adressering är det 68), så det är förmodligen bättre att förberäkna alla värden för minimitalet av noder för varje höjd med den rekursiva formeln för Fibonacci-trädet :

,

,

.

Mellanvärden av antalet noder kommer att motsvara den tidigare (lägre) höjden.

Balansering

Med avseende på ett AVL-träd är vertexbalansering en operation som, om höjdskillnaden mellan det vänstra och högra underträdet = 2, ändrar föräldra-barn-länkarna i underträdet till detta vertex så att skillnaden blir <= 1, annars ändrar ingenting. Det angivna resultatet erhålls genom rotationer av underträdet i den givna vertexen.

4 typer av rotationer används:

1. Liten vänsterrotation Denna rotation används när höjdskillnaden mellan a-delträd och b-delträd är 2 och höjd C <= höjd R.

2. Stor vänsterrotation Denna rotation används när höjdskillnaden mellan a-underträd och b-underträd är 2 och höjden på c-underträdet > höjd R.

3. Liten högerrotation Denna rotation används när höjdskillnaden mellan a-delträd och b-delträd är 2 och höjd C <= höjd L.

4. Stor högerrotation Denna rotation används när höjdskillnaden mellan a-underträd och b-underträd är 2 och höjden på c-underträdet > höjd L.

I varje fall räcker det att helt enkelt bevisa att operationen leder till det önskade resultatet och att den totala höjden minskar med högst 1 och inte kan öka. Ett stort snurr är också en kombination av höger och vänster litet snurr. På grund av balanseringsvillkoret är trädets höjd O(log(N)), där N är antalet hörn, så att lägga till ett element kräver O(log(N))-operationer.

Algoritm för att lägga till en vertex

Balansindikatorn kommer att tolkas ytterligare som skillnaden mellan höjden på vänster och höger underträd, och algoritmen kommer att baseras på TAVLTree-typen som beskrivs ovan. Direkt vid insättning (ark) tilldelas ett nollsaldo. Processen att inkludera en vertex består av tre delar (denna process beskrivs av Niklaus Wirth i Algorithms and Data Structures):

  1. Passera längs sökvägen tills vi är säkra på att nyckeln inte finns i trädet.
  2. Inkludera en ny vertex i trädet och bestämma de resulterande balanseringsindikatorerna.
  3. "Riderar sig tillbaka" längs vägen för att söka och kontrollera vid varje hörn av balansindikatorn. Om det behövs, balansera.

Vi återkommer som ett resultat av funktionen om trädets höjd har minskat eller inte. Antag att en process från den vänstra grenen återvänder till föräldern (rekursionen går tillbaka), då är tre fall möjliga: { h l  - höjden på det vänstra underträdet, h r  - höjden på det högra underträdet } Inkluderande en vertex i det vänstra underträdet kommer att resultera i

  1. h l < h r : utjämnar h l = h r . Ingenting behöver göras.
  2. h l = h r : nu kommer det vänstra underträdet att vara ett större, men balansering krävs inte ännu.
  3. h l > h r : nu krävs h l  - h r = 2, - balansering.

I den tredje situationen är det nödvändigt att bestämma balanseringen av det vänstra underträdet. Om det vänstra underträdet i denna vertex (Tree^.left^.left) är högre än det högra (Tree^.left^.right), så krävs en stor högerrotation, annars räcker det med en liten höger. Liknande (symmetriska) resonemang kan ges för införande i det högra underträdet.

Algoritm för att ta bort en vertex

För enkelhetens skull beskriver vi en rekursiv raderingsalgoritm. Om vertexet är ett löv, tar vi bort det och kallar balanseringen av alla dess förfäder i ordning från förälder till rot. Annars hittar vi närmaste vertex i värde i underträdet för den högsta höjden (höger eller vänster) och flyttar det till platsen för vertexet som ska raderas, samtidigt som vi anropar borttagningsproceduren.

Låt oss bevisa att denna algoritm bevarar balansen. För att göra detta bevisar vi genom induktion på trädets höjd att efter att ha tagit bort en del vertex från trädet och efterföljande balansering, minskar trädets höjd med högst 1. Basen för induktionen: För ett löv, uppenbarligen sant. Induktionssteg: Antingen bryts inte balansvillkoret vid roten (efter radering kan roten ändras), då har höjden på det givna trädet inte ändrats, eller så har det strikt mindre av underträden minskat => höjden före balansering har inte ändrad => efter det kommer den att minska med högst 1.

Uppenbarligen, som ett resultat av dessa åtgärder, anropas borttagningsproceduren inte mer än 3 gånger, eftersom vertexet som tas bort av det andra anropet inte har ett av underträden. Men att hitta den närmaste kräver O(N) operationer varje gång. Möjligheten till optimering blir uppenbar: sökningen efter närmaste vertex kan utföras längs kanten av underträdet, vilket reducerar komplexiteten till O(log(N)).

Icke-rekursiv top-down infogning i ett AVL-träd

En icke-rekursiv algoritm är mer komplicerad än en rekursiv.

  1. Insättningspunkten och vertexen hittas, vars höjd inte kommer att ändras under infogningen (detta är vertexen för vilken höjden på det vänstra underträdet inte är lika med höjden på det högra; vi kommer att kalla det PrimeNode)
  2. Nedstigning från PrimeNode till insättningspunkten utförs med en förändring i balanser
  3. PrimeNode balanserar om när det finns ett spill

Icke-rekursiv radering från topp till botten av ett AVL-träd

För att implementera radering kommer vi att utgå från samma princip som när vi infogar: vi kommer att hitta en vertex, från vilken radering inte kommer att leda till en förändring i dess höjd. Det finns två fall:

  1. höjden på det vänstra underträdet är lika med höjden på det högra underträdet (förutom när bladet inte har några underträd)
  2. höjden på trädet i rörelseriktningen är mindre än den motsatta ("bror" till riktningen) och balansen för "bror" är 0 (att analysera detta alternativ är ganska komplicerat, så inga bevis ännu)

För att underlätta förståelsen innehåller ovanstående algoritm inga optimeringar. Till skillnad från den rekursiva algoritmen ersätts den hittade borttagna vertexen med värdet från den vänstra undergrenen. Denna algoritm kan optimeras på samma sätt som den rekursiva (på grund av det faktum att rörelseriktningen är känd efter att ha hittat vertexet som ska tas bort):

  1. vi letar efter elementet som ska raderas och längs vägen hittar vi vår underbara topp
  2. vi gör förändringar i saldon, vid behov gör vi ombalansering
  3. ta bort vårt element (vi tar faktiskt inte bort det, men ersätter dess nyckel och värde, att redogöra för permutationer av hörn blir lite mer komplicerat)

Ordning av saldon vid borttagning

Som redan nämnts, om vertexet som ska raderas är ett löv, så tas det bort, och den omvända genomgången av trädet sker från föräldern till det raderade bladet. Om det inte är ett löv, hittas en "ersättning" för det, och den omvända traverseringen av trädet kommer från "ersättningsföräldern". Omedelbart efter avlägsnandet av elementet - "ersättning" tar emot balansen av den borttagna noden.

I omvänd bypass: om de under övergången till föräldern kom från vänster, ökar saldot med 1, om de kom från höger, minskar det med 1.

Detta görs tills balansen ändras till -1 eller 1 (märk skillnaden med att infoga ett element!): i detta fall skulle en sådan balansändring indikera en konstant deltahöjd på underträden. Rotationer följer samma regler som vid insättning.

Ordning av saldon vid ett enda varv

Beteckna:

Om rotationen sker när ett element sätts in, är pivotens balans antingen 1 eller −1. I det här fallet, efter rotationen, sätts saldonen för båda lika med 0. Vid radering är allt annorlunda: Pivots saldo kan bli lika med 0 (detta är lätt att verifiera).

Här är en sammanfattande tabell över de slutliga balansernas beroende av rotationsriktningen och den initiala balansen för pivotnoden:

Sväng riktning Gammal pivotbalans Ny Current.Balance Ny pivotbalans
Vänster eller höger -1 eller +1 0 0
Höger 0 -ett +1
Vänster 0 +1 -ett

Dubbelvarv balanserar

Pivot och Current är samma, men en tredje medlem av turn läggs till. Låt oss beteckna det för "Bottom": det är (med en dubbel högersväng) Pivots vänstra son, och med en dubbel vänster - Pivots högra son.

Med denna rotation får Bottom alltid ett saldo på 0 som ett resultat, men arrangemanget av saldon för Pivot och Current beror på dess initiala balans.

Här är en sammanfattande tabell över de slutliga balansernas beroende av rotationsriktningen och den initiala balansen för Bottennoden:

Riktning Gammal bottenbalans Ny Current.Balance Ny pivotbalans
Vänster eller höger 0 0 0
Höger +1 0 -ett
Höger -ett +1 0
Vänster +1 -ett 0
Vänster -ett 0 +1

Prestationsbedömning

Från formeln ovan kommer höjden på ett AVL-träd aldrig att överstiga höjden på ett perfekt balanserat träd med mer än 45 %. För stora har vi uppskattningen . Att utföra grundläggande operationer kräver således en jämförelseordning. Det har experimentellt visat sig att en balansering sker för varannan inneslutning och för vart femte undantag.

Se även

Balanserade (självbalanserande) träd:

Anteckningar

  1. ↑ D. Knut. Konsten att programmera. Sortera och sök. - S. 460.

Litteratur