AVL drevo

Iz MaFiRaWiki

Ta članek ali del članka je v delu. Veseli bomo, če ga boste dopolnili in popravili.

Kaj pomeni to opozorilo?


AVL drevo je podatkovna struktura, ki predstavlja imenik. AVL drevo je tako iskalno drevo, pri katerem so vsa poddrevesa uravnotežena. Imenujejo se po avtorjih te strukture (Adelson-Velskii[1] in Landis [2], 1962).

Osnovne operacije na AVL drevesu so:

  • naredi prazno drevo
  • vstavi ključ x in pripadajočo vrednost y
  • zbriši ključ x in pripadajočo vrednost
  • poišči vrednost, ki pripada ključu x

Pri vstavljanju in brisanju moramo paziti, da vsa poddrevesa v drevesu ostanejo uravnotežena. V ta namen definiramo štiri rotacije drevesa, ki drevo z uravnoteženostjo 2 ali -2 uravnotežijo.

Vstavljanje vozlišča v AVL drevo

  • določimo mesto vstavljanja podatka in ko vstavimo podatek, popravimo uravnoteženost drevesa.
  • ko se vračamo proti korenu drevesa, preverimo uravnotežnost poddreves in po potrebi izvedemo ustrezne rotacije.

Postopek:
1.) S pomočjo rekurzije poiščemo mesto za vstavljanje podatka. Ko pridemo do lista, vstavimo element. Ker je to list
in ima uravnoteženost 0, smo s tem pot v globino rekurzije zaključili in se vrnemo na predhodnji klic.


2.) Če z vstavljanjem v AVL drevo nismo porušili ravnotežja v vozlišču tega drevesa, je postopek končan.


3.) Če z vstavljanjem v AVL drevo porušimo ravnotežje, moramo izvesti ustrezne rotacije.
Naj bo vozlišče, ki ga vstavljamo, vozlišče x. Poznamo štiri možnosti:

  • od neuravnoteženega vozlišča (vozlišče x), smo šli pri iskanju mesta za vstavljanje dvakrat v levo, zato

to vozlišče rotiramo v desno (desna rotacija). Po rotaciji je postopek končan, saj se je vzpostavilo ravnotežje.

image:slika1.JPG

  • od vozlišča x smo pri vstavljanju šli najprej v levo, nato v desno, zato mora sedaj neuravnoteženo vozlišče

v desno poddrevo. Kandidat, ki pride na njegovo mesto, je koren desnega poddrevesa njegovega levega poddrevesa.
Njegovo levo poddrevo sodi levo od korena in desno od korena desnega poddrevesa. Njegovo desno poddrevo (če obstaja) pa
mora ostati desno. Gre za primer LD rotacije.

image:slika2.JPG

  • od vozlišča x smo šli pri vstavljanju v desno in nato v levo. Izvedemo DL rotacijo.

image:slika3.JPG

  • od neuravnoteženega vozlišča (vozlišče x), smo šli pri iskanju mesta za vstavljanje dvakrat v desno, zato

to vozlišče rotiramo v levo (leva rotacija). Po rotaciji je postopek končan, saj se je vzpostavilo ravnotežje.

image:slika4.JPG

Brisanje vozlišča iz AVL drevesa

  • Je zahtevnejša operacija od vstavljanja
  • Odstranjevanje vozlišč enako kot pri iskalnem drevesu
  • kot pri vstavljanju najprej rekurzivno poiščemo element, ki ga želimo odstraniti, nato pa ga nadomestimo z najbolj levim vozliščem v desnem poddrevesu (če ta obstaja), sicer pa z najbolj desnim vozliščem v levem poddrevesu.
  • če je element list (nima sinov), ga enostavno zbrišemo.
  • uravnoteženost poddreves popravimo takoj po brisanju v vsakem vozlišču na poti nazaj do korena.
  • v vozlišču v katerem se nahajamo, preverimo razliko v višini levega in desnega poddrevesa, izračunamo novo uravnoteženost, nato se pomaknemo nivo višje.

Postopek:
1.) Naj bo odstranjeno vozlišče list. Takrat popravimo uravnoteženost v vsakem vozlišču v tistem poddrevesu,
v katerem se je nahajalo brisano vozlišče. Če so uravnoteženost vozlišča -1, 0 ali 1, je postopek končan in nas rekurzija
vrne nivo višje. V nasprotnem primeru gremo naprej na eno od podtočk točke 2.


2.) Odstranjeno vozlišče je notranje, zato ga nadomestimo z najbolj levim vozliščem v desnem poddrevesu.
Na poti nazaj do korena popravimo uravnoteženost poddreves.

  • Uravnoteženost v nobenem vozlišču ni večja kot ena. Drevo je torej še vedno AVL drevo, zato je postopek končan.
  • Neuravnoteženo vozlišče ima negativni predznak, kar pomeni, da je desno poddrevo višje od levega,

zato izvedemo rotacijo v levo.

  • Neuravnoteženo vozlišče ima pozitivni predznak, kar pomeni, da je levo poddrevo višje od desnega,

zato izvedemo rotacijo v desno.

Primer brisanja elementa iz AVL drevesa
Primer brisanja, ki poruši uravnoteženost AVL drevesa
Naloga: Vstavi elemente v AVL drevo
Naloga: Sestavi AVL drevo iz števil

Delna poravnanost AVL-drevesa

Ker je AVL-drevo delno poravnano, velja, da so vse tri operacije (iskanje, vstavljanje in brisanje elementa iz drevesa) učinkovite, tj. časovna zahtevnost vsake operacije je reda O(log n), kjer je n število elementov v drevesu. Dejansko velja, da ni AVL-drevo nikoli za več kot 45% višje od ustreznega popolnoma poravnanega drevesa. Bolj točna je relacija h ≤ 1.44log(n+1).

Glej tudi

Viri

Osebna orodja