Iskalno drevo/KlavdijaGerencer

Iz MaFiRaWiki

Ta članek ali del članka je v delu. Veseli bomo, če ga boste dopolnili in popravili.

Kaj pomeni to opozorilo?

Vsebina

Definicija

Iskalno dvojiško drevo je podatkovna struktura, kjer so elementi ( vozlišča ) urejeni tako, da so vrednosti elementov v levem poddrevesu manjše od vrednosti korena, vrednosti elementov v desnem poddrevesu pa so večje od vrednosti korena. V IDD ni podvojeni elementov.

Primer iskalnegadvojiškega drevesa

Vidimo, da je to dvojiško drevo urejeno po podatkih, kajti so vsi elementi v levem poddrevesu manjši ali enaki od korena in vsi elementi v desnem poddrevesu so večji ali enaki od korena.

Primer gradnje drevesa iz danih podatkov

Dane imamo podatke:

20, 10, 35, 5, 25, 37, 15, 12, 21, 1, 8, 28, 36

Iz teh podatkov želimo zgraditi urejeno dvojiško drevo.

Preden začnemo "gradit" naše drevo, ne smemo pozabiti na osnovno definicijo iskalnega dvojiškega drevesa, ki pravi, da mora bit levo poddrevo <= korenu drevesa in desno poddrevo >= korenu drevesa. Tole definicijo moramo upoštevat pri vsakem posameznem vstavljanu.

Postopek je naslednji:

- Vzamemo prvo številko, ta je 20. Ker je drevo prazno, ga vstavimo. Ta je sedaj koren.

- Naslednja številka je 10. Primerjamo ga s korenom ( 20 ). Ker je 10 < 20, ga vstavimo v levo poddrevo.

- Naslednja je 35. Ker je 35 > 20 ( vedno primerjamo s korenom! ), ga vstavimo v desno poddrevo.

- Naslednja je 5. Ker je 5 < 20, ga vstavimo v levo poddrevo. Vendar ne smemo pozabiti na 10 in številko 5 primerjat še s tem. Ker je 5 < 10, ga vstavimo v njegovo ( 10 ) levo poddrevo.

- Naslednja je 25. Ker je 25 > 20, gremo v desno in ker je 25 < 35, ga vstavimo v levo poddrevo od 35.

- Naslednja je 37. Ker je 37 > 20, gremo v desno in ker je 37 > 35, ga vstavimo v desno poddrevo od 35.

- Naslednja je 15. Ker je 15 < 20, gremo v levo in ker je 15 > 10, ga vstavimo v desno poddrevo od 10.

- Naslednja je 12. Ker je 12 < 20, gremo v levo in ker je 12 > 10, gremo v desno in ker je 12 < 15, ga vstavimo v levo poddrevo od 15.

- Naslednja je 21. Ker je 21 > 20, gremo v desno in ker je 21 < 35, gremo v levo in ker je 21 < 25, ga vstavimo v levo poddrevo od 25.

- Naslednja je 1. Ker je 1 < 20, gremo v levo; ker je 1 < 10, gremo v levo; ker je 1 < 5, ga vstavimo v levo poddrevo od 5.

- Naslednja je 8. Ker je 8 < 20, gremo v levo; ker je 8 < 10, gremo v levo; ker je 8 > 5, ga vstavimo v desno poddrevo od 5.

- Naslednja je 28. Ker je 28 > 20, gremo v desno; ker je 28 < 35, gremo v levo; ker je 28 > 25, ga vstavimo v desno poddrevo od 25.

- Naslednja je 36. Ker je 36 > 20, gremo v desno; ker je 36 > 35, gremo v desno; ker je 36 < 37, ga vstavimo v levo poddrevo od 37.


In smo dobili sledeče urejeno dvojiško drevo.


Primer vstavljanja elementa v že obstoječe iskalno dvojiško drevo

Predpostavimo, da že imamo podano iskalno dvojiško drevo in v tega želimo vstaviti še en element in pri tem bo dvojiško drevo še vedno urejeno. Seveda tudi tukaj ne smemo pozabiti na relacijo, da je levo poddrevo manjše ali enako korenu drevesa ter desno poddrevo večje ali enako korenu drevesa.

