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.
*Implementacija z dvojiškim iskalnim drevesom
Ogledali smo si podatkovni strukturi za predstavitev množice v računalniku. Tabela elementov je preprosta, a neučinkovita tako za dodajanje kot odstranjevanje elementov. Tabela logičnih vrednosti je izjemno učinkovita, ima pa svojevrstno pomanjkljivost: v njej lahko hranimo le cela števila, znake in morda še kaj, gotovo pa ne realnih števil. Če v množici hranimo cela števila, mora biti razlika med največjim in najmanjšim številom razmeroma majhna, sicer tabela logičnih vrednosti zaseda ogromno praznega prostora.
V nadaljevanju se bomo seznanili s podatkovno strukturo, imenovano dvojiško iskalno drevo, ki je v večini primerov učinkovita za vse tri glavne operacije na množici, torej dodajanje, iskanje in odstranjevanje elementov. Dvojiško iskalno drevo je resda nekoliko manj učinkovito od tabele logičnih vrednosti, zato pa lahko vanj shranjujemo poljubne vrednosti, ne samo cela števila in znake. Preden se posvetimo dvojiškemu iskalnemu drevesu, pa se na kratko seznanimo s splošnimi dvojiškimi drevesi.
Dvojiško drevo
Dvojiško drevo je podatkovna struktura, podobna povezanemu seznamu, ki smo ga spoznali v učni enoti o zaporedjih. Dvojiško drevo je namreč prav tako sestavljeno iz posameznih vozlišč, le da ima vsako vozlišče dva naslednika namesto enega samega. Da ju bomo med seboj ločili, ju bomo poimenovali levi in desni naslednik. Vsako vozlišče tako poleg ustreznega elementa (v našem primeru elementa množice, ki jo bomo implementirali z drevesom) vsebuje tudi povezavi na oba naslednika. Vozlišče lahko vsebuje tudi povezavo na predhodnika, ni pa nujno:
Drevesa bomo risali v nekoliko poenostavljeni obliki, kakršna je prikazana na desni strani slike. V zgornjem primeru je levi naslednik vozlišča 10 (vozlišča z elementom 10, če smo natančnejši) vozlišče 7, desni naslednik vozlišče 15, predhodnik pa vozlišče 20. Vozlišče 15 ima samo levega naslednika, vozlišče 30 samo desnega, vozlišča 7, 12 in 35 pa nobenega. Nasledniku vozlišča pravimo tudi otrok, predhodniku pa oče, saj so programerska drevesa podobna družinskim, z malo domišljije pa tudi tistim v naravi, če jih obrnemo na glavo.
Vozlišče brez predhodnika imenujemo koren drevesa (20 v zgornjem primeru), vozlišča brez naslednikov pa so listi (7, 12 in 35 v zgornjem primeru). Levo poddrevo danega vozlišča je drevo, ki ga tvorijo levi naslednik tega vozlišča in vsi njegovi nasledniki, nasledniki naslednikov itd. Na podoben način definiramo desno poddrevo. Na primer, na zgornji sliki je levo poddrevo korena sestavljeno iz vozlišč 10, 7, 15 in 12, desno pa iz vozlišč 30 in 35. Levo poddrevo vozlišča 30 je prazno, desno pa vsebuje samo element 35.