AVL drevo/PolonaVehovec

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 urejeno dvojiško drevo, ki ima globinsko neuravnoteženost ≤ 1. AVL drevesa so uravnotežena. Poimenujejo se po avtorjih te strukture (Adelson-Velskii in Landis, 1962).

Vsebina

Definicija

AVL drevo je urejeno iskalno dvojiško drevo, pri katerem se levo in desno poddrevo v vsakem vozlišču po višini razlikujeta največ za 1. Po vsakem dodajanju novega elementa se lahko višina drevesa poveča največ za 1. Pri tem se lahko razlika višin v kakem vozlišču poveča kvečjemu za 1 in postane 2. Drevo spet uravnotežimo z rotacijami drevesa. Poznamo štiri tipe rotacij:

  • LL rotacija
  • LD rotacija
  • DL rotacija
  • DD rotacija

Osnovne operacije v AVL drevesu, kot so iskanje, vstavljanje ter brisanje elementa in so v osnovi enake kot pri navadnem iskalnem dvojiškem drevesu, le da je pri vstavljanju in brisanju elementa iz drevesa novo dobljeno drevo potrebno ustrezno preoblikovati z zaporedjem rotacij.

Opis rotacij

  • LL oz. levo-leva rotacija

Kot vidimo se višina levega in desnega poddrevesa razlikuje za 2 (višina levega poddrevesa je za 2 večja od višine levega poddrevesa), zato uporabimo LL rotacijo, da drevo uravnotežimo.

-- LL rotacija -→

  • DD oz. desno-desna rotacija

Kot vidimo se višina levega in desnega poddrevesa razlikuje za 2 (višina desnega poddrevesa je za 2 večja od desnega poddrevesa), zato izvedemo DD rotacijo, da drevo uravnotežimo.

-- DD rotacija ->

  • LD oz. levo-desna rotacija

Kot vidimo se višina levega in desnega poddrevesa razlikuje za 2 (višina levega poddrevesa je za 2 večja od višine levega poddrevesa), zato uporabimo LD rotacijo, da drevo uravnotežimo.

-- LD rotacija ->

  • DL oz. desno-leva rotacija

Kot vidimo se višina levega in desnega poddrevesa razlikuje za 2 (višina desnega poddrevesa je za 2 večja od desnega poddrevesa), zato izvedemo DL rotacijo, da drevo uravnotežimo.

-- DL rotacija ->

Postopek brisanja vozlišča iz AVL drevesa

  • Je zahtevnejša operacija od vstavljanja
  • Odstranjevanje vozlišč enako kot pri iskalnem drevesu
   * po vsakem brisanju vozlišča se vrnemo po iskalni poti do korena, pri čemer preverimo ravnotežne 
faktorje vozlišč in jih po potrebi popravimo. * če smo se vrnili po levi veji: p.^bal = p.^bal-1. * če smo se vrnili po desni veji: p.^bal = p.^bal + 1. * če je bilo poddrevo pred odstranjevanjem popolnoma uravnoteženo (p.^bal = 0), se je sedaj
prevesilo na nasprotno stran, vendar se višina poddrevesa ni spremenila. Preverjanje lahko končamo.

Postopek vstavljanja vozlišča v AVL drevo

* iskalno pot sledimo, dokler ne najdemo podatka ali pridemo do lista.
* če pridemo do lista vstavimo novo vozlišče in ker je to list, ima ravnotežni faktor 0.
* na poti nazaj proti korenu preverimo in po potrebi popravimo faktorje ravnotežja v vsakem  vozlišču.
* če smo se vrnili po levi veji: p.^bal = p.^bal-1.
* če smo se vrnili po desni veji: p.^bal = p.^bal + 1.
  • Če je se ravnotežni faktor spremenil z - 1 ali +1 na 0, sta postali levo in desno poddrevo enake višine, zato nadaljnje preverajne ni potrebno in se algoritem konča.
  • Če se je ravnotežni faktor spremenil z 0 na +1 ali -1 se je desno oz.levo poddrevo povečalo. Čeprav se ravnotežje na tem nivoju ni porušilo, je treba preverjanje nadaljevati.
  • Če se je ravnotežni faktor povečal za +2 oz. -2 se je ravnotežje podrlo in je potrebno izvesti preverjanje.

Primer gradnje AVL drevesa

Iz elementov 19, 15, 10, 40, 50, 17, 4, 16, 18, 14 hočemo narediti AVL drevo.
Na začetku vzamemo prva dva elementa, potem pa na vsakem koraku dodamo nov element in sproti gledamo, da je levi sin manjši od korena in desni sin večji od korena oz. pogledamo, da je res iskalno dvojiško drevo. Paziti moramo tudi na višino obeh poddreves, da ni razlika med njima večja od 1, če pa je pa uporabimo primerno rotacijo.

image:AvlPrimer1.png
image:AvlPrimer2.png
image:AvlPrimer3.png
Osebna orodja