Izpitno vprašanje RAČ2PRA 10600

Iz MaFiRaWiki

(Razlika med različicami)
Različica od 09:44, 14 maj 2006
AleksandraVujasin (Pogovor | prispevki)
Lastnosti
← Prejšnja različica
Različica od 09:49, 14 maj 2006
AleksandraVujasin (Pogovor | prispevki)

Naslednja različica →
Vrstica 5: Vrstica 5:
== Odgovor == == Odgovor ==
-* Definicija: dvojiško drevo, za katerega velja, da so vsi elementi v levem poddrevesu (ki je tudi iskalno drevo) manjši od korena in v desnem poddrevesu večji od korena. Tudi desno poddrevo je iskalno dvojiško drevo.+* Definicija: [[Dvojiško drevo|dvojiško drevo]], za katerega velja, da so vsi elementi v levem poddrevesu (ki je tudi iskalno drevo) manjši od korena in v desnem poddrevesu večji od korena. Tudi desno poddrevo je iskalno dvojiško drevo.
=== Lastnosti === === Lastnosti ===
Vrstica 21: Vrstica 21:
** ne najdemo podatka v drevesu ** ne najdemo podatka v drevesu
** ne pridemo do lista (podatek še ni v drevesu, zato ga vstavimo) ** ne pridemo do lista (podatek še ni v drevesu, zato ga vstavimo)
-Primer:+===Primer===
Vstavi v iskalno dvojiško drevo števila: 50, 3, 15, 60, 8. Vstavi v iskalno dvojiško drevo števila: 50, 3, 15, 60, 8.
Vrstica 64: Vrstica 64:
}</graphviz> }</graphviz>
-5.korak: v drevo vstavimo število 8. Ker je 8 < 50 se premaknemo v levo poddrevo, 8 > 3 zato se premaknemo v desno poddrevo, 8 < 15 zato se premaknemo v levo poddrevo in število 15 vstavimo v list. +5.korak: v drevo vstavimo število 8. Ker je 8 < 50 se premaknemo v levo poddrevo, 8 > 3 zato se premaknemo v desno poddrevo, 8 < 15 zato se premaknemo v levo poddrevo in število 8 vstavimo v list.
<graphviz layout="neato"> <graphviz layout="neato">
graph G { graph G {

Različica od 09:49, 14 maj 2006

GFDL Avtor tega članka je študent/ka AnjaRožac.

Pripravil/a ga je pri predmetu Računalništvo 2 (FMF PRA).


Kljub temu ste vsi vabljeni k urejanju in popravkom, saj je bistvo wikija ravno v sodelovalnem delu.

Vsebina

Vprašanje

Iskalno dvojiško drevo-lastnosti, primer uporabe,...

Odgovor

  • Definicija: dvojiško drevo, za katerega velja, da so vsi elementi v levem poddrevesu (ki je tudi iskalno drevo) manjši od korena in v desnem poddrevesu večji od korena. Tudi desno poddrevo je iskalno dvojiško drevo.

Lastnosti

  • iskanje podatkov je lahko dokaj hitro:
    • odvisno je od učinkovitosti predstavitve
    • ni podvojenih elementov
  • iskalno dvojiško drevo vsebuje podatke, urejene po enem ključu: za vsako vozlišče velja, da monožica podatkov v levem poddrevesu ni večja od podatka v korenu in množica podatkov v desnem poddrevesu ni manjša od podatka v korenu.

Vstavljanje podatka v iskalno dvojiško drevo

  • začnemo pri korenu in se pomikamo proti listom
  • podatek, ki ga vstavljamo primerjamo s podatkom v korenu:
    • če je podatek manjši od korena se premaknemo v levo poddrevo
    • če je podatek večji od korena pa se pomaknemo v desno poddrevo
  • postopek ponavljamo dokler:
    • ne najdemo podatka v drevesu
    • ne pridemo do lista (podatek še ni v drevesu, zato ga vstavimo)

Primer

Vstavi v iskalno dvojiško drevo števila: 50, 3, 15, 60, 8.

1.korak: v drevo vstavimo število 50

2.korak: v drevo vstavimo število 3. Ker je 3 < 50 ga vstavimo v list levega poddrevesa.

3.korak: v drevo vstavimo število 15. Ker je 15 < 50 se premaknemo v levo poddrevo, 15 > 3 zato se premaknemo v desno poddrevo in vstavimo število 15 v list.

4.korak: v drevo vstavimo število 60. Ker je 60 > 50 vstavimo število 60 v list desnega poddrevesa.

5.korak: v drevo vstavimo število 8. Ker je 8 < 50 se premaknemo v levo poddrevo, 8 > 3 zato se premaknemo v desno poddrevo, 8 < 15 zato se premaknemo v levo poddrevo in število 8 vstavimo v list.

Osebna orodja