AVL drevo

AVL drevo je drevesna podatkovna struktura, za katero veljajo naslednje lastnosti:

• AVL drevo je iskalno drevo:
  Vozlišča so v drevesu urejena tako, da so v levem poddrevesu vedno manjši elementi od korena, v desnem poddrevesu pa večji od korena. Tudi desno in levo poddrevo sta iskalni drevesi. Tako je iskanje elementov v drevesu veliko lažje, saj vemo, v kateri smeri moramo iskati.
  

  Iskalno drevo

• AVL drevo je uravnoteženo drevo:
  To pomeni, da se lahko višini poddreves vsakega vozlišča razlikujeta za največ 1.
  Rečemo, da je koren drevesa levo-višinski, če je višina levega poddrevesa za eno večja od višine desnega. Po drugi strani je koren desno-višinski, če je višina desnega poddrevesa večja od višine levega. Koren pa je uravnotežen, če sta višini poddreves enaki.
  Če so vsa vozlišča v drevesu uravnotežena, je drevo popolnoma uravnoteženo.

  Popolnoma uravnoteženo iskalno drevo je AVL drevo.

  
  

Pri AVL drevesih si glede uravnoteženosti pomagamo z ravnotežnostnim faktorjem, ki ga pripišemo vsakemu vozlišču.
Izračunamo ga tako, da odštejemo višino desnega poddrevesa od višine levega poddrevesa. Če je torej ravnotežnostni faktor med -1 in 1, je drevo uravnoteženo, sicer pa ne.

Delno uravnoteženo iskalno drevo, kjer je koren drevesa levo-višinski, je AVL drevo, saj so vsi ravnotežnostni faktorji večji od -2 in manjši od 2.

Ravnotežnostni faktor korena zgornjega primera je enak 1, ker je višina njegovega levega poddrevesa enaka 2, višina desnega poddrevesa pa enaka 1. Višini odštejemo in dobimo omenjeni rezultat.

Neuravnoteženo iskalno drevo. Ravnotežnostni faktor v korenu je prevelik, zato to drevo ni AVL.

1. Primer:

Oglejmo si najprej še en primer dvojiškega drevesa, ki je AVL drevo.

Primer AVL drevesa.

Zgornje drevo je AVL, ker je iskalno in so vsa njegova vozlišča v ravnotežju.

Sedaj pa še dva primera dreves, ki nista AVL drevesi:

2. Primer:

Tole drevo ni AVL drevo.

Poglejmo si, zakaj zgornje drevo ni AVL drevo. Opazimo, da drevo ne izpolnjuje pogoja iskalnosti, saj je levi sin (vozlišče 14) večji od korena drevesa (vozlišče 12), moral bi pa biti manjši od korena. Podobno lahko v drevesu najdemo še nekaj takih napak.

3. Primer:

Tudi to drevo ni AVL drevo.

Drugi primer pa je drevo, ki sicer ustreza pogoju iskalnosti, ni pa uravnoteženo in posledično zaradi tega ni AVL drevo. Vozlišče z vrednostjo 23 ima ravnotežnostni faktor 2, kar pomeni, da je višina levega poddrevesa za dve večja od višine levega drevesa.

Kakor druge drevesne podatkovne strukture, tako tudi AVL drevo lahko predstavimo s tabelo. Tak način zapisa je učinkovit in pregleden (sploh pri veliki količini podatkov) in ga zato uporabljamo tako za iskanje elementov v drevesu, kot tudi za operaciji vstavljanja in brisanja elementov iz drevesa.

V tabeli so elementi drevesa razporejeni na naslednji način:

• koren drevesa je na 1. mestu

• element na i-tem mestu tabele ima

  • svojega levega sina na mestu 2i,
  • svojega desnega sina na mestu 2i+1,
  • svojega očeta pa na mestu i/2 (uporabimo celoštevilsko deljenje).
    

1. Primer:

Primer AVL drevesa, predstavljenega s tabelo.

Poglejmo si vozlišče 13, ki se nahaja na i = 2. mestu v tabeli.

• levi sin: , torej je to vozlišče 7
• desni sin: , dobimo vozlišče 20
• oče: , to je koren drevesa, število 35.
  
  

2. Primer:

Še en primer AVL drevesa v obliki tabele.

V tabeli je potrebno elemente našteti po vrsti po nivojih in seveda upoštevati, da morebitna vozlišča nimajo naslednikov. V tem primeru je to vozlišče 13, ki nima naslednikov, zato mesta v tabeli, kjer bi morala biti njegova sinova, označimo z None.

Nov element v AVL drevo vedno vstavimo kot nov list, to je kot vozlišče na dnu drevesa, ki je brez sinov.
Vstavljati začnemo pri korenu drevesa (na vrhu) in se na podlagi vrednosti v vozliščih (pravila iskalnega drevesa) odločamo, ali bomo vstavljali levo ali desno.
Ko element vstavimo v drevo, mu dodelimo ravnotežnostni faktor 0 (0 zato, ker novo vozlišče nima sinov) in popravimo ravnotežnostne faktorje vozlišč na poti, po kateri smo vstavljali in sproti preverimo, če se je kje morda ravnotežje drevesa pokvarilo.

