Iskalno drevo je podatkovna struktura, ki se uporablja v računalniškem programiranju, da vsebuje in organizira seznam podatkov. Vsako iskalno drevo je sestavljeno iz urejenega niza vozlišč. Ta vozlišča se lahko povežejo z nič ali več drugimi vozlišči. vozlišča. Posamezna vozlišča vsebujejo nekaj podatkov, pa tudi povezave do drugih vozlišč. Podatki, ki jih vsebujejo vozlišča drevesa, so zelo pogosto urejeni na nek način, da omogočajo učinkovitim algoritmom iskanje, z lahkoto vstavite in odstranite vozlišča.
Vozlišča drevesa iskanja so opisana s štirimi pomembnimi izrazi. Vrh drevesa, kjer se nahaja prvo vozlišče, se imenuje koren. Če vozlišče vsebuje povezave do pod -vozlišča, je to vozlišče znano kot nadrejeno. Vozlišča, ki so pod nadrejenim, se imenujejo podrejeni, vsako vozlišče, ki nima podrejenih vozlišč, pa se imenuje list. korensko vozlišče je identificirano, ker nima nadrejenega, listna vozlišča pa ne bodo imela otrok.
Program se lahko premika po drevesu in išče podatke tako, da začne na določenem vozlišču, izvede pogojno preverjanje in se nato premakne na naslednje logično vozlišče, če zahtevanih podatkov ni. Odvisno od uporabljene podatkovne strukture , lahko to iskanje traja različno dolgo. Če je drevo iskanja organizirano med postopkom dodajanja in odstranjevanja vozlišč, je iskanje lahko zelo hitro. Ko je drevo sestavljeno naključno, je nerazvrščen ali omogoča več staršev, iskanje lahko traja zelo dolgo.
Eden od dejavnikov, ki vpliva na uporabo dreves iskanja, je vprašanje ravnotežja. Uravnoteženo drevo je tisto, pri katerem desna in leva podrejena podrejenega vozlišča vsebujeta bodisi enako globino podrejenih vozlišč ali sta znotraj štetja enega vozlišča. drug drugega. Globina drevesa je število vozlišč od najnižjega lista drevesa do korena. Neuravnoteženo drevo ima lahko vsa vozlišča samo na eni strani ali pa vse vozlišča so razporejena linearno brez vej. Ko se globina drevesa poveča, se lahko hitrost iskalnih algoritmov dramatično zmanjša.
Obstajajo določene vrste dreves iskanja, ki so opisane kot samouravnotežena. Ta drevesa uporabljajo operacije, kot je vrtenje dreves, da pomagajo vzdrževati ravnovesje, hkrati pa ohranjajo vrstni red podatkov v listih. Čeprav izvajajo rotacije dreves lahko upočasnijo program pri dodajanju in odstranjevanju vozlišč, temu pa nasprotuje hitrost, s katero je mogoče pridobiti podatke.
Čeprav obstaja veliko vrst iskalnih dreves, je najpogostejša drevesna podatkovna struktura binarno iskalno drevo. Ta tip podatkov je sestavljen iz vozlišč, od katerih ima vsako od nič do dve podrejeni vozlišči. Obstaja samo eno korensko vozlišče, in vsi listi v drevesu so razvrščeni od leve proti desni v naraščajočih vrednostih glede na podatke, ki jih hranijo. Obstaja veliko algoritmov za binarna drevesa iskanja, ki lahko naredite naročanje podatkov zelo enostavno.
Za vozlišča drevesa iskanja ni enotne standardne izvedbe. Vozlišča so lahko predstavljena z najrazličnejšimi podatkovnimi strukturami. Uporabljajo se lahko nizi matrik, kot tudi množenje povezanih seznamov. drevo iskanja uporablja strukturo podatkov po meri, ki je zasnovana tako, da pomaga pri dokončanju potrebnih operacij, ki jih zahteva program. Nekatere standardne programske knjižnice vključujejo celo lastne notranje izvedbe dreves iskanja.