TechCodeview

AVL stablo izumili su GM Adelson - Velsky i EM Landis 1962. Stablo je nazvano AVL u čast svojih izumitelja.

AVL stablo može se definirati kao visinski uravnoteženo binarno stablo pretraživanja u kojem je svaki čvor povezan s faktorom ravnoteže koji se izračunava oduzimanjem visine desnog podstabla od visine lijevog podstabla.

Kaže se da je stablo uravnoteženo ako je faktor ravnoteže svakog čvora između -1 i 1, inače će stablo biti neuravnoteženo i trebat će ga uravnotežiti.

Faktor ravnoteže (k) = visina (lijevo (k)) - visina (desno (k))

Ako je faktor ravnoteže bilo kojeg čvora 1, to znači da je lijevo podstablo za jednu razinu više od desnog podstabla.

Ako je faktor ravnoteže bilo kojeg čvora 0, to znači da lijevo podstablo i desno podstablo imaju jednaku visinu.

Ako je faktor ravnoteže bilo kojeg čvora -1, to znači da je lijevo podstablo jednu razinu niže od desnog podstabla.

AVL stablo je dano na sljedećoj slici. Možemo vidjeti da je faktor ravnoteže povezan sa svakim čvorom između -1 i +1. dakle, to je primjer AVL stabla.

Složenost

Operacije na AVL stablu

Zbog činjenice da je AVL stablo također binarno stablo pretraživanja, stoga se sve operacije izvode na isti način kao što se izvode u binarnom stablu pretraživanja. Pretraživanje i prelaženje ne dovode do kršenja svojstva AVL stabla. Međutim, umetanje i brisanje su operacije koje mogu narušiti ovo svojstvo i stoga ih je potrebno ponovno pregledati.

Zašto AVL Tree?

AVL stablo kontrolira visinu binarnog stabla pretraživanja ne dopuštajući da bude iskrivljeno. Vrijeme potrebno za sve operacije u binarnom stablu pretraživanja visine h je Oh) . Međutim, može se proširiti na Na) ako BST postane iskrivljen (tj. najgori slučaj). Ograničavanjem ove visine na log n, AVL stablo nameće gornju granicu za svaku operaciju koja treba biti O(log n) gdje je n broj čvorova.

AVL rotacije

Vršimo rotaciju u AVL stablu samo u slučaju ako je faktor ravnoteže različit od -1, 0 i 1 . U osnovi postoje četiri vrste rotacija koje su sljedeće:

1. L L rotacija: Umetnuti čvor je u lijevom podstablu lijevog podstabla A
2. R R rotacija: Umetnuti čvor je u desnom podstablu desnog podstabla A
3. L R rotacija: Umetnuti čvor je u desnom podstablu lijevog podstabla A
4. R L rotacija: Umetnuti čvor je u lijevom podstablu desnog podstabla A

Gdje je čvor A čvor čiji faktor ravnoteže nije -1, 0, 1.

Prve dvije rotacije LL i RR su pojedinačne rotacije, a sljedeće dvije rotacije LR i RL su dvostruke rotacije. Da bi stablo bilo neuravnoteženo, minimalna visina mora biti najmanje 2. Razumimo svaku rotaciju

1. RR rotacija

Kada BST postane neuravnotežen, zbog umetanja čvora u desno podstablo desnog podstabla A, tada izvodimo RR rotaciju, RR rotacija je rotacija u smjeru suprotnom od kazaljke na satu, koja se primjenjuje na rubu ispod čvora koji ima faktor ravnoteže -2

U gornjem primjeru, čvor A ima faktor ravnoteže -2 jer je čvor C umetnut u desno podstablo desnog podstabla A. Vršimo RR rotaciju na rubu ispod A.

2. LL Rotacija

Kada BST postane neuravnotežen, zbog umetanja čvora u lijevo podstablo lijevog podstabla C, tada izvodimo LL rotaciju, LL rotacija je rotacija u smjeru kazaljke na satu, koja se primjenjuje na rubu ispod čvora koji ima faktor ravnoteže 2.

U gornjem primjeru, čvor C ima faktor ravnoteže 2 jer je čvor A umetnut u lijevo podstablo C lijevog podstabla. Vršimo LL rotaciju na rubu ispod A.

3. LR rotacija

Dvostruke rotacije su malo teže od jednostruke rotacije što je već objašnjeno gore. LR rotacija = RR rotacija + LL rotacija, tj. prvo se RR rotacija izvodi na podstablu, a zatim LL rotacija se izvodi na punom stablu, pod punim stablom mislimo na prvi čvor s putanje umetnutog čvora čiji faktor ravnoteže nije -1 , 0 ili 1.

Razumimo svaki korak vrlo jasno:

država	Akcijski
	Čvor B je umetnut u desno podstablo A lijevo podstablo C, zbog čega je C postao neuravnotežen čvor s faktorom ravnoteže 2. Ovaj slučaj je L R rotacija gdje je: Umetnuti čvor je u desnom podstablu lijevog podstabla C
	Kako je LR rotacija = RR + LL rotacija, stoga se prvo izvodi RR (u smjeru suprotnom od kazaljke na satu) na podstablu s korijenom u A. Radeći RR rotaciju, čvor A , postalo je lijevo podstablo od B .
	Nakon izvođenja RR rotacije, čvor C je još uvijek neuravnotežen, tj. ima faktor ravnoteže 2, budući da je umetnuti čvor A lijevo od lijevo od C
	Sada izvodimo LL rotaciju u smjeru kazaljke na satu na punom stablu, tj. na čvoru C. čvor C sada je postalo desno podstablo čvora B, A je lijevo podstablo B
	Faktor ravnoteže svakog čvora sada je -1, 0 ili 1, tj. BST je sada uravnotežen.

