AVL Tree izgudroja GM Adelson - Velsky un EM Landis 1962. gadā. Koks ir nosaukts AVL par godu tā izgudrotājiem.
AVL Tree var definēt kā augstuma līdzsvarotu bināro meklēšanas koku, kurā katrs mezgls ir saistīts ar līdzsvara koeficientu, kas tiek aprēķināts, atņemot tā labā apakškoka augstumu no tā kreisā apakškoka augstuma.
Tiek uzskatīts, ka koks ir līdzsvarots, ja katra mezgla līdzsvara koeficients ir no -1 līdz 1, pretējā gadījumā koks būs nelīdzsvarots un tas ir jāsabalansē.
Līdzsvara koeficients (k) = augstums (pa kreisi (k)) - augstums (labais (k))
Ja jebkura mezgla līdzsvara koeficients ir 1, tas nozīmē, ka kreisais apakškoks ir par vienu līmeni augstāks nekā labais apakškoks.
Ja jebkura mezgla līdzsvara koeficients ir 0, tas nozīmē, ka kreisais apakškoks un labais apakškoks satur vienādu augstumu.
Ja jebkura mezgla līdzsvara koeficients ir -1, tas nozīmē, ka kreisais apakškoks ir par vienu līmeni zemāks nekā labais apakškoks.
AVL koks ir parādīts nākamajā attēlā. Mēs redzam, ka ar katru mezglu saistītais līdzsvara koeficients ir no -1 līdz +1. tāpēc tas ir AVL koka piemērs.
Sarežģītība
| Algoritms | Vidējais gadījums | Sliktākajā gadījumā |
|---|---|---|
| Kosmoss | o(n) | o(n) |
| Meklēt | o(log n) | o(log n) |
| Ievietot | o(log n) | o(log n) |
| Dzēst | o(log n) | o(log n) |
Darbības uz AVL koka
Sakarā ar to, ka AVL koks ir arī binārais meklēšanas koks, visas darbības tiek veiktas tāpat kā binārajā meklēšanas kokā. Meklēšana un šķērsošana nenoved pie AVL koka īpašuma pārkāpuma. Tomēr ievietošana un dzēšana ir darbības, kas var pārkāpt šo īpašību, un tāpēc tās ir jāpārskata.
| SN | Darbība | Apraksts |
|---|---|---|
| 1 | Ievietošana | Ievietošana AVL kokā tiek veikta tāpat kā binārajā meklēšanas kokā. Tomēr tas var novest pie pārkāpumiem AVL koka īpašumā, un tāpēc kokam var būt nepieciešama līdzsvarošana. Koku var līdzsvarot, piemērojot rotācijas. |
| 2 | Dzēšana | Dzēšanu var veikt arī tādā pašā veidā, kā tas tiek veikts binārajā meklēšanas kokā. Dzēšana var arī izjaukt koka līdzsvaru, tāpēc koka līdzsvarošanai tiek izmantoti dažādi rotācijas veidi. |
Kāpēc AVL koks?
AVL koks kontrolē binārā meklēšanas koka augstumu, neļaujot tam būt šķībam. Laiks, kas nepieciešams visām darbībām binārā meklēšanas kokā ar augstumu h ir O(h) . Tomēr to var paplašināt līdz O(n) ja BST kļūst šķībs (t.i., sliktākajā gadījumā). Ierobežojot šo augstumu līdz log n, AVL koks katrai darbībai uzliek augšējo robežu O(log n) kur n ir mezglu skaits.
AVL Rotācijas
Rotāciju AVL kokā veicam tikai gadījumā, ja Balance Factor ir cits kā -1, 0 un 1 . Pamatā ir četri rotācijas veidi, kas ir šādi:
- L L rotācija: ievietotais mezgls atrodas A kreisā apakškoka kreisajā apakškokā
- R R rotācija : ievietotais mezgls atrodas A labā apakškoka labajā apakškokā
- L R rotācija : ievietotais mezgls atrodas A kreisā apakškoka labajā apakškokā
- R L rotācija : ievietotais mezgls atrodas A labā apakškoka kreisajā apakškokā
Kur mezgls A ir mezgls, kura bilances koeficients atšķiras no -1, 0, 1.
Pirmie divi apgriezieni LL un RR ir vienreizēji apgriezieni, un nākamās divas rotācijas LR un RL ir dubultās apgriezieni. Lai koks būtu nelīdzsvarots, minimālajam augstumam jābūt vismaz 2, Ļaujiet mums saprast katru rotāciju
1. RR Rotācija
Kad BST kļūst nelīdzsvarots, jo A labā apakškoka labajā apakškokā tiek ievietots mezgls, tad veicam RR rotāciju, RR rotācija ir rotācija pretēji pulksteņrādītāja virzienam, kas tiek piemērota malai zem mezgla ar līdzsvara koeficientu -2.
Iepriekš minētajā piemērā mezglam A ir līdzsvara koeficients -2, jo mezgls C ir ievietots labā apakškoka A labajā apakškokā. Mēs veicam RR rotāciju malā zem A.
2. LL Rotācija
Kad BST kļūst nelīdzsvarots, jo C kreisā apakškoka kreisajā apakškokā tiek ievietots mezgls, tad veicam LL rotāciju, LL rotācija ir pulksteņa rādītāja virziena rotācija, kas tiek piemērota malai zem mezgla ar līdzsvara koeficientu 2.
Iepriekš minētajā piemērā mezglam C ir līdzsvara koeficients 2, jo mezgls A ir ievietots C kreisā apakškoka kreisajā apakškokā. Mēs veicam LL rotāciju malā zem A.
3. LR Rotācija
Dubultās rotācijas ir nedaudz grūtākas nekā viena rotācija, kas jau ir izskaidrota iepriekš. LR rotācija = RR rotācija + LL rotācija, t.i., vispirms tiek veikta RR rotācija apakškokam un pēc tam LL rotācija tiek veikta pilnam kokam, ar pilnu koku mēs domājam pirmo mezglu no ievietotā mezgla ceļa, kura līdzsvara koeficients ir citāds nekā -1 , 0 vai 1.
Ļaujiet mums ļoti skaidri saprast katru soli:
| Valsts | Darbība |
|---|---|
 | A labajā apakškokā C kreisajā apakškokā ir ievietots mezgls B, kā dēļ C ir kļuvis par nelīdzsvarotu mezglu ar līdzsvara koeficientu 2. Šis gadījums ir L R rotācija, kur: Ievietotais mezgls atrodas kreisā apakškoka labajā apakškokā. C |
 | Tā kā LR rotācija = RR + LL rotācija, vispirms tiek veikta RR (pretēji pulksteņrādītāja virzienam) apakškokam, kas sakņojas pie A. Veicot RR rotāciju, mezgls A , ir kļuvis par kreiso apakškoku B . |
 | Pēc RR rotācijas veikšanas mezgls C joprojām ir nelīdzsvarots, t.i., tam ir līdzsvara koeficients 2, jo ievietotais mezgls A atrodas pa kreisi no kreisās puses. C |
 | Tagad mēs veicam LL rotāciju pulksteņrādītāja virzienā uz pilnu koku, t.i. uz mezgla C. mezglu C tagad ir kļuvis par mezgla B labo apakškoku, bet A ir B kreisais apakškoks |
 | Katra mezgla līdzsvara koeficients tagad ir -1, 0 vai 1, t.i., BST tagad ir līdzsvarots. |
