Šta je binarno stablo?
Osnovne ideje:
- Hijerarhijska organizacija: Čvorovi predstavljaju podatke, a grane pokazuju odnose između tih podataka. Na primer, u porodičnom stablu, svaka osoba bi bila čvor, a grane bi pokazivale veze između roditelja i dece.
- Korenski čvor: Ovo je čvor na vrhu drveta, od kojeg sve ostalo “potiče”. Na primer, “glava porodice” u porodičnom stablu.
- Listovi: To su čvorovi na krajevima drveta, koji nemaju potomke. U porodičnom stablu, to bi bili ljudi koji nemaju decu.
- Dubina i visina: Dubina meri koliko je neki čvor udaljen od korena, a visina pokazuje najdužu udaljenost od tog čvora do nekog lista.
Zašto su drveća korisna?
- Efikasno upravljanje podacima: Pošto su hijerarhijski organizovana, drveća omogućavaju lako pretraživanje i manipulaciju podacima. Na primer, u pretraživačima fajlova koristiš stablo da brzo pronađeš željeni folder ili fajl.
- Fleksibilnost: U drveću, svaki čvor može imati više “dece” (veza), što omogućava da se lako modeluju složeni odnosi, poput porodičnih veza ili struktura preduzeća.
- Podstabla: Velika stabla mogu se “razložiti” na manje delove, što olakšava rad s njima. Zamislimo da radimo sa ogromnim brojem podataka – podstabla nam omogućavaju da ih analiziramo deo po deo.
Prolazak kroz stablo
- In-order obilaženje
- Prvo ideš skroz levo, sve dok ne naiđeš na list (čvor koji nema decu)
- Onda se vratiš na njegov roditeljski čvor (koren)
- Na kraju pogledaš desno dete
- Kod binarnih stabala pretrage ovo ti daje elemente u rastućem redosledu (sortirano)
- Post-order obilaženje
- Ovde ideš na decu pre nego na roditelje
- Prvo obiđeš levo dete, zatim desno, pa tek onda koren
- Ovo je korisno kada trebaš da izbrišeš celo stablo, jer brisanje počinje od listova, pa ide prema korenu (sigurno je jer nema referenci na čvorove koji su već obrisani)
- Pre-order obilaženje
- Kreneš od korena, pa ideš levo, pa desno
- Ovo je korisno kada, recimo, želiš da napraviš kopiju stabla ili da ga sačuvaš u fajlu jer čuva strukturu kako jeste
Pravljenje binary search tree
Ubacivanje elemenata u binary search tree se zasniva na principu upoređivanja. Elementi se poređuju sa trenutnim čvorom i odlučuje se da li će biti smešteni u levu ili desnu podstablu. Postoje četiri ključna slučaja pri ubacivanju:
- Ako je novi element manji od trenutnog, ide u levo podstablo
- Ako je veći, ide u desno podstablo.
- Ako je jednak trenutnom elementu, odlučuje se da li će biti dozvoljeni duplikati (ubaciti ga ili ignorisati).
- Ako se dođe do null čvora, stvorimo novi čvor i ubacimo element.