4. RL rotacija

Kao što je već spomenuto, dvostruke rotacije su malo teže od jednostruke rotacije što je već objašnjeno gore. R L rotacija = LL rotacija + RR rotacija, tj. prvo se LL rotacija izvodi na podstablu, a zatim RR rotacija se izvodi na punom stablu, pod punim stablom mislimo na prvi čvor s putanje umetnutog čvora čiji faktor ravnoteže nije -1 , 0 ili 1.

država	Akcijski
	čvor B je umetnuto u lijevo podstablo od C desno podstablo od A , zbog čega je A postao neuravnoteženi čvor s faktorom ravnoteže - 2. Ovaj slučaj je RL rotacija gdje je: Umetnuti čvor je u lijevom podstablu desnog podstabla A
	Kako je RL rotacija = LL rotacija + RR rotacija, dakle, LL (u smjeru kazaljke na satu) na podstablu ukorijenjenom na C izvodi se prvi. Radeći RR rotaciju, čvor C je postalo desno podstablo od B .
	Nakon izvođenja LL rotacije, čvor A je još uvijek neuravnotežen, tj. ima faktor ravnoteže -2, što je zbog desnog podstabla čvora desnog podstabla A.
	Sada izvodimo RR rotaciju (rotaciju suprotno od kazaljke na satu) na punom stablu, tj. na čvoru A. čvor C sada je postalo desno podstablo čvora B, a čvor A je postalo lijevo podstablo B.
	Faktor ravnoteže svakog čvora sada je -1, 0 ili 1, tj. BST je sada uravnotežen.

P: Konstruirajte AVL stablo sa sljedećim elementima

H, I, J, B, A, E, C, F, D, G, K, L

1. Umetnite H, I, J

Umetanjem gornjih elemenata, posebno u slučaju H, BST postaje neuravnotežen jer je faktor ravnoteže H -2. Budući da je BST zakošen udesno, izvršit ćemo RR rotaciju na čvoru H.

Rezultirajuće stablo bilance je:

2. Umetnite B, A

Nakon umetanja gornjih elemenata, posebno u slučaju A, BST postaje neuravnotežen jer je faktor ravnoteže H i I 2, uzimamo u obzir prvi čvor od posljednjeg umetnutog čvora, tj. H. Budući da je BST iz H zakošen ulijevo, izvršit ćemo LL rotaciju na čvoru H.

Rezultirajuće stablo bilance je:

3. Umetnite E

Umetanjem E, BST postaje neuravnotežen jer je faktor ravnoteže I 2, budući da ako putujemo od E do I ustanovimo da je umetnut u lijevo podstablo desnog podstabla I, izvršit ćemo LR rotaciju na čvoru I. LR = RR + LL rotacija

3 a) Prvo izvodimo RR rotaciju na čvoru B

Rezultirajuće stablo nakon RR rotacije je:

3b) Prvo izvodimo LL rotaciju na čvoru I

Rezultirajuće uravnoteženo stablo nakon LL rotacije je:

4. Umetnite C, F, D

Nakon umetanja C, F, D, BST postaje neuravnotežen jer je faktor ravnoteže B i H -2, jer ako putujemo od D do B, ustanovit ćemo da je umetnut u desno podstablo ili lijevo podstablo B, izvršit ćemo RL Rotacija na čvoru I. RL = LL + RR rotacija.

4a) Prvo izvodimo LL rotaciju na čvoru E

Rezultirajuće stablo nakon LL rotacije je:

4b) Zatim izvodimo RR rotaciju na čvoru B

Rezultirajuće uravnoteženo stablo nakon RR rotacije je:

5. Umetnite G

Nakon umetanja G, BST postaje neuravnotežen jer je faktor ravnoteže H 2, jer ako putujemo od G do H, ustanovimo da je umetnut u lijevo podstablo desnog podstabla H, izvršit ćemo LR rotaciju na čvoru I. LR = RR + LL rotacija.

5 a) Prvo izvodimo RR rotaciju na čvoru C

Rezultirajuće stablo nakon RR rotacije je:

reactjs karta

5 b) Zatim izvodimo LL rotaciju na čvoru H

Rezultirajuće uravnoteženo stablo nakon LL rotacije je:

6. Umetnite K

Nakon umetanja K, BST postaje neuravnotežen jer je faktor ravnoteže I -2. Budući da je BST zakošen udesno od I do K, stoga ćemo izvesti RR rotaciju na čvoru I.

Rezultirajuće uravnoteženo stablo nakon RR rotacije je:

7. Umetnite L

Nakon umetanja L stablo je i dalje uravnoteženo jer je faktor ravnoteže svakog čvora sada ili -1, 0, +1. Stoga je stablo uravnoteženo AVL stablo