AVL-fa

A Wikipédiából, a szabad enciklopédiából.

Kiegyensúlyozatlan fa (nem-AVL)

Ugyanez a fa kiegyensúlyozás után

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 jobb részfa magasságát a bal 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 vörös-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]

[szerkesztés] 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.

[szerkesztés] 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.

A lehetséges forgatások egy AVL-fában

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.

[szerkesztés] 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.

[szerkesztés] 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.

[szerkesztés] Összehasonlítás más struktúrákkal

Az AVL- és Vörös-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. Az egyetlen különbség a kettő közt a magasságkorlát. n elem esetén: