Izpitno vprašanje DIRI2005 10500

Iz MaFiRaWiki

Predmet Dopolnilno izobraževanje iz računalništva in informatike (DIRI)

Vsebina

Vprašanje

Sestavi algoritem, ki s pomočjo osnovnih operacij nad dvojiškim drevesom poišče minimalni in maksimalni element v drevesu.

Odgovor za iskano dvojiško drevo

Za iskano dvojiško drevo je značilno, da je levi sin vedno manjši, desni pa vedno večji od korena. Torej bi najmanjši element iskali skrajno levo v drevesu, največjega pa skrajno desno v drevesu.

Dvojiško drevo
Slika1: Dvojiško drevo.

V tem primeru je najmanjši element 0, največji pa 10.
Opomba: Namesto števil so v drevesu lahko tudi leksikografsko urejena gesla.

Algoritem za iskanje najmanjšega elementa

Začnemo v korenu, nato preverijamo ali ima vozel levega sina. Če ga ima se premaknemo nanj (ga obiščemo), če ga pa nima je to najmanjši oz. minimalni element.

dokler ima koren levega sina
    obišči levega sina
vrni koren

Metoda

Program, ki vrne min vrednost v nepraznem iskanem binarnem drevesu.

  1.  
  2. public int minVrednost() {
  3. return( minVrednost(root) );
  4. }
  5. private int minVrednost(Node node) {
  6. Node current = node;
  7. while (current.left != null) {
  8. current = current.left;
  9. }
  10.  
  11. return(current.data);
  12. }

Algoritem za izkanje maksimalnega elementa v iskalnem dvojiškem drevesu

Ta algoritem je obraten prejšnjemu.

dokler ima koren desnega sina
    obišči desnega sina
vrni koren

Poljubno dvojiško drevo

Poljubno dvojiško drevo
Slika2: Poljubno dvojiško drevo.

Glede na to, da drevo sedaj ni urejeno, torej elementi v drevesu niso razvrščeni po velikosti bo potrebno pregledati celotno drevo in primerjati element po element. Pri drevesih uporabljamo različne načine pregleda:

Dvojiško drevo - JavaApplet

Iskanje največjega elementa

Recimo, da se odločimo za premi pregled. V tem primeru najprej pregledamo koren in si ga zapomnimo (vrednost shranimo v spremenljivko npr. max), nato premo pregledamo levo poddrevo. To pomeni, da poiščemo maksimalni element v levem poddrevesu. Nato na enak način daredimo še premi prehod na desnem poddrevesu. V našem primeru (Slika2) bi bilo zaporedje dogodkov sledeče:

  • pregled korena
    • v max shrani vrednost 27
  • pregled levega poddrevesa
    • ugotovimo, da je maksimalni element v levem poddrevesu 71
  • ker je 71 več kot 27, je v max sedaj 71
  • pregled desnega poddrevesa
    • ugotovimo, da je maksimalni element v desnem poddrevesu 46
  • ker je 46 manj kot 71, spremeljivka max ostane nespremenjeva
  • v spremenljivki max je shranjena vrednost 71, ki jo vrnemo kot rezultat

Algoritem

  1. public int maxV(DVDrevo d) {
  2. if (d.prazno()) return -Integer.MIN_VALUE; // za prazno drevo vrnemo najmanjšo možno vrednost
  3. else {
  4. int maxVred = Math.max(d.koren(), maxV(d.levoPoddrevo());
  5. maxVred = Math.max(maxV(d.desnoPoddrevo(), maxVred);
  6. return maxVred;
  7. }
  8. }

iskanje najmanjšega elementa

Gre povsem podobno, le da začnemo pri praznem drevesu z največjo možno vrednostjo in uporabljamo minimum.

Osebna orodja