An AVL medis apibrėžiamas kaip savibalansas Skirtumas tarp kairiojo ir dešiniojo pomedžio aukščių bet kuriame mazge yra žinomas kaip balanso faktorius mazgo.

excel pašalinti pirmąjį simbolį

AVL medis pavadintas jo išradėjų Georgijaus Adelsono-Velskio ir Evgenii Landis vardu, kurie jį paskelbė savo 1962 m. darbe „Informacijos organizavimo algoritmas“.

AVL medžių pavyzdys:

AVL medis

Aukščiau pateiktas medis yra AVL, nes kiekvieno mazgo kairiojo ir dešiniojo pomedžio aukščių skirtumai yra mažesni arba lygūs 1.

AVL medžio operacijos:

• Įdėjimas
• Ištrynimas
• Ieškoma [Tai panašu į paieškos atlikimą BST]

Pomedžių pasukimas AVL medyje:

AVL medis gali suktis vienu iš keturių būdų, kaip išlaikyti pusiausvyrą:

Rotacija į kairę :

Kai mazgas pridedamas prie dešiniojo pomedžio dešiniojo pomedžio, jei medis išsibalansuoja, atliekame vieną sukimąsi į kairę.

Pasukimas į kairę AVL medyje

Teisingas sukimasis :

kaip pasiekti icloud nuotraukas

Jei mazgas pridedamas prie kairiojo kairiojo pomedžio pomedžio, AVL medis gali išsibalansuoti, padarome vieną sukimąsi į dešinę.

Pasukimas į dešinę AVL medyje

Sukimas į kairę-dešinę :

Sukimas į kairę į dešinę yra derinys, kai pirmasis sukimas į kairę vyksta po to, kai įvyksta sukimas į dešinę.

Sukimas į kairę-dešinę AVL medyje

Sukimas į dešinę – į kairę :

Sukimas į dešinę į kairę yra derinys, kai pirmasis sukimas į dešinę vyksta po to, kai įvyksta sukimas į kairę.

Sukimas į dešinę ir į kairę AVL medyje

AVL medžio taikymas:

1. Jis naudojamas dideliems įrašams duomenų bazėje indeksuoti ir efektyviai joje ieškoti.
2. Visų tipų atmintyje esančioms kolekcijoms, įskaitant rinkinius ir žodynus, naudojami AVL medžiai.
3. Duomenų bazių programos, kuriose įterpimai ir trynimai yra mažiau paplitę, tačiau reikia dažnai ieškoti duomenų
4. Programinė įranga, kuriai reikalinga optimizuota paieška.
5. Jis taikomas verslo srityse ir siužetinių žaidimų žaidimuose.

AVL medžio pranašumai:

1. AVL medžiai gali patys susibalansuoti.
2. Jis tikrai nėra iškreiptas.
3. Tai suteikia greitesnę paiešką nei raudonai juodi medžiai
4. Palyginti su kitais medžiais, pavyzdžiui, dvejetainiu medžiu, sudėtingesnis paieškos laikas.
5. Aukštis negali viršyti log(N), kur N yra bendras medžio mazgų skaičius.

AVL medžio trūkumai:

1. Jį sunku įgyvendinti.
2. Kai kurioms operacijoms jis turi didelius pastovius veiksnius.
3. Mažiau naudojami, palyginti su raudonai juodais medžiais.
4. Dėl gana griežtos pusiausvyros AVL medžiai atlieka sudėtingas įterpimo ir pašalinimo operacijas, nes atliekama daugiau sukimų.
5. Norėdami subalansuoti, imkitės daugiau apdorojimo.

Susiję straipsniai:

paieškos algoritmai

• Dvejetainės paieškos medžių įvadas – duomenų struktūros ir algoritmų vadovėliai
• Įterpimas į AVL medį
• Ištrynimas AVL medyje