AVL Tree išrado GM Adelson - Velsky ir EM Landis 1962 m. Medis pavadintas AVL jo išradėjų garbei.
kaip pakeisti eilutę į int
AVL medis gali būti apibrėžtas kaip subalansuoto aukščio dvejetainis paieškos medis, kuriame kiekvienas mazgas yra susietas su balanso koeficientu, kuris apskaičiuojamas atimant jo dešiniojo pomedžio aukštį iš kairiojo pomedžio aukščio.
Sakoma, kad medis yra subalansuotas, jei kiekvieno mazgo balanso koeficientas yra nuo -1 iki 1, kitaip medis bus nesubalansuotas ir jį reikės subalansuoti.
Balanso koeficientas (k) = aukštis (kairė (k)) - aukštis (dešinė (k))
Jei bet kurio mazgo balanso koeficientas yra 1, tai reiškia, kad kairysis pomedis yra vienu lygiu aukščiau nei dešinysis pomedis.
Jei bet kurio mazgo balanso koeficientas yra 0, tai reiškia, kad kairiojo ir dešiniojo pomedžio aukštis yra vienodas.
Jei bet kurio mazgo balanso koeficientas yra -1, tai reiškia, kad kairysis pomedis yra vienu lygiu žemiau nei dešinysis pomedis.
AVL medis pateiktas toliau pateiktame paveikslėlyje. Matome, kad su kiekvienu mazgu susietas balanso koeficientas yra nuo -1 iki +1. todėl tai yra AVL medžio pavyzdys.
Sudėtingumas
| Algoritmas | Vidutinis atvejis | Blogiausiu atveju |
|---|---|---|
| Erdvė | o(n) | o(n) |
| Paieška | o (log n) | o (log n) |
| Įdėti | o (log n) | o (log n) |
| Ištrinti | o (log n) | o (log n) |
Operacijos AVL medyje
Dėl to, kad AVL medis taip pat yra dvejetainis paieškos medis, todėl visos operacijos atliekamos taip pat, kaip ir dvejetainiame paieškos medyje. Paieškos ir važiavimas nesukelia AVL medžio savybių pažeidimo. Tačiau įterpimas ir ištrynimas yra operacijos, kurios gali pažeisti šią savybę, todėl jas reikia peržiūrėti dar kartą.
| SN | Operacija | apibūdinimas |
|---|---|---|
| 1 | Įdėjimas | Įterpimas į AVL medį atliekamas taip pat, kaip ir dvejetainiame paieškos medyje. Tačiau tai gali sukelti AVL medžio savybių pažeidimą, todėl medį gali reikėti subalansuoti. Medį galima subalansuoti taikant sukimus. |
| 2 | Ištrynimas | Ištrynimas taip pat gali būti atliekamas taip pat, kaip ir dvejetainiame paieškos medyje. Ištrynimas taip pat gali sutrikdyti medžio pusiausvyrą, todėl medžio pusiausvyrai atkurti naudojami įvairūs sukimosi tipai. |
Kodėl AVL medis?
AVL medis kontroliuoja dvejetainio paieškos medžio aukštį, neleidžiant jam būti iškreiptam. Laikas, per kurį atliekamos visos operacijos dvejetainiame paieškos medyje, kurio aukštis h yra Oi) . Tačiau jis gali būti pratęstas iki O(n) jei BST pasislenka (t. y. blogiausiu atveju). Apribojant šį aukštį iki log n, AVL medis nustato viršutinę kiekvienos operacijos ribą O(log n) kur n yra mazgų skaičius.
AVL rotacijos
Sukimą AVL medyje atliekame tik tuo atveju, jei Balance Factor yra kitoks nei -1, 0 ir 1 . Iš esmės yra keturi sukimosi tipai, kurie yra tokie:
- L L pasukimas: įterptas mazgas yra kairiajame A kairiojo pomedžio pomedyje
- R R pasukimas : įterptas mazgas yra dešiniajame A dešiniojo pomedžio pomedyje
- L R pasukimas : įterptas mazgas yra kairiajame A pomedžio dešiniajame pomedyje
- R L pasukimas : įterptas mazgas yra kairiajame dešiniojo A pomedžio pomedyje
Kur mazgas A yra mazgas, kurio balanso koeficientas yra kitoks nei -1, 0, 1.
Pirmieji du pasukimai LL ir RR yra pavieniai, o kiti du sukimai LR ir RL yra dvigubi. Kad medis būtų nesubalansuotas, minimalus aukštis turi būti bent 2, Supraskime kiekvieną sukimąsi
1. RR rotacija
Kai BST tampa nesubalansuotas, dėl to, kad į dešinįjį A dešiniojo pomedžio pomedį įterpiamas mazgas, atliekame RR sukimą, RR sukimas yra sukimas prieš laikrodžio rodyklę, kuris taikomas krašte po mazgu, kurio balanso koeficientas -2
Aukščiau pateiktame pavyzdyje mazgas A turi balanso koeficientą -2, nes mazgas C yra įterptas į dešinįjį A dešiniojo pomedžio pomedį. RR pasukimą atliekame krašte žemiau A.
2. LL Rotacija
Kai BST tampa nesubalansuotas, dėl to, kad į kairiojo C kairiojo pomedžio kairįjį pomedį įterpiamas mazgas, atliekame LL sukimą, LL sukimas yra sukimas pagal laikrodžio rodyklę, kuris taikomas krašte po mazgu, kurio balanso koeficientas 2.
Aukščiau pateiktame pavyzdyje mazgas C turi balanso koeficientą 2, nes mazgas A yra įterptas į kairiojo C kairiojo pomedžio kairįjį pomedį. Atliekame LL pasukimą krašte žemiau A.
3. LR Rotacija
Dvigubas sukimasis yra šiek tiek sunkesnis nei vienas sukimas, kuris jau buvo paaiškintas aukščiau. LR sukimas = RR sukimas + LL pasukimas, t.y. pirmiausia RR sukimas atliekamas ant pomedžio, o po to LL sukimas atliekamas visame medyje, pilnu medžiu reiškia pirmąjį mazgą nuo įterpto mazgo kelio, kurio balanso koeficientas yra kitoks nei -1 , 0 arba 1.
režisierius Karanas Joharas
Supraskime kiekvieną žingsnį labai aiškiai:
| valstybė | Veiksmas |
|---|---|
 | Mazgas B buvo įterptas į dešinįjį A pomedį, į kairįjį C pomedį, dėl kurio C tapo nesubalansuotu mazgu, turinčiu balanso koeficientą 2. Šis atvejis yra L R sukimas, kur: Įterptas mazgas yra kairiojo pomedžio dešiniajame pomedyje. C |
 | Kadangi LR sukimas = RR + LL pasukimas, tai pirmiausia atliekamas RR (prieš laikrodžio rodyklę) ant pomedžio, kurio šaknys yra A. Atlikdami RR sukimąsi, mazgas A , tapo kairiuoju pomedžiu B . |
 | Atlikus RR sukimą, mazgas C vis dar yra nesubalansuotas, t. y. turi balanso koeficientą 2, nes įterptas mazgas A yra kairėje arba kairėje C |
 | Dabar mes atliekame LL sukimąsi pagal laikrodžio rodyklę visame medyje, ty mazge C. mazgas C dabar tapo dešiniuoju mazgo B pomedžiu, o A yra kairiuoju B pomedžiu |
 | Kiekvieno mazgo balanso koeficientas dabar yra -1, 0 arba 1, t. y. BST dabar subalansuotas. |
