AVL fa

Az AVL fa  egy magasságkiegyensúlyozott bináris keresőfa : minden csúcsánál a két részfa magassága legfeljebb 1-gyel tér el.

Az AVL egy rövidítés, amelyet az alkotók (szovjet tudósok) Adelson-Velsky Georgy Maksimovich és Landis Evgeny Mikhailovich első betűi alkotnak .

Maximális magasság

Egy AVL-fa maximális magassága adott számú csomóponthoz [1] :

ahol:

(felhajt)

(lekerekít)

(lekerekít).

A lehetséges magasságok száma a gyakorlatban nagyon korlátozott (32 bites címzésnél a maximális magasság 45, 48 bites címzésnél 68), ezért valószínűleg jobb előre kiszámítani a minimális szám összes értékét. csomópontok mindegyik magassághoz a Fibonacci-fa rekurzív képletével :

,

,

.

A csomópontok számának közbenső értékei megfelelnek az előző (alsó) magasságnak.

Egyensúlyozás

Egy AVL-fára vonatkozóan a csúcskiegyenlítés egy olyan művelet, amely ha a bal és a jobb oldali részfa magasságkülönbsége = 2, megváltoztatja a szülő-gyermek hivatkozásokat ennek a csúcsnak a részfájában úgy, hogy a különbség <= 1 legyen, ellenkező esetben nem változtat semmin. A jelzett eredményt az adott csúcs részfájának elforgatásával kapjuk.

4 féle forgást használnak:

1. Kis balra forgatás Ezt az elforgatást akkor használjuk, ha az a-részfa és a b-részfa magasságkülönbsége 2, és C magasság <= R magasság.

2. Nagy elforgatás balra Ezt a forgatást akkor használjuk, ha az a-részfa és a b-részfa magasságkülönbsége 2, és a c-részfa magassága > R magasság.

3. Kis jobbra forgatás Ezt az elforgatást akkor használjuk, ha az a-részfa és a b-részfa magasságkülönbsége 2, és C magasság <= L magasság.

4. Nagy jobbra forgatás Ezt a forgatást akkor használjuk, ha az a-részfa és a b-részfa magasságkülönbsége 2, és a c-részfa magassága > L magasság.

Minden esetben elegendő egyszerűen bebizonyítani, hogy a művelet a kívánt eredményhez vezet, és a teljes magasság legfeljebb 1-gyel csökken, és nem növekedhet. Szintén egy nagy pörgetés a jobb és bal oldali kis pörgetés kombinációja. A kiegyenlítési feltétel miatt a fa magassága O(log(N)), ahol N a csúcsok száma, tehát egy elem hozzáadásához O(log(N)) műveletekre van szükség.

Algoritmus egy csúcs hozzáadásához

Az egyensúlyjelzőt a továbbiakban a bal és a jobb oldali részfa magasságának különbségeként értelmezzük, és az algoritmus a fent leírt TAVLTree típuson fog alapulni. Közvetlenül a beszúráskor (lap) nulla egyenleg van hozzárendelve. A csúcsok felvételének folyamata három részből áll (ezt a folyamatot Niklaus Wirth írja le az Algoritmusok és adatstruktúrák című fejezetében):

1. Haladjon végig a keresési útvonalon, amíg meg nem győződünk arról, hogy a kulcs nincs a fában.
2. Új csúcs felvétele a fába és az ebből eredő egyensúlyi mutatók meghatározása.
3. "Visszavonul" a keresés és ellenőrzés útján az egyensúlyjelző minden csúcsánál. Ha szükséges, egyensúlyozzon.

A függvény hatására visszaadjuk, hogy a fa magassága csökkent-e vagy sem. Tegyük fel, hogy egy folyamat a bal oldali ágról visszatér a szülőhöz (a rekurzió visszamegy), akkor három eset lehetséges: { h l  - a bal oldali részfa magassága, h r  - a jobb oldali részfa magassága } Csúcs szerepeltetése a bal oldali részfában eredménye lesz