4. RL Rotācija
Kā jau tika runāts, šī dubultā rotācija ir nedaudz stingrāka nekā viena rotācija, kas jau tika paskaidrota iepriekš. RL rotācija = LL rotācija + RR rotācija, t.i., vispirms LL rotācija tiek veikta apakškokam un pēc tam RR rotācija tiek veikta pilnam kokam, ar pilnu koku mēs domājam pirmo mezglu no ievietotā mezgla ceļa, kura līdzsvara koeficients ir citāds nekā -1 , 0 vai 1.
| Valsts | Darbība |
|---|---|
 | Mezgls B ir ievietots kreisajā apakškokā C labais apakškoks A , kura dēļ A ir kļuvis par nelīdzsvarotu mezglu ar līdzsvara koeficientu - 2. Šis gadījums ir RL rotācija kur: Ievietotais mezgls atrodas A labā apakškoka kreisajā apakškokā. |
 | Tā kā RL rotācija = LL rotācija + RR rotācija, tātad LL (pulksteņrādītāja virzienā) apakškokā, kas sakņojas C tiek veikta vispirms. Veicot RR rotāciju, mezgls C ir kļuvis par pareizo apakškoku B . |
 | Pēc LL rotācijas veikšanas mezgls A joprojām ir nelīdzsvarots, t.i., tam ir līdzsvara koeficients -2, kas ir saistīts ar labā apakškoka mezgla A labās puses apakškoku. |
 | Tagad mēs veicam RR rotāciju (griešanos pretēji pulksteņrādītāja virzienam) uz pilna koka, t.i., uz mezgla A. mezgls C tagad ir kļuvis par mezgla B labo apakškoku, un mezgls A ir kļuvis par B kreiso apakškoku. |
 | Katra mezgla līdzsvara koeficients tagad ir -1, 0 vai 1, t.i., BST tagad ir līdzsvarots. |
