Az AVL Tree-t a GM Adelson - Velsky és az EM Landis találta fel 1962-ben. A fát feltalálói tiszteletére AVL-nek nevezték el.
Az AVL Tree magassággal kiegyensúlyozott bináris keresőfaként definiálható, amelyben minden csomópont hozzá van rendelve egy egyensúlyi tényezőhöz, amelyet úgy számítanak ki, hogy a jobb oldali részfa magasságát kivonják a bal oldali részfáéból.
egyesítése rendezés java
A fa kiegyensúlyozottnak tekinthető, ha az egyes csomópontok egyensúlytényezője -1 és 1 között van, ellenkező esetben a fa kiegyensúlyozatlan lesz, és ki kell egyensúlyozni.
Egyensúlytényező (k) = magasság (bal (k)) - magasság (jobb (k))
Ha bármely csomópont egyensúlyi tényezője 1, az azt jelenti, hogy a bal oldali részfa egy szinttel magasabb, mint a jobb oldali részfa.
Ha bármely csomópont egyensúlyi tényezője 0, az azt jelenti, hogy a bal oldali részfa és a jobb oldali részfa azonos magasságú.
Ha bármely csomópont egyensúlytényezője -1, az azt jelenti, hogy a bal oldali részfa egy szinttel alacsonyabb, mint a jobb oldali részfa.
A következő ábrán egy AVL fa látható. Láthatjuk, hogy az egyes csomópontokhoz tartozó egyensúlytényező -1 és +1 között van. ezért ez egy példa az AVL fára.
Bonyolultság
| Algoritmus | Átlagos eset | Legrosszabb esetben |
|---|---|---|
| Hely | tovább) | tovább) |
| Keresés | o(log n) | o(log n) |
| Beszúrás | o(log n) | o(log n) |
| Töröl | o(log n) | o(log n) |
Műveletek az AVL fán
Tekintettel arra, hogy az AVL fa egyben bináris keresőfa is, minden műveletet ugyanúgy hajtanak végre, mint egy bináris keresőfában. A keresés és a bejárás nem vezet az AVL fa tulajdonságainak megsértéséhez. Azonban a beillesztés és a törlés azok a műveletek, amelyek sérthetik ezt a tulajdonságot, ezért ezeket újra meg kell vizsgálni.
| SN | Művelet | Leírás |
|---|---|---|
| 1 | Beillesztés | Az AVL fába történő beillesztés ugyanúgy történik, mint a bináris keresési fában. Ez azonban az AVL-fa tulajdonság megsértéséhez vezethet, ezért előfordulhat, hogy a fát ki kell egyensúlyozni. A fa forgatással egyensúlyba hozható. |
| 2 | Törlés | A törlés ugyanúgy végrehajtható, mint a bináris keresési fában. A törlés a fa egyensúlyát is megzavarhatja, ezért különféle forgatásokat alkalmaznak a fa egyensúlyának helyreállítására. |
Miért AVL Tree?
Az AVL-fa szabályozza a bináris keresési fa magasságát úgy, hogy nem engedi, hogy elferdüljön. A h magasságú bináris keresési fa összes műveletéhez szükséges idő O(h) . Ez azonban kiterjeszthető arra Tovább) ha a BST elferdül (azaz a legrosszabb eset). Ha ezt a magasságot log n-re korlátozza, az AVL fa felső korlátot ír elő minden egyes be műveletre O(log n) ahol n a csomópontok száma.
AVL forgások
Az AVL fában csak abban az esetben végezzük el a forgatást, ha a Balance Factor nem -1, 0 és 1 . Alapvetően négyféle forgatás létezik, amelyek a következők:
- L L forgatás: A beszúrt csomópont az A bal oldali részfájának bal részfájában található
- R R forgatás: A beszúrt csomópont az A jobb oldali részfájának jobb oldali részfájában található
- L R elforgatás: A beszúrt csomópont az A bal oldali részfájának jobb oldali részfájában található
- R L forgatás: A beszúrt csomópont az A jobb oldali részfájának bal oldali részfájában található
Ahol az A csomópont az a csomópont, amelynek egyensúlyi tényezője nem -1, 0, 1.
Az első két forgás LL és RR egyszeres, a következő két LR és RL forgatás kettős forgatás. Ahhoz, hogy egy fa kiegyensúlyozatlan legyen, a minimális magasságnak legalább 2-nek kell lennie. Értsük meg az egyes forgatásokat
1. RR forgatás
Amikor a BST kiegyensúlyozatlanná válik, amiatt, hogy az A jobb oldali részfájába egy csomópont kerül be, akkor RR forgatást hajtunk végre, az RR forgatás az óramutató járásával ellentétes forgatás, amelyet a -2 egyensúlyi tényezőjű csomópont alatti élre alkalmazunk.
A fenti példában az A csomópont egyensúlyi tényezője -2, mert a C csomópont az A jobb oldali részfa jobb oldali részfájába van beillesztve. Az RR forgatást az A alatti élen hajtjuk végre.
2. LL forgás
Amikor a BST kiegyensúlyozatlanná válik, amiatt, hogy a C bal oldali részfájába egy csomópont kerül be, akkor LL forgatást hajtunk végre, az LL forgatás az óramutató járásával megegyező forgatás, amelyet egy 2-es egyensúlytényezővel rendelkező csomópont alatti élre alkalmazunk.
A fenti példában a C csomópont 2-es egyensúlyi tényezővel rendelkezik, mivel egy A csomópont be van illesztve a C bal részfa bal oldali részfájába. Az LL forgatást az A alatti élen végezzük.
3. LR forgatás
A kettős forgatás kissé keményebb, mint az egyszeri forgatás, amit fentebb már kifejtettünk. LR forgatás = RR forgatás + LL elforgatás, azaz először az RR forgatást részfán, majd az LL forgatást teljes fán hajtjuk végre, teljes fa alatt a beillesztett csomópont útvonalának első csomópontját értjük, amelynek egyensúlyi tényezője nem -1 , 0 vagy 1.
Értsünk meg minden egyes lépést nagyon világosan:
| Állapot | Akció |
|---|---|
 | Az A jobb oldali részfájába a C bal oldali részfájába egy B csomópont került be, ami miatt C 2-es egyensúlytényezővel rendelkező kiegyensúlyozatlan csomópont lett. Ez az eset L R elforgatás, ahol: A beszúrt csomópont a bal oldali részfájának jobb oldali részfájában található. C |
 | Mivel LR forgatás = RR + LL forgatás, ezért először az RR-t (óramutató járásával ellentétes irányba) hajtjuk végre az A-ban gyökerező részfán. RR rotációval, csomópont A , a bal oldali részfája lett B . |
 | Az RR forgatás végrehajtása után a C csomópont továbbra is kiegyensúlyozatlan, azaz 2-es egyensúlytényezővel rendelkezik, mivel a beillesztett A csomópont a bal vagy bal oldalon található. C |
 | Most a teljes fán, azaz a C. csomóponton végezzük az LL óramutató járásával megegyező forgatást C most a B csomópont jobb oldali részfája lett, A pedig a B csomópont bal oldali részfája |
 | Az egyes csomópontok egyensúlytényezője most vagy -1, 0 vagy 1, azaz a BST most kiegyensúlyozott. |
