Izpitno vprašanje DIRI2005 10500

Iz MaFiRaWiki

(Razlika med različicami)
Različica od 11:26, 27 maj 2008
MatijaLokar (Pogovor | prispevki)
Algoritem
← Prejšnja različica
Različica od 11:31, 27 maj 2008
MatijaLokar (Pogovor | prispevki)
Iskanje največjega elementa
Naslednja različica →
Vrstica 48: Vrstica 48:
[http://http://lsdis.cs.uga.edu/~aleman/mams/csci6900/hci/partc/bintree/prototype.php Dvojiško drevo - JavaApplet] [http://http://lsdis.cs.uga.edu/~aleman/mams/csci6900/hci/partc/bintree/prototype.php Dvojiško drevo - JavaApplet]
==Iskanje največjega elementa== ==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 in sproti preverjamo, če je morda kak element večji od elementa, ki ga hranimo v spremenljivki max. Če je, shranimo v spremenljivko max vrednost večjega elementa, če pa ne, pa nadaljujemo s pregledom.+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. Nato na enak način daredimo še premi prehod na desnem poddrevesu.
V našem primeru (Slika2) bi bilo zaporedje dogodkov sledeče: V našem primeru (Slika2) bi bilo zaporedje dogodkov sledeče:
* pregled korena * pregled korena
** v max shrani vrednost 27 ** v max shrani vrednost 27
-* premi pregled:+* pregled levega poddrevesa
-** 13 nadaljuje+** ugotovimo, da je maksimalni element v levem poddrevesu 71
-** 6 nadaljuje+* ker je 71 več kot 27, je v max sedaj 71
-** 7 nadaljuje+* pregled desnega poddrevesa
-** 23 nadaljuje+** ugotovimo, da je maksimalni element v desnem poddrevesu 46
-** 8 nadaljuje+* ker je 46 manj kot 71, spremeljivka max ostane nespremenjeva
-** 71 v max shrani vrednost 71, nadaljuje+* v spremenljivki max je shranjena vrednost 71, ki jo vrnemo kot rezultat
-** 11 nadaljuje + 
-** 43 nadaljuje +
-** 1 nadaljuje +
-** 46 nadaljuje +
-** 32 konec +
-v spremenljivki max je shranjena vrednost 71.+
=Algoritem= =Algoritem=
<java>public int maxV(DVDrevo d) { <java>public int maxV(DVDrevo d) {

Različica od 11:31, 27 maj 2008

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(maxV(d.levoPoddrevo(), d.koren());
  5. maxVred = Math.max(maxV(d.desnoPoddrevo(), maxVred);
  6. return maxVred;
  7. }
  8. }

iskanje najmanjšega elementa

Seveda je to le obrnjena slika iskanja največjega elementa.

Osebna orodja