6.6. AVL-fa

Történetileg a piros-fekete fák kifejlesztését megelőzte az AVL-fák kifejlesztése. Az AVL elnevezés a szerzők neveinek rövidítéséből származik (Adelszon, Velszkij és Landisz). Egy fa magasságán a gyökértől levelekig tartó utak maximális hosszát értjük. Ez induktív definícióval a következőképpen fogalmazható meg:

– Üres fa magassága 0.

– Az egy gyökérből álló fa magassága 1.

– Az egynél több csúcsból álló fa magassága eggyel nagyobb, mint a magasabb részfájának magassága.

AVL-fának nevezünk minden olyan bináris keresőfát, melyben a bal- és jobboldali részfák magasságának különbsége abszolút értékben egyetlen csúcsnál sem haladja meg az 1-et.

6.6.1. Forgatások

Az AVL-beszúrás és AVL-törlés ugyancsak a naív beszúrásra és naív törlésre épít. A piros-fekete fákhoz hasonlóan itt is forgatással lehet az AVL-tulajdonságot helyreállítani. Attól függően, hogy hol és mennyire sérül az AVL tulajdonság, négy különböző forgatást kell használni. Az alábbi ábrákon található zöld számok az adott csúcs jobboldali részfája magasságának és baloldali részfája magasságának különbsége. A 6.6.1. ábrán az első esetben jobbraforgatást, a második esetben balraforgatást kell alkalmazni, hogy az AVL tulajdonság helyreálljon. A 6.6.2. ábrán az első esetben ez egy x körüli balraforgatással, majd egy z körüli jobbraforgatással, míg a második esetben ez egy z körüli jobbraforgatással, majd egy x körüli balraforgatással érhető el. Mindkét esetben a végeredmény a 6.6.3. ábrán látható. Mind a beszúrásnál, mind a törlésnél a beszúrt, illetve törölt csúcstól a gyökér fele vezető úton található csúcsokra ellenőrizni kell az AVL-tulajdonság meglétét.

6.12. ábra - 6.6.1. ábra Egyszeres forgatások

6.6.1. ábra Egyszeres forgatások


6.13. ábra - 6.6.2. ábra. Kétszeres forgatások

6.6.2. ábra. Kétszeres forgatások


6.14. ábra - 6.6.3. ábra. Kétszeres forgatások végeredménye

6.6.3. ábra. Kétszeres forgatások végeredménye


Az AVL fák algoritmusának kódja igen hosszú, ezért itt nem részletezzük. Az interneten majd minden programnyelvre megtalálható valamely megvalósítása.

6.4. példa - 12. példa

Alábbiakban az látható, hogy hogyan szúrhatjuk be egy üres AVL-fába sorban a 7, 9, 3, 5, 4, 2, 1, 6 és 8 számokat, majd sorra ugyanezeket töröljük is.

6.15. ábra - 6.6.4. ábra A 7, 9, 3 és 5 beszúrása

6.6.4. ábra A 7, 9, 3 és 5 beszúrása


6.16. ábra - 6.6.5. ábra A 4 naiv beszúrása

6.6.5. ábra A 4 naiv beszúrása


A pirossal jelölt mezők jelzik azt, ahol az AVL-tulajdonság nem áll fenn. A 3-at és a 7-et tartalmazó csúcsok miatt nem AVL-fa a fa. Az 5-öt tartalmazó csúcsnál ez az érték az irányítást is figyelembe véve −1, így 3-at tartalmazó csúcs gyökerű fára kell alkalmazni a kétszeres forgatást.

6.17. ábra - 6.6.6. ábra A forgatás után helyreáll az AVL-tulajdonság

6.6.6. ábra A forgatás után helyreáll az AVL-tulajdonság


A 2 beszúrásával az AVL tulajdonság újra sérül, s mivel a négyet tartalmazó csúcshoz tartozó különbség −1, most egyszeres forgatásra lesz szükség.

6.18. ábra - 6.6.7. ábra A 2 naív beszúrásával ismét sérül az AVL-tulajdonság

6.6.7. ábra A 2 naív beszúrásával ismét sérül az AVL-tulajdonság


6.19. ábra - 6.6.8. ábra Forgatással megint helyreállítható

6.6.8. ábra Forgatással megint helyreállítható


6.20. ábra - 6.6.9. ábra Az 1 naív beszúrásával ismét sérül az AVL-tulajdonság

6.6.9. ábra Az 1 naív beszúrásával ismét sérül az AVL-tulajdonság


6.21. ábra - 6.6.10. ábra Megint egy egyszeres forgatásra van szükség

6.6.10. ábra Megint egy egyszeres forgatásra van szükség


6.22. ábra - 6.6.11. ábra 6 és 8 beszúrása

6.6.11. ábra 6 és 8 beszúrása


6.23. ábra - 6.6.12. ábra A 9 törlése és a helyreállítás

6.6.12. ábra A 9 törlése és a helyreállítás


6.24. ábra - 6.6.13. ábra 3 és 5 törlése

6.6.13. ábra 3 és 5 törlése


6.25. ábra - 6.6.14. ábra 2, 1 és 6 törlése

6.6.14. ábra 2, 1 és 6 törlése