Poglejmo si nekaj primerov vstavljanja:

1. Primer:

V drevo na spodnji sliki želimo vstaviti element 8.

AVL drevo pred vstavljanjem.

Vstavljati začnemo pri korenu. Ker je 8 večje od 6, nadaljujemo vstavljanje pri njegovem desnem sinu, tj. vozlišču 9. Ker je 9 večje od naše vstavljane 8, bomo vstavljanje nadaljevali v levem poddrevesu. Ker pa je le-to še prazno, lahko novo vozlišče kar vstavimo.

Pot vstavljanja novega vozlišča.

Ko element vstavimo, je potrebno poskrbeti še za ravnotežnostne faktorje. Vozlišču 8 pripišemo ravnotežnostni faktor 0 in gremo nazaj po poti, po kateri smo vstavljali; 9 ima sedaj na levi eno vozlišče (tj. višina levega poddrevesa je enaka 1), na desni pa še nobenega, zato je njen ravnotežnostni faktor 1-0 = 1. Podobno poračunamo še faktor za koren drevesa, ki je po novem enak 0.

Po vstavljanju popravimo ravnotežnostne faktorje.

Ko smo ravnotežnostne faktorje popravili, drevo pogledamo, če se ni mogoče ravnotežje kje pokvarilo in zato naše drevo ni več AVL. V tem primeru so vsi faktorji med -1 in 1, torej drevo še vedno ustreza in primer je zaključen.

2. Primer:

V spodnje drevo želimo vstaviti element 39.

AVL drevo.

Novo vozlišče spet vstavimo po enakem postopku, kot pri prejšnjem primeru; začnemo pri korenu in novo vozlišče vstavimo kot list.

Pot vstavljanja elementa 39.

Po tem, ko smo element vstavili, na novo izračunamo ravnotežnostne faktorje.

Še en primer AVL drevesa v obliki tabele.

Med preverjanjem pa ugotovimo, da se je v vozlišču 36 ravnotežje drevesa pokvarilo in to drevo ne ustreza več pravilom AVL dreves.
Ker želimo doseči, da bo drevo zopet AVL drevo, bomo zgornje drevo malo "popravili" - vozlišča bomo zarotirali tako, da bodo vozlišča drevesa spet v ravnotežju. To pa naredimo z eno od rotacij.

Kot smo že povedali, rotacije uporabljamo v primerih, ko z vstavljanjem novega vozlišča v drevo pokvarimo ravnotežje.
Poznamo dve osnovni rotaciji:

• levo rotacijo in
• desno rotacijo.
  

Leva rotacija

Uporabimo jo v primeru, ko smo pri vstavljanju novega elementa šli dvakrat v levo in je ravnotežni faktor na nekem vozlišču enak 2. Na tem vozlišču opravimo levo rotacijo tako, da njegov levi sin zasede njegovo mesto, sam pa postane njegov desni sin.

• Leva rotacija na enostavnem primeru:
  v tole drevo smo vstavili vozlišče 7 in zato se je v korenu drevesa ravnotežje pokvarilo.

  Leva rotacija.

  
  

• V splošnem pa je leva rotacija na elementu X takšna:
  (X, Y, in Z so vozlišča; A, B, C in D pa so neprazna poddrevesa)

  Leva rotacija v splošnem.

  
  

Desna rotacija

Desna rotacija je simetrična levi. Uporabimo jo, če smo pri vstavljanju novega vozlišča šli dvakrat v desno in je ravnotežnostni faktor na nekem vozlišču enak -2. Na tem vozlišču torej opravimo desno rotacijo tako, da njegov desni sin zasede njegovo mesto, sam pa postane njegov desni sin.

• Desna rotacija na enostavnem primeru:
  

  Desna rotacija na primeru.

  
  

• V splošnem pa desna rotacija na elementu X poteka tako:
  (X, Y, in Z so vozlišča; A, B, C in D pa so neprazna poddrevesa)

  Desna rotacija v splošnem.

  
  

Poleg leve in desne rotacije pa uporabljamo še dve sestavljeni rotaciji:

• levo-desna (L-D) rotacija in
• desno-leva (D-L) rotacija.

Kot že ime pove, sta rotaciji sestavljeni iz dveh korakov: iz desne in leve rotacije (oz. obratno), ki ju izvedemo eno za drugo.

Levo-desna rotacija

To rotacijo je potrebno opraviti, če smo pri vstavljanju novega elementa šli najprej v levo in nato v desno. Ravnotežnostni faktor je tako na nekem vozlišču (recimo mu koren) enak 2.
Rotacijo opravimo tako, da na levem sinu od korena najprej izvedemo desno rotacijo in na korenu nato še levo rotacijo.

