Izpitno vprašanje RAČ2PRA 10600

Iz MaFiRaWiki

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 manjši od korena in v desnem poddrevesu večji od korena. Levo in desno poddrevo sta iskalni dvojiški drevesi.

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