Binarno stablo

Binarno stablo (engl. binary tree) 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

Skica binarnog stabla

• Č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.

Vidi još

• AVL-stablo
• Crveno-crno stablo