Binarno stablo
<s>Binarno stablo () je u informatici struktura namenjena čuvanju podataka.</s><s>Njene memorijske jedinice su organizovane po principu piramide.</s><s>Tačnije, svaka memorijska jedinica (čvor) binarnog stabla može da pokazuje na još najviše dva elementa (njegova deca), dok stablo ima samo jedan elemenat na koga ne pokazuje ni jedan drugi (koren).</s><s>Od ovog elementa se može doći u bilo koji drugi elemenat stabla.</s><s>Svaki elemenat stabla može biti i svestan koji elemenat pokazuje na njega (tj. ko mu je roditelj).</s>

<s>Osnovni pojmovi</s>

<s>Čvor stabla je jedna memorijska ćelija stabla.</s><s>Ona može imati nula, jedan ili dva podčvora.</s><s>Ista može da nosi dve različite vrednosti:
 Ključ.</s><s>Najčešće numerička vrednost, po kojoj se neki element raspoređuje u binarnom stablu
 Vrednost.</s><s>Podatak koji treba zapamtiti.</s><s>Može se desiti da su vrednost i ključ jedno te isto, tj. da se sortiranje binarnog stabla vrši po samoj vrednosti.</s><s>Koren stabla je čvor stabla koji nije podčvor nijednog drugog čvora u stablu.</s><s>List je čvor stabla koji nema ni jedan podčvor
 Roditelj nekog čvora je čvor koji pokazuje na njega
 Dete nekog čvora je čvor na koji neki drugi čvor pokazuje</s>

<s>U vezi sa slikom desno: čvorovi stabla su elementi prikazani krugovima.</s><s>Upisani brojevi su vrednosti ključeva po kojima se elementi sortiraju.</s><s>Čvor sa ključem 8 je koren stabla.</s><s>Njegova deca su čvorovi sa ključevima 3 i 10.</s><s>Roditelj čvorova sa vrednošću ključeva 3 i 10 je čvor sa ključem 8. Listovi stabla su čvorovi sa ključevima 1, 4, 7 i 13.</s>

<s>Podstablo ili podgrana je skup svih čvorova stabla koji se nalaze levo ili desno od nekog od čvorova stabla</s>

<s>Operacije 
Iako sortirano, binarno stablo ne garantuje brzinu izvođenja operacija.</s><s>Traženje elementa u stablu npr. može da varira od -{O(log n)}- u najboljem (kao kod binarne pretrage) do -{O(n)}- u najgorem slučaju (kao kod linearne pretrage nesortiranog niza).</s><s>Slično je i sa ostalim operacijama.</s>

<s>Pretraga 
Pretraga počinje od korena stabla.</s><s>Sledi jedan od algoritama:</s>

<s>Uporedi vrednost traženog ključa sa vrednošću ključa trenutno ispitivanog čvora
 Ukoliko je ključ veći, ispitati desno (levo) dete
 Ukoliko je ključ manji, ispitati levo (desno) dete
 Ukoliko je ključ jednak, trenutno ispitivani čvor je traženi čvor
 Ako dete ka kome treba da se nastavi pretraga ne postoji, onda tražena vrednost ključa na postoji u stablu</s>

<s>Dodavanje novog elementa 
Pretragom (v. gore) se ustanovljava da elementa koji treba dodati u stablu nema.</s><s>Potom se na mestu deteta koje nije postojalo pravi novi element sa datim ključem i podacima.</s>

<s>Brisanje elementa 
Brisanje elementa iz stabla je najsloženiji od ova tri procesa.</s><s>U zavisnosti od toga koliko dece ima, deli se u tri slučaja:
 Ukoliko čvor za brisanje nema dece.</s><s>Treba obrisati čvor, a njegovo mesto kod roditelja treba da bude naznačeno kao prazno.</s><s>Ukoliko čvor za brisanje ima jedno dete.</s><s>Čvor treba obrisati, a njegovo mesto kod roditelja zauzima njegovo dete.</s><s>Ukoliko čvor za brisanje ima dvoje dece.</s><s>Čvor treba obrisati, a njegovo mesto i ulogu zauzima ili „najlevlji“ čvor njegove desne podgrane, ili „najdesniji“ čvor njegove leve podgrane.</s><s>Ovi čvorovi mogu imati jedno ili nijedno dete, a treba ih istim ovim algoritmom obrisati sa mesta na kome su bili pre nego što preuzmu novu ulogu u stablu.</s>

<s>Vidi još 
 AVL-stablo
 Crveno-crno stablo</s>

<s>Spoljašnje veze</s>

<s>Strukture podataka
Informatika
Algoritmi</s>