J: Izveidojiet AVL koku ar šādiem elementiem
H, I, J, B, A, E, C, F, D, G, K, L
1. Ievietojiet H, I, J
Ievietojot iepriekš minētos elementus, īpaši H gadījumā, BST kļūst nelīdzsvarots, jo H līdzsvara koeficients ir -2. Tā kā BST ir šķībs, mēs veiksim RR rotāciju mezglā H.
Rezultātā iegūtais bilances koks ir:
tostring java metode
2. Ievietojiet B, A
Ievietojot iepriekš minētos elementus, īpaši A gadījumā, BST kļūst nelīdzsvarots, jo H un I līdzsvara koeficients ir 2, mēs ņemam vērā pirmo mezglu no pēdējā ievietotā mezgla, t.i., H. Tā kā BST no H ir šķībs pa kreisi, mēs veiksim LL rotāciju mezglā H.
Rezultātā iegūtais bilances koks ir:
3. Ievietojiet E
Ievietojot E, BST kļūst nelīdzsvarots, jo I līdzsvara faktors ir 2, jo, ceļojot no E uz I, mēs atklājam, ka tas ir ievietots I labā apakškoka kreisajā apakškokā, mēs veiksim LR rotāciju mezglā I. LR = RR + LL rotācija
3 a) Vispirms mēs veicam RR rotāciju mezglā B
Rezultātā koks pēc RR rotācijas ir:
3b) Vispirms mezglā I veicam LL rotāciju
Rezultātā sabalansētais koks pēc LL rotācijas ir:
4. Ievietojiet C, F, D
Ievietojot C, F, D, BST kļūst nelīdzsvarots, jo B un H līdzsvara faktors ir -2, jo, ceļojot no D uz B, mēs atklājam, ka tas ir ievietots B kreisā apakškoka labajā apakškokā, mēs veiksim RL Rotācija mezglā I. RL = LL + RR rotācija.
4a) Vispirms mēs veicam LL rotāciju mezglā E
Rezultātā koks pēc LL rotācijas ir:
4b) Pēc tam mēs veicam RR rotāciju mezglā B
Rezultātā sabalansētais koks pēc RR rotācijas ir:
5. Ievietojiet G
Ievietojot G, BST kļūst nelīdzsvarots, jo H līdzsvara faktors ir 2, jo, ja mēs ceļojam no G uz H, mēs atklājam, ka tas ir ievietots H labā apakškoka kreisajā apakškokā, mēs veiksim LR rotāciju mezglā I. LR = RR + LL rotācija.
5 a) Vispirms veicam RR rotāciju mezglā C
Rezultātā koks pēc RR rotācijas ir:
5 b) Pēc tam veicam LL rotāciju mezglā H
Rezultātā sabalansētais koks pēc LL rotācijas ir:
6. Ievietojiet K
Ievietojot K, BST kļūst nelīdzsvarots, jo I līdzsvara faktors ir -2. Tā kā BST ir šķībs no I līdz K, mēs veiksim RR rotāciju mezglā I.
Rezultātā sabalansētais koks pēc RR rotācijas ir:
7. Ievietojiet L
Ievietojot L koks joprojām ir līdzsvarots, jo katra mezgla līdzsvara koeficients tagad ir vai nu -1, 0, +1. Tādējādi koks ir līdzsvarots AVL koks
