Mi az AVL fa?
Az AVL fa a bináris keresőfa egyik altípusa. A feltalálói, Adelson, Velskii és Landis nevét viselik, az AVL fák a bináris kereső fák által mutatott összes tulajdonság mellett dinamikus önkiegyensúlyozással is rendelkeznek.
A BST egy csomópontokból álló adatstruktúra. A következő garanciákkal rendelkezik:
- Minden fának van egy gyökércsomópontja (a tetején).
- A gyökércsomópontnak nulla, egy vagy két gyermekcsomópontja van.
- Minden gyermekcsomópontnak nulla, egy vagy két gyermekcsomópontja van, és így tovább.
- Minden csomópontnak legfeljebb két gyermeke van.
- Minden csomópontnál a bal leszármazottai kisebbek, mint a jelenlegi csomópontok, ami kevesebb, mint a jobb oldali leszármazottaké.
Az AVL fákra további garancia vonatkozik:
- A jobb és a bal részfa mélysége közötti különbség nem lehet egynél több. E garancia fenntartása érdekében az AVL megvalósítása magában foglal egy algoritmust a fa egyensúlyának helyreállítására, amikor egy további elem hozzáadása felborítaná ezt a garanciát.
Az AVL fák a legrosszabb esetben keresik, beillesztik és törlik az O (log n) idejét.
Jobb elforgatás
Balra forgatás
AVL beillesztési folyamat
A normál bináris keresési fa beszúrásához hasonló beillesztést fog végrehajtani. A behelyezés után az AVL tulajdonságot bal vagy jobb forgatással javítja.
- Ha a jobb alfa bal gyermekében egyensúlyhiány van, akkor bal-jobb forgatást hajt végre.
- Ha a bal alfa bal gyermekében egyensúlyhiány van, akkor jobbra forgat.
- Ha a jobb alfa jobb gyermekénél van egyensúlyhiány, akkor bal forgatást hajt végre.
- Ha a bal alfa jobb gyermekében van egyensúlyhiány, akkor a jobb-bal forgatást hajtja végre.
Az AVL fa egy önkiegyensúlyozó bináris kereső fa. Az AVL fa egy bináris keresőfa, amelynek a következő tulajdonságai vannak: -> Minden csomópont alfái magasságban legfeljebb egy magassággal térnek el. -> Minden alfa egy AVL fa.
Az AVL fa ellenőrzi a bal és a jobb alfa magasságát, és biztosítja, hogy a különbség legfeljebb 1 legyen. Ezt a különbséget Balance Factor-nak nevezzük. Az AVL fa magassága mindig O (Logn), ahol n a fa csomópontjainak száma.
AVL Tree Rotations
Az AVL fában minden olyan művelet elvégzése után, mint a beillesztés és törlés, ellenőriznünk kell a fa minden csomópontjának egyensúlyi tényezőjét. Ha minden csomópont megfelel az egyensúlyi tényező feltételének, akkor befejezzük a műveletet, különben kiegyensúlyozottá kell tennünk. Forgatási műveletek segítségével a fa kiegyensúlyozottá válik, amikor a fa bármilyen művelet miatt egyensúlytalanná válik.
Forgatási műveletekkel a fa kiegyensúlyozottá válik. Négy forgatás van, és két típusba sorolhatók:
Egyetlen bal forgatás (LL forgatás)
Az LL forgatásban minden csomópont egy pozícióval balra mozog az aktuális pozícióból.
Egyetlen jobb elforgatás (RR forgatás)
Az RR forgatásban minden csomópont egy pozícióval jobbra mozog az aktuális pozícióból.
Balra jobbra forgatás (LR forgatás)
Az LR Rotation az egyetlen bal forgatás, majd az egyszeres jobb forgatás kombinációja. Az LR forgatásban először minden csomópont egy pozíciót balra, majd egy pozíciót jobbra mozgat az aktuális pozícióból.
Jobb bal forgatás (RL forgatás)
Az RL elforgatás egyetlen jobb elfordítás, majd egyszeri bal elforgatás kombinációja. Az RL forgatásnál először minden csomópont egy pozíciót jobbra, majd egy pozíciót balra mozgat az aktuális pozícióból.
Az AVL fák időelemzése
Az AVL fa egy bináris keresőfa, amely további tulajdonságokkal rendelkezik, amelyek szerint a csomópont bal és a jobb alfa fája közötti különbség nem lehet nagyobb, mint 1.
Algoritmus átlaga Legrosszabb eset: Hely:, O(n)Idő:O(n)
AVL fák alkalmazása
Az AVL fák előnyösek azokban az esetekben, amikor olyan adatbázist tervez, ahol a beillesztések és törlések nem olyan gyakoriak, de gyakran meg kell keresni az ott található elemeket.