• Levo-desna rotacija na enostavnem primeru:
  tu smo na novo vstavili vozlišče 10, ki je korenu 11 podrlo ravnotežje. Na vozlišču 6 najprej izvedemo desno rotacijo, nato pa na korenu še levo.
  

  Levo-desna rotacija.

  
  

• V splošnem je rotacija takšna:
  (X, Y, in Z so vozlišča; A, B, C in D pa so neprazna poddrevesa)
  

  

  Levo-desna rotacija v splošnem.

  
  

Desno-leva rotacija

Ta rotacija je simetrična levo-desni rotaciji.
Potrebno jo je izvesti, če smo pri vstavljanju novega elementa šli najprej v desno in nato v levo. Ravnotežnostni faktor je na nekem vozlišču (recimo mu koren) enak -2.
Rotacijo opravimo tako, da na desnem sinu korena najprej izvedemo levo rotacijo in na korenu nato še desno rotacijo.

• Desno-leva rotacija na enostavnem primeru:
  

  Desno-leva rotacija.

  
  

• V splošnem je potek rotacije takšen:
  (X, Y, in Z so vozlišča; A, B, C in D pa so neprazna poddrevesa)
  

  

  Desno-leva rotacija v splošnem.

  
  

Sedaj, ko smo se naučili vso teorijo vstavljanja vozlišč v AVL drevo, si lahko pogledamo primer gradnje drevesa na krajšem filmčku.

Poglej filmček

Preskoči primer in nadaljuj s teorijo

Poleg vstavljanja vozlišč je brisanje ena glavnih operacij AVL dreves. Odstranimo lahko katerokoli vozlišče v drevesu, pri tem pa moramo poznati naslednja pravila:

• če želimo iz AVL drevesa odstraniti list, to vozlišče enostavno zbrišemo

• če odstranjujemo vozlišče, ki ni list, pa moramo brisani element v drevesu nadomestiti

  • z najbolj levim vozliščem v desnem poddrevesu, če le-to obstaja
  • sicer pa z najbolj desnim vozliščem v levem poddrevesu
    

Po odstranjevanju vozlišča je v vsakem primeru potrebno popraviti ravnotežnostne faktorje v drevesu in opraviti morebitne rotacije, če je le-to potrebno.

Poglejmo si nekaj primerov odstranjevanja:

1. Primer:

Iz drevesa na spodnji sliki želimo odstraniti vozlišče z vrednostjo 12.

AVL drevo pred brisanjem vozlišča.

Vozlišče 12 bomo nadomestili z najbolj levim elementom v desnem poddrevesu brisanega elementa. Ker desno poddrevo vsebuje le eno vozlišče, uporabimo tega.

Brisani element nadomestimo z njegovim desnim sinom.

Po brisanju na novo poračunamo ravnotežnostne faktorje in ugotovimo, da je drevo še vedno v ravnotežju. Primer je končan.

Drevo po odstranjevanju vozlišča.

2. Primer:

Poglejmo si še en malo večji primer. Tokrat bomo iz spodnjega AVL drevesa odstranili vozlišče z vrednostjo 32.

AVL drevo pred brisanjem.

Brisani element nadomestimo z njegovim desnim sinom, ki je, podobno kot v prejšnjem primeru, edini naslednik v desnem poddrevesu brisanega vozlišča.

AVL drevo pred brisanjem.

Nadaljevanje primera...

Po brisanju je potrebno popraviti ravnotežnostne faktorje v drevesu.
Ugotovimo, da zaradi brisanja drevo ni več uravnoteženo in potrebno je izvesti rotacijo.

Drevo po brisanju - potrebna je rotacija.

Drevo smo zarotirali v desno (leva rotacija). Po rotaciji spet preverimo ravnotežnostne faktorje in ugotovimo, da je sedaj AVL drevo v ravnotežju. Zgled je končan.

Po rotaciji je drevo spet v ravnotežju.

Prišli smo do konca snovi o AVL drevesih in sedaj je na vrsti krajši preizkus znanja.

Reši kviz

Preskoči kviz in zaključi

Ali drevo na sliki predstavlja AVL drevo?

V katero smer zarotiramo drevo pri levi rotaciji?

Katero rotacijo bi bilo potrebno izvesti, da bi spodnje drevo uravnotežili?

Preveri

Izračunaj ravnotežnostni faktor označenega vozlišča na sliki!

Odgovor:

Preveri

• Diplomska naloga Petra Tome - Uravnotežena dvojiška drevesa
• Katja Pipan - Seminarska naloga iz AVL dreves
• Tjaša Rebec in Maja Komljanovič - Seminarska naloga iz AVL dreves
• Jernej Kozak: Podatkovne strukture in algoritmi, DMFA, Ljubljana 1986.