Izpitno vprašanje RAČ2PRA 9000

Iz MaFiRaWiki

Vsebina

Vprašanje

Formalno opiši podatkovno strukturo dvojiško drevo. Navedi nekaj primerov uporabe te strukture.

Odgovor

Dvojiško drevo je v računalništvu drevesna podatkovna struktura. Dvojiško drevo je lahko prazno ali pa ga sestavlja t.i. vozlišče koren, ki sestavlja levo in desno poddrevo. Levo in desno poddrevo sta prav tako dvojiški drevesi. V vsakdanjem življenju lahko z dvojiškim drevesom predstavimo rodoslovne podatke. V teoriji grafov je dvojiško drevo definirano kot povezan neciklični graf, kjer stopnja nobene točke (vozlišča) ne presega števila 3. Število vozlišč drevesa imenujemo teža drevesa, dolžina najdaljše poti od korena do kateregakoli lista pa je globina drevesa.

Osnovni pojmi: OČE, SIN, LIST, KOREN, STOPNJA VOZLIŠČA, PREDNIKI, POTOMCI

Slika:ena.jpg

Nivo vozlišča: koren ima nivo 1, otroci korena nivo 2, otroci otrok nivo 3.

Globina vozlišča: koren ima globino 1, vozlišče, ki ni koren ima globino za 1 večje kot njegov oče.

Višina drevesa: listi imajo višino 1, vozlišče ki ni list ima za 1 večjo višino kot njegov max. potomec.

Drevo potomcev ni nujno dvojiško. Drevo prednikov je vedno dvojiško drevo.

Terminologija

vozlišče: element drevesa; ima podatek in informacijo o iz njega izhajajočih poddrevesih

list (končna vozlišča): vozlišča stopnje 0

notranja vozlišča: vsa razen listov

sin (ali naslednik): koren poddrevesa nekega vozlišča; v := sin(v)

oče (ali predhodnik): obratno; v := oče(v)

predniki: vozlišča na poti od korena do nekega vozlišča

stopnja vozlišča: podana s številom iz njega izhajajočih poddreves

stopnja drevesa: podana z najvišjo stopnjo njihovih vozlišč

nivo vozlišča: koren ima nivo 1; če ima oče nivo n ima sin novo n+1

višina drevesa: definirana z vozliščem z najvišjim nivojem

gozd: množica disjunktnih dreves

mejno drevo: vrstni red poodreves v vsakem vozlišču je podan in pomemben

Dvojiško drevo poznamo v obliki drevesne strukture. Loki potekajo od zgoraj navzdol. Leve sinove ločimo od desnih.

Slika:dva.jpg

Posebne oblike dvojiških dreves:

izrojeno dvojiško drevo

levo poravnano dvojiško drevo {200px}

Lastnosti dvojiških dreves: - Največje število vozlišč na nivoju i : 2i-1

npr: nivo = 3

št. vozlišč = 23-1 = 22 = 4

Slika:pet.jpg

- Največje število vozlišč v drevesu višine k:

nmax=\sum_{i=1}^k 2^{i-1} = 2^k-1
npr. višina = 3
n = 23 − 1 = 7

- Najmanjša višina drevesa z n vozlišči: logaritemska zahtevnost pri pregledih dreves


Struktura DVOJIŠKEGA DREVESA

declare  //  deklariranje metod v dvojiskem drevesu
   pripravi: 0 => dvojisko drevo;  // prazno dvojisko drevo
         sestavi: (dvojisko drevo, podatek, dvojisko drevo) => dvojisko drevo;  // v koren vstavimo       
                                // podatek in naredimo levo in desno dvojisko drevo
   vrni: dvojisko drevo => podatek;  // vrne podatek »koren« iz drevesa 
   levi sin: dvojisko drevo => dvojisko drevo; // levi sin korena
   desni sin: dvojisko drevo => dvojisko drevo;  //desni sin korena
   prazno: dvojisko drevo => {true, false};  // ce je prazno vrne true dugace false
where  // prikaz dolocenih primerov
   levi sin(pripravi) ::= NAPAKA;  // vrne napako
   levi sin(sestavi(l,k,d)) ::= l;  // sestavi levi sin
   desni sin(pripravi) ::= NAPAKA; // vrne napako
   desni sin(sestavi(l,k,d)) ::= d;  // sestavi desni sin
   prazno(pripravi) ::= true;  // vrne true ker je pripravi prazno
   prazno(sestavi(l,k,d)) ::= false; // false ker moramo sestaviti levo ali desno 
   vrni(pripravi) ::= NAPAKA; // vrne napako
   vrni(sestavi(l,k,d)) ::= k;  // vrne koren drevesa
end;

Uporaba dvojiškega drevesa

Imamo splošno urejeno dvojiško drevo in uporabimo premi pregled za izpis knjige po poglavjih.

Slika:sest.jpg

Dvojiško drevo lahko uporabimo za izpis aritmetičnega izraza. Uporabimo vmesni vrstni red. Izraz ((2x(a − 1)) + (3xb)) v dvojiškem drevesu

Slika:sedem.jpg

V splošnem urejenem drevesu lahko izračunamo skupno velikost datotek v imeniku. Uporabimo obratni (pregled) vrstni red. Slika:osem.jpg

Izračun vrednosti izraza

Algorithm evalExpr(v)
   if jeList(v)
      return v.element()
   else
      x<- evalExpr(leftChild(v))  
      y<- evalExpr(rightChild(v))
      ℵ<- operator v v
return x ℵ y

Osebna orodja