Binarno stablo

**Binarno stablo** () je u informatici struktura namenjena čuvanju podataka. Njene memorijske jedinice su organizovane po principu piramide. 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*). Od ovog elementa se može doći u bilo koji drugi elemenat stabla. Svaki elemenat stabla može biti i svestan koji elemenat pokazuje na njega (tj. ko mu je *roditelj*).

## Osnovni pojmovi

* **Čvor stabla** je jedna memorijska ćelija stabla. Ona može imati nula, jedan ili dva podčvora. Ista može da nosi dve različite vrednosti:
** Ključ. Najčešće numerička vrednost, po kojoj se neki element raspoređuje u binarnom stablu
** Vrednost. Podatak koji treba zapamtiti. Može se desiti da su vrednost i ključ jedno te isto, tj. da se sortiranje binarnog stabla vrši po samoj vrednosti.
* **Koren stabla** je čvor stabla koji nije podčvor nijednog drugog čvora u stablu.
* **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

U vezi sa slikom desno: **čvorovi** stabla su elementi prikazani krugovima. Upisani brojevi su vrednosti ključeva po kojima se elementi sortiraju. Čvor sa ključem 8 je **koren** stabla. Njegova **deca** su čvorovi sa ključevima 3 i 10. **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.

* **Podstablo** ili **podgrana** je skup svih čvorova stabla koji se nalaze levo ili desno od nekog od čvorova stabla

## Operacije
Iako sortirano, binarno stablo ne garantuje brzinu izvođenja operacija. 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). Slično je i sa ostalim operacijama.

### Pretraga
Pretraga počinje od korena stabla. Sledi jedan od algoritama:

* 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

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

### Brisanje elementa
Brisanje elementa iz stabla je najsloženiji od ova tri procesa. U zavisnosti od toga koliko dece ima, deli se u tri slučaja:
* Ukoliko čvor za brisanje **nema dece**. Treba obrisati čvor, a njegovo mesto kod roditelja treba da bude naznačeno kao prazno.
* Ukoliko čvor za brisanje ima **jedno dete**. Čvor treba obrisati, a njegovo mesto kod roditelja zauzima njegovo dete.
* Ukoliko čvor za brisanje ima **dvoje dece**. Čvor treba obrisati, a njegovo mesto i ulogu zauzima ili „najlevlji“ čvor njegove desne podgrane, ili „najdesniji“ čvor njegove leve podgrane. 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.

## Povezano
* AVL-stablo
* Crveno-crno stablo

## Vanjske veze