Binarno stablo

Stablo predstavlja važnu strukturu podataka, veoma pogodnu za modeliranje objekata koji oslikavaju hijerarhijsku organizaciju. Tako se stablom mogu predstavljati rodbinski i nasljedni odnosi u porodici (genealoško stablo), položaj ljudi na funkcijama, organizacija jedinica u vojsci, složeni matematički izrazi, skeletoni sportskih takmičenja itd. Očigledno sve ove aplikacije pokazuju prirodu grananja ili širenja organizacije po nivoima od vrha ka dnu.

Primjer stabla.

Definicije stabla i terminologija

Rekurzivna definicija

Stablo T je konačan, neprazan skup elemenata proizvoljnog tipa – čvorova takav da:

•  Postoji jedan poseban čvor koji se naziva korijen.
• Ostali čvorovi se mogu razdvojiti u n≥0 disjunktnih podskupova , koji su, također, stabla. Ova stabla se nazivaju podstablima korijena.

Definicija stabla je očigledno rekurzivna, jer se stablo definiše preko sebe samog, a u krajnjem slučaju stablo može da se svede samo na korijen. Zbog toga se ovakav tip stabala naziva korijenim stablom, za razliku od slobodnog stabla, koje se definiše kao posebna vrsta grafa.

Terminologija

Grane spajaju čvorove.

Ako se uoči neki čvor od kojeg se dalje granaju podstabla, onda se on smatra roditeljem čvorova koji predstavljaju korijene tih podstabala, a oni njegovom djecom. Ulazni stepen je broj grana koje ulaze u čvor, a izlazni stepen je broj grana koje izlaze iz čvora. Čvorovi sa nultim izlaznim stepenom nazivaju se listovi. Visina ili dubina stabla se određuje kao maksimalna vrijednost nivoa listova u stablu i to je najveća udaljenost nekog lista u stablu od korijena. Za dva stabla se kaže da su slična ako imaju istu strukturu, što znači da imaju isti broj čvorova i grana, kao i istu topologiju. Za dva stabla se kaže da su ekvivalentna ako su slična, a odgovarajući čvorovi imaju isti sadržaj. Uređeno stablo je stablo u kojem podstabla svakog čvora čine uređen skup (inače je neuređeno). Poziciona stabla stepena m su ona stabla kod kojih je svakom podstablu nekog čvora pridružena jedinstvena pozicija označena rednim brojem od 1 do m.

Predstavljanje stabala

Grafičko predstavljanje

Grafički se stablo najčešće predstavlja kao graf sa korijenom na vrhu, njegovom djecom ispod njega i tako sve do listova na dnu (za razliku od stabala u prirodi). Ova predstava najprirodnije odgovara terminu „stablo“. Pored toga, može da se koristi i predstava preko zagrada. Prvo se navodi korijen, a onda, u zagradi, njegova podstabla, koja se, zatim, na isti način u ugniježdenim zagradama predstavljaju preko svojih podstabala. Redoslijed pojavljivanja zagrada može da određuje i poredak djece u uređenim stablima.

Memorijska reprezentacija

Za predstavljanje stabala u memoriji se najčešće koristi ulančana reprezentacija. U tom načinu, čvor se predstavlja elementom koji, pored informacionog dijela (sadržaja), ima i pokazivače na djecu. Broj pokazivača može biti i promjenljiv, u zavisnosti od broja djece.  Mnogo pogodnije je, zbog alokacije i dealokacije prostora, da broj pokazivača po čvoru bude fiksan i jednak stepenu stabla, da se iniciraju samo pokazivači na postojeća podstabla, dok su ostali prazni.

Pored ulančanih, postoje i sekvencijalne reprezentacije. S obzirom da svaki čvor sem korijena ima samo jednog roditelja, stablo sa n čvorova se najprostije može predstaviti vektorom V[1:n] tako da svakom čvoru odgovara jedan element koji sadrži indeks roditelja toga čvora. Vrijednost prvog elementa koji odgovara korijenu je 0.

Treća, najvažnija sekvencijalna reprezentacija, također koristi vektor V[1:n] za smještanje čvorova stabla. Na prvo mjesto se smješta korijen, a zatim njegova djeca po njihovom pozicionom poretku, tako što se za nedostajuća podstabla ostave prazna mjesta. Zatim se nižu čvorovi iz drugog nivoa i tako redom.

Binarna stabla

Primjer binarnog stabla.

Binarno stablo se rekurzivno definiše kao konačan skup čvorova koji je ili prazan ili se sastoji od korijena sa dva posebna podstabla, lijevim i desnim, koja su, također, binarna stabla. Ono je po svojoj definiciji poziciono stablo.

Operacije umetanja i brisanja

Aktivnosti pri operacijama umetanja i brisanja zavise od ukazanog mjesta u stablu gdje se ubacuje novi čvor ili sa kojeg se briše čvor.

Primjer umetanja novog čvora.

Ako se čvor ubacuje kao list, onda jedino treba njegovom adresom popuniti odgovarajući pokazivač u čvoru roditelja. Ako se novi čvor ubacuje između nekog čvora (roditelja) i njegovog djeteta, onda novi čvor preuzima na toj strani od roditelja odgovarajući pokazivač na dijete, a roditelj sada ukazuje na novi čvor.

Primjer brisanja čvora.

Primjer brisanja čvora.