4. RL sukimasis
Kaip jau buvo aptarta, šis dvigubas sukimasis yra šiek tiek sunkesnis nei vienas sukimas, kuris jau buvo paaiškintas aukščiau. R L sukimas = LL pasukimas + RR pasukimas, t.y. pirmiausia LL sukimas atliekamas ant pomedžio, o po to RR sukimas atliekamas visame medyje, pilnu medžiu reiškia pirmąjį mazgą nuo įterpto mazgo kelio, kurio balanso koeficientas yra kitoks nei -1 , 0 arba 1.
| valstybė | Veiksmas |
|---|---|
 | Mazgas B buvo įterptas į kairįjį pomedį C dešinysis pomedis A , dėl kurio A tapo nesubalansuotu mazgu, kurio balanso koeficientas - 2. Šis atvejis yra RL sukimasis kur: Įterptas mazgas yra dešiniojo A pomedžio kairėje |
 | Kadangi RL sukimas = LL pasukimas + RR pasukimas, taigi, LL (pagal laikrodžio rodyklę) ant pomedžio, įsišaknijusio C atliekama pirmiausia. Atlikdami RR sukimąsi, mazgas C tapo tinkamu pomedžiu B . |
 | Atlikus LL sukimąsi, mazgas A vis dar nesubalansuotas, t. y. turi balanso koeficientą -2, kuris atsiranda dėl dešiniojo pomedžio mazgo A dešiniojo pomedžio. |
 | Dabar atliekame RR sukimąsi (sukimas prieš laikrodžio rodyklę) visame medyje, ty mazge A. mazgas C dabar tapo dešiniuoju mazgo B pomedžiu, o mazgas A tapo kairiuoju B pomedžiu. |
 | Kiekvieno mazgo balanso koeficientas dabar yra -1, 0 arba 1, t. y. BST dabar yra subalansuotas. |
