AVL-fa

A számítógép-tudományban az AVL-fa alatt egy ön-kiegyensúlyozó bináris keresőfát értünk. Ez volt az első ilyen adatszerkezet. Egy AVL-fában bármely csúcspont két részfájának magassága közti különbség legfeljebb egy. Kiegyensúlyozott-magasságúnak is hívják az ilyen struktúrákat. A keresés, beillesztés és törlés egyaránt O(log n) nagyságrendű időt vesz igénybe, még a legrosszabb esetben is. Beillesztés és törlés esetén szükséges lehet forgatások alkalmazásával újra kiegyensúlyozni a fát.

Az AVL-fa nevét két feltalálójáról G. M. Adelson-Velsky-ről és E. M. Landis-ról kapta, akik 1963-ban publikálták^[1] An algorithm for the organization of information (Egy algoritmus az információ szervezettségéhez) című cikkükben.

Minden csúcsnak van egy ún. egyensúly-faktora, amit megkapunk, ha kivonjuk a bal részfa magasságát a jobb részfáéból. Egy csúcs kiegyensúlyozott, ha ez az érték 1, 0 vagy -1. Minden más esetben a csúcs kiegyensúlyozatlan és forgatásokat igényel.

Az AVL-fákat gyakran hasonlítják össze a piros-fekete fákkal, mivel azonos műveleteket valósítanak meg és ezekre az O(log n) futásidő jellemző. Gyakori keresést igénylő alkalmazásokban az AVL-fa hatékonyabb^[2]

Műveletek

Az egyes műveletek megegyeznek egy kiegyensúlyozatlan bináris fán végrehajtottakkal, de kiegészülhetnek egy vagy több forgatással, amik a fa egyensúlyát hivatottak megtartani.

Beillesztés

Miután beillesztettük az elemet a megfelelő helyre ki kell számolnunk annak egyensúly-faktorát. Ha ez az érték 1, 0 vagy -1, akkor a fa egyensúlya megmaradt és nincs szükség forgatásra.

Ha az egyensúly faktor 2 vagy -2 a fa egyensúlya megsérült és forgatásokra van szükség, hogy helyreállítsuk azt. Általában egy vagy két forgatás elég ehhez.

Négyféle forgatást különböztetünk meg, ezek közül kettő tükörképe a másik kettőnek. Legyen például a kiegyensúlyozatlan részfa P, a jobb gyermeke Q, a bal pedig O. Ha P egyensúly-faktora 2, akkor az azt jelenti, hogy a jobb oldali részfában van a hiba. Ha Q faktora 1, akkor a beillesztés a jobb (külső) oldalon történt meg és egy bal-forgatás szükséges (P a gyökérelem). Ha Q egyensúlya -1 akkor a beillesztés a bal (belső) oldalon történt meg, ekkor egy kétszeres forgatásra van szükség. Először jobbra forgatunk (Q a gyökérelem), aztán balra (P a gyökér).

A másik két eset hasonló, ott az egyensúly-faktor -2 és a bal oldali részfa bontja meg az egyensúlyt.^[3]

A forgatás konstans idejű művelet, és mivel a fa magassága limitált a beillesztés O(log n) nagyságrendű időt igényel.

Törlés

Ha a törlendő csúcs levél, egyszerűen töröljük. Minden más esetben kivágjuk a bal részfa legnagyobb vagy a jobb részfa legkisebb elemét és a törlendő elem helyére illesztjük. Ezután visszamegyünk a fán (a törölt elem szülőjéig) és újraszámoljuk a fa egyensúlyát. A visszakövetés leáll, ha az egyensúly 1 vagy -1. Ha a faktor 0, azt jelzi, hogy a részfa magassága eggyel csökkent, és folytatódik a művelet. Ha az egyensúly 2 vagy -2, az egyensúly megsérült és forgatásokra van szükség. Ha a forgatás után az egyensúly 0 a követés folytatódik, mivel a részfa magassága eggyel csökkent. Ez ellentétes a beillesztéssel, mivel ott a 0 azt jelzi, hogy a fa magassága nem változott.

A törlendő elem kiválasztása O(log(n)) nagyságrendű, míg a visszakövetésé maximum O(log(h)), ezért a törlés O(log n) nagyságrendű művelet.

Keresés

A keresés hasonlóan zajlik, mint egy kiegyensúlyozatlan fa esetében. Mivel az AVL-fa kiegyensúlyozott a keresés O(log n) nagyságrendű művelet. A keresés során nincs szükség a fa módosítására.

Összehasonlítás más struktúrákkal

Az AVL- és Piros-fekete fák egyaránt önkiegyensúlyozók, ezért matematikailag hasonlóak. Az egyensúlyozás különböző módon történik, de mindkét esetben konstans időben. A különbség a kettő közt a magasságkorlát. n elem esetén:

• az AVL-fa magassága maximum 1.44 * log n
• a Piros-fekete fa magassága 2 * log n

A Piros-fekete fánál a beszúrást lehet gyorsítani, ha egyszerre keresem a beszúrandó elem helyét és egyensúlyozom ki.

A beszúrás, törlés és keresés mindkét fánál O(log n) nagyságrendű, de rosszabb esetekben az AVL-fa valamivel gyorsabb.

Források

További információk

A Wikimédia Commons tartalmaz AVL-fa témájú médiaállományokat.

• Demonstrációs programok AVL fák esetén
• Bináris keresőfák, AVL-fák
• Animáció AVL-fákhoz