Kod brisanja lista iz čvora jedino treba u njegovom roditelju postaviti odgovarajući prazan pokazivač. Ako čvor koji se briše ima jedno dijete, pokazivač u čvoru njegovog roditelja koji je ranije ukazivao na čvor koji se briše, treba da se preusmjeri tako da pokazuje na dijete čvora koji se briše. Ukoliko čvor koji treba da se briše ima oba djeteta, situacija se usložnjava.

Obilazak binarnog stabla

U primjenama koje koriste binarna stabla često se javlja potreba sa pristupom svakom čvoru stabla u cilju neke obrade. U takvim slučajevima čvorovima treba pristupiti u sistematskom poretku i obraditi ih samo po jednom. Ovakva operacija se naziva obilaskom ili prolazom stabla. Kada se obilazi binarno stablo, svaki čvor i njegova podstabla se tretiraju na isti način i na njih se primijenjuju ista pravila. Konvencija da se lijevo podstablo uvijek posjećuje prije desnog daje tri uobičajena metoda obilaska: preorder, inorder, postorder.  Sva tri načina su važna i imaju svoje praktične primjene. Oni se definišu na rekurzivan način:

Preorder:

1. posjeti se korijen
2. obiđe se prvo lijevo podstablo na preorder način
3. obiđe se desno podstablo na preorder način

Inorder:

1. obiđe se lijevo postablo na inorder način
2. posjeti se korijen
3. obiđe se desno podstablo na inorder način

Postorder:

1. obiđe se lijevo podstablo na postorder način
2. obiđe se desno podstablo na postorder način
3. posjeti se korijen

Balansiranje stabla

Za binarno stablo se kaže da je balansirano ako za svaki čvor važi da se broj čvorova u njegovom lijevom i desnom podstablu ne razlikuje za više od 1. Da bi se dobilo još i stablo minimalne visine za dati broj čvorova, jasno je da čvorove treba distribuirati ravnomjerno na lijevo i desno podstablo, maksimalno popunjavajući sve nivoe osim posljednjeg.

To obezbjeđuje sljedeći rekurzivni algoritam:

1. uzme se jedan čvor kao korijen,
2. generiše se lijevo podstablo sa $nl=\llcorner n/2\lrcorner \upharpoonleft$
3. generiše se desno podstablo sa $nd=n-nl-1$ čvorova

Stablo dobijeno po ovom algoritmu je sigurno balansirano, ali, u opštem slučaju nije kompletno, jer posljednji nivo nije garantovano popunjen, a sigurno nije skoro kompletno, jer posljednji nivo nije sukcesivno popunjen. Međutim, ovako dobijeno stablo, također, postiže minimalnu visinu za dati broj čvorova. S druge strane, kompletno stablo jeste, a skoro kompletno stablo nije balansirano po ovom kriterijumu.

Binarna stabla pretrage

Binarno stablo pretrage, poznato i kao sortirano binarno stablo, je binarno stablo zasnovano na čvorovima, gdje svaki čvor ima uporedljivi ključ (sa dodijeljenom vrijednošću) i zadovoljava uslov da je vrijednost svakog čvora veća od vrijednosti svakog čvora u njegovom lijevom podstablu i manja od vrijednosti svakog čvora u njegovom desnom podstablu. Svaki čvor ima najviše dva djeteta. Svako dijete mora da bude ili list (nema nijedno dijete) ili korijen još jednog binarnog stabla pretrage.Najveća prednost binarnog stabla pretrage je da ostaje uređeno, što omogućava brže vrijeme pretrage nego većina drugih struktura.

Primjer binarnog stabla pretrage.

Za binarno stablo pretrage također vrijedi:

1. Prosječna dubina stabla je O(log N)
2. Maksimalna dubina stabla je O(N)
3. Algoritam za pretragu ima složenost O(dubina stabla)
4. Algoritmi za pronalaženje minimuma i maximuma imaju složenost O(dubina stabla)
5. Algoritam za umetanje ima složenost O(dubina stabla)
6. Algoritam za brisanje elementa ima složenost O(dubina stabla)

Binarno stablo pretrage je fundamentalna struktura podataka pomoću koje se konstruišu apstraktnije strukture podataka kao npr. skupovi, multiskupovi i asocijativni nizovi. Neki od nedostataka su:

• Oblik binarnog stabla pretrage zavisi samo od reda ubacivanja elemenata, i može biti degenerisano.
• Kada ubacujemo ili tražimo element u binarnom stablu pretrage, ključ svakog posjećenog čvora mora da se uporedi sa ključem elementa kog ubacujemo ili tražimo.
• Ključevi u binarnom stablu pretrage mogu biti dugački, što može uticati na vremensku složenost.

Predstavljanje aritmetičkih izraza

Primjer predstavljanja aritmetičkog izraza (a+b*c)+((d*e+f)*g) stablom.

Binarna stabla su veome pogodne strukture podataka za predstavljanje aritmetičkih izraza u kojima se javljaju unarni i binarni operatori i za manipulaciju sa njima. Zbog toga prevodioci mnogo koriste stabla pri analiziranju i parsiranju izraza, kao i pri generisanju koda za njihovo izračunavanje. Ako se posmatra izraz dat u infiksnoj notaciji, uočava se da se on može prirodno predstaviti binarnim stablom kod kojeg su čvorovima grananja pridruženi operatori, a lijevo i desno podstablo predstavljaju složene operande. Na kraju, listovi stabla označavaju proste operande – promjenljive i konstante. Obilaskom ovakvog stabla na razne načine mogu se dobiti varijante izraza u različitim notacijama.