Licenca
To delo je na voljo pod pogoji slovenske licence Creative Commons 2.5:
priznanje avtorstva - nekomercialno - deljenje pod enakimi pogoji.
Celotna licenca je na voljo na spletu na naslovu http://creativecommons.org/licenses/by-nc-sa/2.5/si/. V skladu s to licenco je dovoljeno vsakemu uporabniku delo razmnoževati, distribuirati, javno priobčevati, dajati v najem in tudi predelovati, vendar samo v nekomercialne namene in ob pogoju, da navede avtorja oziroma avtorje in izdajatelja tega dela. Če uporabnik delo predela, kar pomeni, da ga spremeni, preoblikuje, prevede ali uporabi to delo v svojem delu, lahko predelavo dela ponudi na voljo le pod pogoji, ki so enaki pogojem iz te licence oziroma pod enako licenco.
Slika
Slika
Rešitev
*Implementacija z dvojiškim iskalnim drevesom
Levi del spodnje slike prikazuje iskanje elementa 12. Ker je element 12 manjši od elementa v korenu (20), se pomaknemo v levega naslednika, torej v vozlišče 10. Iskani element 12 je večji od elementa 10, zato se pomaknemo v desnega naslednika, torej v vozlišče 15. Iskani element 12 je manjši od elementa 15, zato se zopet pomaknemo v levega naslednika. To vozlišče pa ravno vsebuje element 12, zato postopek končamo. Element smo našli!
Desni del spodnje slike pa prikazuje iskanje elementa 27. Postopek nas pripelje do levega naslednika vozlišča 30, vendar pa ta ne obstaja, zato lahko zaključimo, da drevo ne vsebuje elementa 27.
Element v dvojiško iskalno drevo najlažje dodamo kot nov list. Z iskalnim postopkom se spustimo po drevesu in na mestu, ki ga na koncu dosežemo, dodamo nov list. Če na poti navzdol naletimo na vozlišče z elementom, enakim tistemu, ki ga želimo dodati, postopek prekinemo, saj drevo predstavlja množico, ki ne sme vsebovati podvojitev. Spodnja slika prikazuje dodajanje elementov 18 in 32 v drevo, s katerim se ukvarjamo:
Vaja
Na papir nariši dvojiško iskalno drevo, ki ga dobimo, če v prazno drevo po vrsti dodamo elemente 10, 5, 15, 18, 9, 17, 12 in 7.
Kolikšna je časovna zahtevnost iskanja in dodajanja elementov? Pri obeh operacijah potrebujemo kvečjemu toliko primerjav in pomikov, kot je nivojev drevesa. Kot smo že izračunali, ima popolnoma uravnoteženo dvojiško iskalno drevo z n elementi log2(n + 1) nivojev, kar zahteva časovno zahtevnost O(log2n) (pri zapisu O(...) lahko zanemarimo nekatere konstantne člene in faktorje). Ta čas je bistveno krajši od časa O(n) pri tabeli elementov in le nekoliko daljši od časa O(1) pri tabeli logičnih vrednosti, pri čemer drevo nima nobene od omejitev te implementacije.
Časovna zahtevnost O(log2n) velja za drevesa, pri katerih so poti od korena do posameznih listov približno enako dolge. Pri skrajno neuravnoteženih drevesih, pri katerih ima vsako vozlišče (z izjemo edinega lista drevesa) enega samega naslednika, časovna zahtevnost iskanja in dodajanja postane O(n). Zato se v praksi pri dodajanju elementov pogosto uporabljajo postopki, ki drevo sproti preurejajo tako, da je vedno približno uravnoteženo.
Odstranjevanje elementov iz dvojiškega iskalnega drevesa je nekoliko težje, zato se z njim ne bomo ukvarjali. Omenimo le, da je časovna zahtevnost te operacije prav tako O(log2n), če je drevo vsaj približno uravnoteženo.
Simulacija
S pomočjo interaktivne simulacije razišči dvojiško iskalno drevo (ang. binary search tree). V drevo lahko elemente dodajaš, odstranjuješ ali pa jih v drevesu iščeš. Lahko se tudi sprehodiš po elementih drevesa.