4. RL forgatás
Mint már említettük, ez a kettős forgatás valamivel keményebb, mint az egyszeres forgatás, amelyet fentebb már kifejtettünk. RL forgatás = LL forgatás + RR forgatás, azaz először az LL forgatást részfán, majd az RR forgatást teljes fán hajtjuk végre, teljes fa alatt a beillesztett csomópont útvonalának első csomópontját értjük, amelynek egyensúlyi tényezője nem -1 , 0 vagy 1.
| Állapot | Akció |
|---|---|
 | Egy csomópont B bekerült a bal oldali részfájába C a jobb oldali részfa A , ami miatt A kiegyensúlyozatlan csomóponttá vált, amelynek egyensúlyi tényezője - 2. Ez az eset az RL forgatás, ahol: A beszúrt csomópont az A jobb oldali részfájának bal oldali részfájában található |
 | Mivel RL elforgatás = LL elforgatás + RR elforgatás, ezért LL (óramutató járásával megegyezően) a részfán gyökerezve C először kerül végrehajtásra. RR rotációval, csomópont C a megfelelő részfája lett B . |
 | Az LL forgatás végrehajtása után a csomópont A még mindig kiegyensúlyozatlan, azaz -2 egyensúlytényezővel rendelkezik, ami az A jobb oldali részfa csomópont jobb részfájának köszönhető. |
 | Most RR forgatást (óramutató járásával ellentétes forgatást) hajtunk végre teljes fán, azaz az A csomóponton. C most a B csomópont jobb oldali részfája lett, az A csomópont pedig a B csomópont bal oldali részfája. |
 | Az egyes csomópontok egyensúlytényezője most vagy -1, 0 vagy 1, azaz a BST most kiegyensúlyozott. |