Klausimas: Sukurkite AVL medį, turintį šiuos elementus
H, I, J, B, A, E, C, F, D, G, K, L
1. Įterpkite H, I, J
Įterpus aukščiau nurodytus elementus, ypač H atveju, BST tampa nesubalansuotas, nes H balanso koeficientas yra -2. Kadangi BST yra į dešinę, mes atliksime RR sukimąsi mazge H.
Gautas balanso medis yra:
referencinis kintamasis Java
2. Įterpkite B, A
Įterpus aukščiau nurodytus elementus, ypač A atveju, BST tampa nesubalansuotas, nes H ir I balanso koeficientas yra 2, mes atsižvelgiame į pirmąjį mazgą iš paskutinio įterpto mazgo, t. y. H. Kadangi BST iš H yra pasviręs į kairę, atliksime LL sukimąsi mazge H.
Gautas balanso medis yra:
3. Įdėkite E
Įterpus E, BST tampa nesubalansuotas, nes I balanso koeficientas yra 2, nes jei keliaujame iš E į I, pamatysime, kad jis yra įterptas į dešinįjį I pomedžio kairįjį pomedį, atliksime LR sukimą I mazge. LR = RR + LL sukimasis
3 a) Pirmiausia atliekame RR pasukimą mazge B
Gautas medis po RR pasukimo yra:
3b) Pirmiausia atliekame LL sukimąsi mazge I
Gautas subalansuotas medis po LL sukimosi yra:
4. Įterpkite C, F, D
Įterpus C, F, D, BST tampa nesubalansuotas, nes B ir H balanso koeficientas yra -2, nes jei keliaujame iš D į B, pamatysime, kad jis yra įterptas į dešinįjį kairiojo B pomedžio pomedį, atliksime RL sukimasis mazge I. RL = LL + RR sukimas.
4a) Pirmiausia atliekame LL pasukimą mazge E
Gautas medis po LL pasukimo yra:
katalogo pervadinimas
4b) Tada atliekame RR sukimąsi mazge B
Gautas subalansuotas medis po RR pasukimo yra:
5. Įdėkite G
Įterpus G, BST tampa nesubalansuotas, nes H balanso koeficientas yra 2, nes jei keliaujame iš G į H, pamatysime, kad jis yra įterptas į dešiniojo H pomedžio kairįjį pomedį, atliksime LR sukimą I mazge. LR = RR + LL sukimasis.
atsitiktinis skaičius gen java
5 a) Pirmiausia atliekame RR sukimąsi mazge C
Gautas medis po RR pasukimo yra:
5 b) Tada atliekame LL sukimąsi mazge H
Gautas subalansuotas medis po LL sukimosi yra:
6. Įdėkite K
Įterpus K, BST tampa nesubalansuotas, nes I balanso koeficientas yra -2. Kadangi BST yra į dešinę nuo I iki K, todėl mazge I atliksime RR sukimąsi.
Gautas subalansuotas medis po RR pasukimo yra:
7. Įdėkite L
Įdėjus L medis vis dar yra subalansuotas, nes kiekvieno mazgo balanso koeficientas dabar yra -1, 0, +1. Taigi medis yra subalansuotas AVL medis
