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
[szerkesztés]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
[szerkeszté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
[szerkeszté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
[szerkeszté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
[szerkesztés]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
[szerkesztés]- ↑ Cikk. [2008. január 26-i dátummal az eredetiből archiválva]. (Hozzáférés: 2008. január 28.)
- ↑ Teljesítmény analízis
- ↑ Műveletek AVL-fán. [2008. április 14-i dátummal az eredetiből archiválva]. (Hozzáférés: 2008. január 28.)
További információk
[szerkesztés]