K: Hozzon létre egy AVL fát a következő elemekkel
H, I, J, B, A, E, C, F, D, G, K, L
1. Szúrja be a H, I, J jeleket
A fenti elemek beillesztésekor, különösen H esetén, a BST kiegyensúlyozatlanná válik, mivel a H egyensúlytényezője -2. Mivel a BST jobbra ferde, RR-elforgatást fogunk végrehajtani a H csomóponton.
Az eredményül kapott mérlegfa a következő:
2. Szúrja be a B, A jeleket
cserélje ki a karakterláncot java-ban
A fenti elemek beillesztésekor, különösen A esetén, a BST kiegyensúlyozatlanná válik, mivel H és I egyensúlytényezője 2, ezért az utoljára beillesztett csomópont első csomópontját, azaz H-t vesszük figyelembe. Mivel a H-ból származó BST balra ferde, LL forgatást hajtunk végre a H csomóponton.
Az eredményül kapott mérlegfa a következő:
3. Illessze be az E-t
css-ben lebeg
Az E beszúrásakor a BST kiegyensúlyozatlanná válik, mivel az I egyensúlytényezője 2, mivel ha E-ből I-be utazunk, azt találjuk, hogy az I jobb oldali részfájának bal oldali részfájába van beillesztve, akkor LR forgatást hajtunk végre az I csomóponton. LR = RR + LL forgás
3 a) Először RR forgatást hajtunk végre a B csomóponton
Az eredményül kapott fa RR forgatás után a következő:
3b) Először LL forgatást végzünk az I csomóponton
Az eredményül kapott kiegyensúlyozott fa LL forgatás után:
4. C, F, D beszúrása
C, F, D beszúrásakor a BST kiegyensúlyozatlanná válik, mivel B és H egyensúlytényezője -2, mivel ha D-ből B-be utazunk, azt találjuk, hogy a B bal oldali részfájának jobb oldali részfájába van beillesztve, akkor végrehajtjuk. RL Forgatás az I. csomóponton. RL = LL + RR forgás.
4a) Először LL forgatást hajtunk végre az E csomóponton
Az eredményül kapott fa LL forgatás után a következő:
4b) Ezután végrehajtjuk az RR forgatást a B csomóponton
c kód abs
Az eredményül kapott kiegyensúlyozott fa RR forgatás után:
5. Illessze be a G-t
G beszúrásakor a BST kiegyensúlyozatlanná válik, mivel a H egyensúlytényezője 2, mivel ha G-ből H-ba utazunk, azt találjuk, hogy a H jobb oldali részfájának bal oldali részfájába illesztjük be, akkor az I csomóponton LR-elforgatást hajtunk végre. LR = RR + LL forgás.
5 a) Először RR forgatást hajtunk végre a C csomóponton
Az eredményül kapott fa RR forgatás után a következő:
5 b) Ezután LL forgatást végzünk a H csomóponton
Az eredményül kapott kiegyensúlyozott fa LL forgatás után:
6. Illessze be a K betűt
K beszúrásakor a BST kiegyensúlyozatlanná válik, mivel az I egyensúlytényezője -2. Mivel a BST jobbra ferde I-től K-ig, ezért RR-elforgatást hajtunk végre az I csomóponton.
Az eredményül kapott kiegyensúlyozott fa RR forgatás után:
7. Illessze be az L betűt
Beszúrásakor az L fa továbbra is kiegyensúlyozott, mivel az egyes csomópontok egyensúlytényezője most vagy -1, 0, +1. Ezért a fa egy Balanced AVL fa
