AVL medis besibalansuojantis dvejetainis paieškos medis informatikoje naudojama duomenų struktūra Tokio medžio šaknies i

AVL medis – 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 skiriasi daugiausiai 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 m. ir gavo vardą iš savo kūrėjų (G. M. Adelson-Velsky ir E. M. Landis).

Įterpimas

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

Nuorodos

Java appletas 2005-08-01 iš Wayback Machine projekto.

Literatūra

G. Adelson-Velsky, E. M. Landis, „An algorithm for the organization of information“, Doklady Akademii Nauk SSSR, 1962

Šis straipsnis apie programavimą yra . Jūs galite prisidėti prie Vikipedijos papildydami šį straipsnį.