AVL medis

AVL medis - tai besibalansuojantis dvejetainis paieškos medis, informatikoje naudojama duomenų struktūra. Tokio medžio šaknies (ir visų viršūnių) kairiojo ir dešiniojo pomedžio aukščiai skyriasi tik 1. Įterpimo, pašalinimo ir paieškos operacijų sudėtingumas yra O (log n) vidutiniu ir blogiausiu atveju.

AVL-medis buvo pirmas besibalansuojantis medis. Jis buvo išrastas 1962 ir gavo vardą iš savo kūrėjų (Adel‘son-Vel‘skii ir Landis).

Įterpimas

Pirma elementas įterpimas kaip ir paprastajame dvejetainiame medyje. Po to, einant link viršūnės atliekame pasukimą aplink išsibalansuotas viršūnes. Kadangi kiekvienas pasukimas užtrunka fiksuotą laiko tarpą, operacijos sudetingumas priklauso tik nuo pasukimų (viršūnių iki šaknies) skaičiaus.

Nuorodos

• Java appletas