Podano imamo sledeče iskalno dvojiško drevo:


In v to iskalno dvojiško drevo želimo vstaviti 35.

Postopek vstavljanja:

- Vzamemo število 35.

- Pogledamo koren. Ker je 35 > 12, gremo v desno.

- Sedaj gledamo 99. Ker je 35 < 99, gremo levo od 99.

- Sedaj gledamo 24. Ker je 35 > 24, gremo desno od 24.

- Sedaj gledamo 30. Ker je 35 > 30, gremo desno od 30.

- Gledamo 40. Ker je 35 < 40, gremo levo od 40.

- In ker smo naleteli na list ( to je vozlišče s številko 40 ), vstavimo 35 v levo poddrevo od 40.


In smo dobili naslednje iskalno dvojiško drevo:

Primer iskanja elementa v urejenem dvojiškem drevesu

Imamo podano urejeno dvojiško drevo. V tem drevesu želimo poiskati določen element.

Podano imamo sledeče urejeno dvojiško drevo:

V tem drevesu želimo poiskati element 20.

Postopek iskanja elementa:

- Pogledamo koren ( 12 ). Ker je 20 > 12, gremo v desno poddrevo.

- Pogledamo naslednje vozlišče, t.j. 99. Ker je 20 < 99, gremo v levo poddrevo.

- Pogledamo 24. Ker je 20 < 24, gremo v levo poddrevo.

- Pogledamo 21. Ker je 20 < 21, gremo v levo poddrevo.

- Pogledamo 20. Ker je 20 = 20, smo našli naš iskani element.


Seveda pa obstajajo tudi primeri, ko iščemo element v iskalnem dvojiškem drevesu, vendar pa le tega ni.

Preizkusimo to naredit na našem iskalnem dvojiškem drevesu, ki je podan zgoraj in v njej iščimo element 8.

Postopek iskanja elementa:

- Pogledamo koren ( 12 ). Ker je 8 < 12, gremo v levo poddrevo.

- Pogledamo naslednje vozlišče, t.j. 4. Ker je 8 > 4, gremo v desno poddrevo.

- Pogledamo 9. Ker je 8 < 9, gremo v levo poddrevo.

- Pogledamo naslednje vozlišče, t.j. 7. Ker je 8 > 7, gremo v desno poddrevo.

- Vendar pa desno poddrevo od 7 ne obstaja, oz. je prazno. V tem primeru se naš postopek preneha, saj nismo našli željenega elementa.

Priporočam zanimivo spletno stran, kjer je lepo grafično prikazano iskanje elementa v iskalnem dvojiškem drevesu: Primer iskanja elementa v iskalnem dvojiškem drevesu

Časovna zahtevnost pri iskanju elementa v dvojiškem drevesu

Za iskanje podatka v iskalnem dvojiškem drevesu z n vozlišči potrebujemo v najslabšem primeru n primerjanj, kvečjemu pa :

log_{2}(n) = \frac{log_{10}(n)}{log_{10}(2)}

Pri našem primeru iskanja elementa je tole enako:

log_{2}(15) = \frac{log_{10}(15)}{log_{10}(2)} = 4

Kar pomeni, da imamo 15 povezav in za to rabimo približno 4 korake ( premike ), preden najdemo naš iskani element.

Za iskanje podatka v drevesu z 2 * n podatki ( vozlišči ) potrebujemo le 1 primerjavo več, sajti dvakrat več vozlišč kot v celotnem drevesu poveča njegovo višino oz. potrebno število iskanj le za 1.


Časovna zahtevnost pri vstavljanju elementa v že obstoječe iskalno dvojiško drevo

Pri vstavljanju elementa v že obstoječe urejeno dvojiško drevo potrebujemo n primerjav oz. premikov, se pravi toliko, kolikor je višina iskalnega dvojiškega drevesa.

V našem primeru vstavljanja elementa je višina drevesa 6, zato smo tudi rabili najmanj 6 primerjav in premikov, preden smo vstavili zaželjen element.





Glej tudi

Osebna orodja