Ugrás a tartalomhoz

Adatstruktúrák és algoritmusok

Házy Attila, Nagy Ferenc (2009)

5.6. AVL-fák

5.6. AVL-fák

Az AVL-fákat G.M. Adelszon-Velszkij, E.M. Landisz vezették be 1962-ben.

5.14. Definíció. AVL-fa

Egy bináris keresőfát AVL-fának nevezünk, ha a fa minden csúcsára teljesül az alábbi úgynevezett AVL tulajdonság: (kiegyensúlyozottsági feltétel).

az csúcs baloldali, a jobboldali részfáját jelöli, pedig a részfa magassága.

Jelölje a fa szintjeinek számát. (Ez eggyel nagyobb, mint a magasság). Jelölje a szintű fa csúcsainak minimális számát. Ekkor minden k 2 esetén teljesül, hogyb

5.15. Tétel.

, ahol a -dik Fibonacci szám.

Bizonyítás. és esetén a tétel nyílvánvalóan igaz.

Teljes indukcióval -re kapjuk:

5.16. Következmény.

Egy csúcsot tartalmazó AVL-fa szintjeinek számára fennáll a

egyenlőtlenség, azaz a szintszám és így a magasság is nagyságú.

Bizonyítás. A tétel alapján , azaz . A Fibonacci számokra igaz, hogy , ahol . Tehát . Innen logaritmust véve .

5.17. Tétel.

Egy csúcsból álló AVL-fa esetén egy új csúcs beszúrását követően legfeljebb egy (esetleg dupla) forgatással az AVL tulajdonság helyreállítható. A beszúrás költsége ezzel együtt .

Törlés után legfeljebb (szimpla vagy dupla) forgatás helyreállítja az AVL tulajdonságot.