1. h l < h r : kiegyenlíti h l = h r . Semmit sem kell tenni.
2. h l = h r : most a bal oldali részfa eggyel nagyobb lesz, de a kiegyenlítés még nem szükséges.
3. h l > h r : most h l  - h r = 2, - kiegyensúlyozás szükséges.

A harmadik helyzetben meg kell határozni a bal oldali részfa egyensúlyát. Ha ennek a csúcsnak a bal oldali részfája (Tree^.left^.left) magasabb, mint a jobb oldali (Tree^.left^.right), akkor nagy jobbra forgatás szükséges, különben elég egy kicsi jobb oldali. Hasonló (szimmetrikus) érvelés adható a jobb oldali részfába való beillesztéshez.

Algoritmus egy csúcs törléséhez

Az egyszerűség kedvéért leírunk egy rekurzív törlési algoritmust. Ha a csúcs egy levél, akkor töröljük, és felhívjuk az összes őse kiegyensúlyozását a szülőtől a gyökérig. Ellenkező esetben a legnagyobb magasságú részfában (jobbra vagy balra) megkeressük az értékben legközelebb eső csúcsot, és az eltávolítási eljárás meghívása közben a törölni kívánt csúcs helyére mozgatjuk.

Bizonyítsuk be, hogy ez az algoritmus megőrzi az egyensúlyt. Ehhez a fa magasságán végzett indukcióval igazoljuk, hogy a fáról néhány csúcs eltávolítása és az azt követő kiegyenlítés után a fa magassága legfeljebb 1-gyel csökken. Az indukció alapja: Levélre ez nyilvánvalóan igaz. Indukciós lépés: vagy a gyökér egyensúlyi feltétele (törlés után a gyökér megváltozhat) nem sérül, akkor az adott fa magassága nem változott, vagy a szigorúan kisebb részfa csökkent => a kiegyenlítés előtti magasság nem változott => ezután legfeljebb 1-gyel fog csökkenni.

Nyilvánvaló, hogy ezen műveletek eredményeként az eltávolítási eljárást legfeljebb 3 alkalommal hívják meg, mivel a második hívás által eltávolított csúcs nem rendelkezik az egyik részfával. De a legközelebbi megtalálásához minden alkalommal O(N) műveletre van szükség. Nyilvánvalóvá válik az optimalizálás lehetősége: a legközelebbi csúcs keresése végrehajtható a részfa éle mentén, ami a komplexitást O(log(N)-ra csökkenti).

Nem rekurzív felülről lefelé történő beszúrás egy AVL fába

A nem rekurzív algoritmus bonyolultabb, mint a rekurzív.

1. Megtalálható a beszúrási pont és a csúcs, amelynek magassága nem változik a beillesztés során (ez az a csúcs, amelynél a bal oldali részfa magassága nem egyenlő a jobb oldali részfa magasságával, ezt nevezzük PrimeNode-nak)
2. A PrimeNode-ról a beszúrási pontra való leereszkedés az egyenlegek megváltoztatásával történik
3. Túlcsordulás esetén a PrimeNode újraegyensúlyoz

Nem rekurzív törlés egy AVL-fa tetejétől lefelé

A törlés megvalósításához ugyanazon az elven járunk el, mint a beszúrásnál: találunk egy olyan csúcsot, amelyből a törlés nem vezet magasságának változásához. Két eset van:

1. a bal oldali részfa magassága megegyezik a jobb oldali részfa magasságával (kivéve, ha a levélben nincs részfa)
2. a fa mozgási irányú magassága kisebb, mint az ellenkezője (az irány „testvére”), a „testvér” egyensúlya pedig 0 (ezen lehetőség elemzése meglehetősen bonyolult, így még nincs bizonyíték)

A könnyebb érthetőség kedvéért a fenti algoritmus nem tartalmaz optimalizálást. A rekurzív algoritmustól eltérően a talált eltávolított csúcsot a bal oldali alág értékével helyettesítjük. Ez az algoritmus ugyanúgy optimalizálható, mint a rekurzív (annak köszönhetően, hogy az eltávolítandó csúcs megtalálása után ismert a mozgás iránya):

1. keressük a törlendő elemet, és útközben megtaláljuk a csodálatos felsőnket
2. egyenlegeket változtatunk, szükség esetén újraegyensúlyozást végzünk
3. töröljük az elemünket (valójában nem töröljük, hanem lecseréljük a kulcsát és az értékét, a csúcsok permutációinak elszámolása kicsit bonyolultabb lesz)

Egyenlegek rendezése eltávolításkor

Mint már említettük, ha a törölni kívánt csúcs egy levél, akkor az törlődik, és a fa fordított bejárása a törölt levél szülőjétől történik. Ha nem levél, akkor „helyettesítést” találnak neki, és a fa fordított bejárása a „helyettesítő” szülőtől származik. Közvetlenül az elem eltávolítása után - a "csere" megkapja az eltávolított csomópont egyenlegét.

Fordított kitérőben: ha a szülőhöz való áttérés során balról érkeztek, az egyenleg 1-gyel nő, ha jobbról, akkor 1-gyel csökken.

Ez addig történik, amíg az egyensúly -1-re vagy 1-re nem változik (figyeljük meg a különbséget egy elem beszúrásával!): ebben az esetben egy ilyen egyensúlyváltozás a részfák állandó deltamagasságát jelezné. A forgatás ugyanazokat a szabályokat követi, mint a beillesztéskor.

Egyenlegek elrendezése egyetlen fordulaton

Jelöli:

• "Aktuális" - olyan csomópont, amelynek egyenlege -2 vagy 2: vagyis az, amelyet el kell forgatni (a diagramban - a elem )
• "Pivot" - a forgástengely. +2: Az aktuális bal oldali gyermeke, −2: Az aktuális jobb gyermeke ( b elem a diagramban )

Ha az elforgatás egy elem beszúrásakor történik, akkor a Pivot egyensúlya 1 vagy −1. Ebben az esetben a forgatás után mindkettő egyenlege 0-ra van állítva. Törléskor minden más: a Pivot egyenlege 0-val is egyenlővé válhat (ez könnyen ellenőrizhető).

Íme egy összefoglaló táblázat a végső egyenlegek forgásiránytól és a Pivot csomópont kezdeti egyensúlyától való függéséről:

Dupla fordulatú mérlegek

A Pivot és a Current ugyanaz, de hozzáadódik a kör harmadik tagja. Jelöljük "Bottom"-nak: ez (dupla jobbra fordulással) Pivot bal fia, dupla balral pedig Pivot jobb fia.

Ezzel a forgatással a Bottom mindig 0 egyenleget kap, de a Pivot és Current egyenlegeinek elrendezése a kezdeti egyensúlytól függ.

Íme egy összefoglaló táblázat a végső egyenlegek forgásiránytól és az alsó csomópont kezdeti egyenlegétől való függéséről:

Teljesítményértékelés

A fenti képlet alapján egy AVL fa magassága soha nem haladja meg a tökéletesen kiegyensúlyozott fa magasságát 45%-nál nagyobb mértékben. A nagyok esetében megvan a becslés . Így az alapműveletek elvégzéséhez az összehasonlítások sorrendje szükséges. Kísérletileg azt találták, hogy minden 2 zárványra és minden 5 kivételre egy kiegyensúlyozás történik.

Lásd még

Kiegyensúlyozott (önkiegyensúlyozó) fák:

• Vörös-fekete fa
• mátrix fa
• Tökéletesen kiegyensúlyozott fa
• bővülő fa

Jegyzetek

1. ↑ D. Knut. Programozás művészete. Rendezés és keresés. - S. 460.

Irodalom

• Wirth N. Algoritmusok és adatstruktúrák. - M .: Mir, 1989. - S. 272-286.
• Adelson-Velsky G. M., Landis E. M. Egy algoritmus az információk szervezésére // Doklady AN SSSR. - 1962. - T. 146 , 2. sz . - S. 263-266 .
• Ben Pfaff. GNU libavl