Uvod
Operacije obilaska, tipično nisu prvo što nekome može pasti na pamet kada se govori o stablima pretrage, ali, značaj navedenih operacija sasvim je nezanemarljiv i u AVL stablima (i drugim stablima za pretragu), i takođe, obilasci stabla su veoma zanimljivi sami po sebi (kao deo opšteg obrazovanja) - i veoma korisni u drugim algoritmima.
U AVL stablu, preko BFS obilaska, može se prikazati struktura stabla - po nivoima, a inorder varijanta DFS obilaska, može se iskoristiti za generisanje liste koja sadrži elemente stabla koji su sortirani u rastući poredak. *
Preostale dve varijante DFS obilaska (preorder i postorder), u slučaju AVL stabla ne igraju preveliku ulogu, ali su zato (i te kako) bitne u slučaju implementacije algoritma Shunting Yard, kao i u stablima izraza (srodni algoritmi kojima smo posvetili zasebne članke).
Obilazak stabla - osnovna ideja
Obilazak stabla je operacija koja podrazumeva pristup svakom pojedinačnom elementu, uz što manje poseta, što se dalje može iskorititi za ispis sadržaja stabla, kreiranje statičkog niza ili liste (sa vrednostima iz stabla), ili na neki drugi način.
U osnovnom smislu, stablo je moguće obići na dva načina, na koje smo se osvrnuli u članku o pronalaženju putanja kroz lavirint (iako struktura "lavirinta" nije isto što i struktura stabla, osnovni principi su isti).
U pitanju su algoritmi:
- BFS - obilazak "po širini"
- DFS - obilazak "u dubinu"
Algoritmi BFS i DFS su (kao što smo objasnili u pomenutom članku), prevashodno algoritmi pretrage (Breadth/Depth First Search - eng. pretraga), ali se nazivi BFS i DFS koriste i kada su u pitanju obilasci stabala i grafova (i stoga ćemo u nastavku i dalje upotrebljavati dva pomenuta termina).
BFS - Obilazak stabla "po širini"
BFS obilazak podrazumeva da se čvorovima pristupa (ili jednostavnije, da se čvorovi ispisuju) - "nivo po nivo": prvo se obilazi (ispisuje) koreni čvor, potom dva njegova direktna potomka, zatim potomci direktnih potomaka korenog čvora, pa redom ostatak stabla (nivo-po-nivo), sve do 'listova' (to jest, čvorova koji nemaju potomke).
U implementaciji BFS obilaska koristićemo red za čekanje (queue) i sprovesti obilazak po sledećem postupku:
Algoritam započinje smeštanjem korenog čvora u red za čekanje, posle čega sledi petlja koja ima sledeća svojstva:
- na početku svake iteracije uzima se u obradu (i uklanja iz reda), element sa početka reda
- direktni potomci izdvojenog elementa smeštaju se na kraj reda
- petlja se završava onda kada - pri ispitivanju uslova za (ponovni) ulazak u petlju - u redu za čekanje nema više elemenata za obradu
U stablu koje smo do sada koristili za primere ....
.... BFS obilazak ima sledeći tok ....
Prvo se u red za čekanje smešta čvor #10 (koreni čvor):
.... i potom algoritam ulazi u petlju.
Petlja se "načinje" preuzimanjem čvora sa početka reda:
Sama vrednost čvora koji je u obradi (10), direktno se ispisuje, a pre toga se pronalaze 'potomci' čvora #10 (čvorovi #5 i #15) i smeštaju u red za čekanje:
Već na ovom mestu, možemo uvideti zašto nismo odmah (bez ubacivanja u red), uzeli koreni čvor "u razmatranje". Ukoliko smestimo koreni čvor u red i pokrenemo petlju (kao što smo i učinili), važe sledeća pravila:
- u trenutku kada se petlja pokreće, red nije prazan (što znači da je uslov za ulazak u petlju zadovoljen)
- posle uklanjanja korenog čvora iz reda, red jeste prazan (ali)
- u tom trenutku petlja je već pokrenuta i pre nego što se program vrati na ispitivanje uslova, moraju se izvršiti naredbe iz tela petlje
- u toku izvršavanja tela petlje, u red za čekanje se ubacuju dva nova čvora (potomci korenog čvora, čvorovi #5 i #15)
- kada se program vrati na ispitivanje uslova, red (ponovo) nije prazan
Vidimo sada, da "čudni" korak ubacivanja korenog čvora u red, posle čega se ubačeni čvor odmah uklanja iz reda, zapravo ima smisla. Takav postupak predstavlja elegantan način organizacije petlje, u kome opšta pravila važe u svakom koraku, a ne samo u "svim koracima osim prvog".
U nastavku, preuzima se iz reda čvor #5 ....
.... ispisuje se vrednost čvora, a u red se smeštaju potomci (zapravo, samo jedan potomak - čvor #7):
Sledeći čvor koji se preuzima iz reda, je čvor #15 ....
.... ispisuje se vrednost 15 i u red se smeštaj potomci, čvorovi #12 i #22 ....
Dalje se iz reda preuzima čvor #7 ....
.... vrednost se ispisuje, ali, budući da dati čvor nema potomke, iz reda se odmah preuzima sledeći čvor (#12):
Budući da ni čvor #12 nema potomke, samo se ispisuje vrednost 12 i nastavlja se sa preuzimanjem čvorova iz reda ....
Ispisuje se vrednost čvora #22 i u red se smeštaju potomci (čvorovi #17 i #24)
Čvor #17 ....
.... nema potomke, kao ni čvor #24 ....
.... tako da nije bilo dodavanja novih čvorova u red (ali su, naravno, vrednosti čvorova #17 i #24 - ispisane).
Takođe, budući da je red za čekanje ispražnjen ....
.... zaključujemo da smo završili sa petljom (odnosno, sa BFS obilaskom stabla).
BFS obilazak - implementacija
BFS obilazak stabla može se implementirati na sledeći način:
public void BFS_Ispis() {
Queue<Cvor> red = new LinkedList<Cvor>(),
sledeci = new LinkedList<Cvor>(), pom;
boolean reseno = false;
red.add(Koren);
while (!reseno) {
while (!red.isEmpty()) {
Cvor C = red.remove();
System.out.printf("%d(%d %d) ", C.Vrednost, C.Visina, C.BalansFaktor);
if (C.Levi != null) sledeci.add(C.Levi);
if (C.Desni != null) sledeci.add(C.Desni);
}
System.out.printf("\n");
pom = red;
red = sledeci;
sledeci = pom;
reseno = red.isEmpty() && sledeci.isEmpty();
}
}
Kao što vidimo, implementacija je prilično jednostavna, dosledno sledi principe koje smo izneli, ali - uz mali dodatak: "spratovi" AVL stabla ispisuju se red-po-red (uz dodatni ispis visine i faktora balansa za svaki čvor).
DFS - Obilazak stabla "u dubinu"
Pre nego što započnemo priču o DFS algoritmima, iznećemo jedno opažanje koje čitaocima može biti od koristi.
Za razliku od algoritma BFS, koji ima jednostavnu ideju, ali ne baš skroz jednostavnu implementaciju (iz perspektive većine mladih programera/studenata I i II godine fakulteta), DFS algoritmi nisu baš skroz jednostavni za razumevanje pri prvom susretu (sa druge strane, uz ponešto truda, taj prvobitni utisak se lako prevazilazi), ali je zato implementacija DFS algoritama - pod uslovom da onaj ko piše implementaciju dobro razume rekurziju - krajnje jednostavna.
DFS obilasci podrazumevaju pronalaženje elemenata (a u našem slučaju, i ispis) - "po dubini" stabla.
U praktičnom smislu, bilo koji DFS obilazak (koji navodimo), podrazumeva da se "držimo leve strane stabla", "dokle god je moguće", a da se udesno prelazi onda kada "nema dalje levo" (naravno, uz povratak jedan korak unazad, na poslednju "raskrsnicu" - pre nego što 'skrenemo desno').
Šematski to možemo prikazati na sledeći način (slika ipak vredi "toliko-i-toliko" reči):
Opisani princip pristupanja čvorovima stabla, omogućava tri različite varijante DFS obilaska:
- preorder (koreni čvor - levo podstablo - desno podstablo)
- inorder (levo podstablo - koreni čvor - desno podstablo)
- postorder (levo podstablo - desno podstablo - koreni čvor)
Naravno, da bismo se upoznali kako dolikuje sa svime što smo naveli, razmotrićemo detaljno sva tri algoritma.
Preorder obilazak stabla
Preorder obilazak stabla podrazumeva obilazak (i ispis čvorova, popunjavanje liste, ili neku drugu operaciju), po sledećem redosledu:
- koreni čvor
- celokupno levo podstablo
- celokupno desno podstablo
Dakle, posmatrano za bilo koji čvor u stablu, važi pravilo da će prvo biti ispisan dati čvor, potom levo podstablo, a zatim i desno podstablo.
Usvojićemo i šematski prikaz, u kome se crvenom bojom označava deo stabla koji se ispisuje odmah, zelenom bojom - deo stabla koji je drugi po redu za ispis, a plavom bojom - deo stabla koji je treći po redu za ispis (R-G-B).
U konkretnom primeru koji koristimo, navedeni šematski prikaz ima sledeći oblik:
Iz prikazanog možemo zaključiti da će prvo biti ispisan koreni čvor (10), potom čvorovi #5 i #7 (tek pošto bude ispisan koreni čvor), a zatim i čvorovi #12, #15, #22, #17 i #24 (tek pošto budu ispisani koreni čvor i levo podstablo).
Počinjemo sa ispisom i shodno pravilu "koren - levo podstablo - desno podstablo", prvo se ispisuje vrednost 10:
Potom se prelazi na levo podstablo korenog čvora i ispisuje vrednost korenog čvora podstabla (5):
.... a zatim, budući da levog podstabla nema, ispisuje se desno podstablo (u praktičnom smislu - samo čvor #7):
Budući da smo sada završili sa korenom stabla (čvor #10) i levim podstablom, prelazimo na desno podstablo.
Kada pređemo na desno podstablo, prvo se ispisuje koren podstabla (15):
.... zatim levo podstablo ....
.... i na kraju, krajnje desno podstablo.
Za kraj, ispisuje se prvo koreni čvor preostalog podstabla (čvor #22) ....
.... zatim levo podstablo (praktično - samo čvor #17):
.... i na kraju desno podstablo (praktično - samo čvor #24):
Obilazak je završen ....
.... i sve vrednosti su ispisane.
Preorder obilazak stabla - Implementacija
Obećali smo da će implementacija DFS algoritama (pod uslovom da dobro razumete rekurziju), biti krajnje jednostavna ....
public void DFSIspisPreorder(Cvor C) {
if (C == null) return;
System.out.printf("%d ", C.Vrednost);
DFSIspisPreorder(C.Levi);
DFSIspisPreorder(C.Desni);
}
.... i verujemo da ćete se složiti da vas uopšte nismo 'prevarili'.
Ako se dvoumite oko implementacije koju ste videli, slobodno koji put 'provucite' stablo iz primera kroz navedeni algoritam.
Kao što vidimo, sve funkcioniše (doslovno) onako kako smo naveli na početku i za svaki čvor važi:
- prvo se ispisuje vrednost datog čvora
- zatim se ispisuje celo levo podstablo
- na kraju se ispisuje celo desno podstablo
Inorder obilazak stabla
Inorder obilazak stabla podrazumeva obilazak (i ispis čvorova, smeštanje u listu, ili neku drugu operaciju), po sledećem redosledu:
- celokupno levo podstablo
- koreni čvor
- celokupno desno podstablo
Kao što smo naveli u uvodnom odeljku, preko inorder obilaska, elementi stabla se mogu ispisati u rastućem poretku (odnosno, istim redosledom, od elemenata se može formirati lista, statički niz i sl).
Ovoga puta, šematski prikaz obilaska ima sledeći oblik:
.... i mnogi čitaoci mogu se zapitati: kako će tačno biti ispisano levo podstablo?
Odgovor je (ponovo) - shodno prethodno navedenim pravilima. :)
Budući da levo podstablo (prvobitnog levog podstabla) ne postoji, ispisuje se prvo, koreni čvor podstabla (5).
Potom se prelazi na desno podstablo (čiji je koren čvor #7):
Budući da čvor #7 nema levo podstablo, može se ispisati vrednost korenog čvora podstabla (7), a zatim, s obzirom na to da čvor #7 nema ni desno podstablo, možemo se vratiti korak unazad, na čvor #5.
Pošto je čvor #5 (već) rešen, možemo se vratiti još jedan korak unazad, skroz do korenog čvora početnog stabla (čvor #10).
Sada, kada je rešeno celo levo podstablo početnog stabla (čiji je koren čvor #10), može se ispisati i vrednost korenog čvora početnog stabla (10):
Pošto su levo podstablo i koreni čvor osnovnog stabla ispisani, posvetićemo se desnom podstablu:
Čvor #15 ima levo podstablo, pa prvo prelazimo na levu stranu:
U praktičnom smislu, vidimo da se čvor #12 može ispisati odmah.
Međutim, u implementaciji, rekurzivni poziv bi prvo ispitao da li čvor #12 ima levo podstablo (i ukoliko podstablo postoji, pristupilo bi se rekurzivnom obilasku levog podstabla) - i tek potom bi čvor #12 bio ispisan.
Posle navedenih koraka, drugi rekurzivni poziv, pokušao bi da ispiše desno podstablo (čvora #12), ali, budući da nijedno od dva podstabla ne postoji, posle neuspešne probe ispisa desnog podstabla, vraćamo se na čvor #12.
Pošto je čvor #12 rešen, možemo se vratiti i na čvor #15, a sada se može i ispisati vrednost 15 (s obzirom na to da je celo levo podstablo čvora #15 rešeno).
Pošto je čvor #15 ispisan, možemo se usmeriti na njegovo desno podstablo ....
Praktično - odmah će biti ispisan čvor #17, ali, u implementaciji bi se to desilo tek pošto se završi rekurzivni obilazak levog podstabla * (postupak ne prikazujemo na slikama).
Na red dolazi čvor #22 ....
.... i na kraju čvor #24:
Kao i do sada, zelena boja sugeriše da je čvor #24 drugi na redu za ispis, ali, s obzirom na to da čvor nema levo podstablo, praktično se ispisuje odmah.
S obzirom na to da nema ni desnog podstabla (i drugih obilazaka) ....
.... celokupan obilazak stabla je gotov i sve vrednosti su ispisane:
Inorder obilazak stabla - Implementacija
Pogledajmo i implementaciju inorder obilaska:
public void DFSIspisInorder(Cvor C) {
if (C == null) return;
DFSIspisInorder(C.Levi);
System.out.printf("%d ", C.Vrednost);
DFSIspisInorder(C.Desni);
}
Ponovo dosledno sprovodimo teoretske principe, uz korišćenje rekurzije, a može se reći da je rekurzija - u slučaju implementacije DFS obilazaka: i mehanizam za preusmeravanje, i svojevrstan sigurnosni mehanizam (koji omogućava da se na sledeće korake ne prelazi dok prethodni koraci nisu rešeni).
Postorder obilazak stabla
Postorder obilazak stabla podrazumeva obilazak (i ispis čvorova, upis u listu, ili neku drugu operaciju), po sledećem redosledu:
- celokupno levo podstablo
- celokupno desno podstablo
- koreni čvor
Šematski prikaz obilaska ima sledeći oblik:
Koreni čvor (prema navedenim pravilima) ostavljamo za kraj i usmeravamo se na levo podstablo:
Čvor #5, kao koren podstabla, poslednji je po redu za ispis (u podstablu kome pripada) i pre njega se ispisuje čvor #7 ....
U svemu (kao i do sada), "ispod haube" postoje rekurzivni pozivi (jedan je "pokušao" da ispiše levo podstablo čvora #5, a u implementaciji bi postojala i dva rekurzivna poziva koja traže podstabla čvora #7). U praksi, vraćamo se na čvor #5 i može se ispisati vrednost čvora:
Međutim, kada se vratimo na koreni čvor, ne može se ispisati vrednost 10, budući da (još uvek) nije rešeno desno podstablo ....
.... i stoga se usmeravamo (upravo) na desno podstablo:
Koreni čvor (15) se u prvom koraku preskače, i prelazimo na levo podstablo.
U praktičnom smislu, čvor #12 se ispisuje odmah (a "ispod haube", preko rekurzivnih obilazaka je ustanovljeno da čvor #12 nema podstabla):
Vraćamo se "korak unazad" i proveravamo čvor #15 (budući da je postorder obilazak ponešto neintuitivniji od prva dva obilaska, prikazujemo i neke dodatne korake, "za svaki slučaj") ....
.... ali, možemo samo da primetimo da se vrednost 15 još uvek ne može ispisati, i da je potrebno da prvo obradimo desno podstablo čvora #15:
U "poslednjem podstablu", prvo rešavamo levo podstablo - što u praktičnom smislu znači da se vrednost 17 ispisuje odmah (budući da čvor #17 nema podstabla):
Kada se vratimo na čvor #22, ponovo navedeni čvor (shodno pravilima), moramo preskočiti ....
Prelazimo na desno podstablo ("baš poslednje podstablo"), što u praktičnom smislu (ponovo) znači da se samo ispisuje vrednost 24 (budući da ni čvor #24 nema podstabla):
Sada se možemo vratiti unazad i ispisati i preostale čvorove, prvo čvor #22:
.... potom i čvor #15:
.... i na kraju koreni čvor #10:
Postorder obilazak je završen ....
....i sve vrednosti su ispisane.
Postorder obilazak stabla - Implementacija
Implementacija postorder obilaska ima sledeći oblik:
public void DFSIspisPostorder(Cvor C) {
if (C == null) return;
DFSIspisPostorder(C.Levi);
DFSIspisPostorder(C.Desni);
System.out.printf("%d ", C.Vrednost);
}
I ovoga puta koristimo iste principe kao i u prethodna dva slučaja (a verujemo i da smo uspeli da bar neke "protivnike rekurzije" ubedimo da promene stav o ovoj krajnje korisnoj pojavi u programiranju).
Uprošćena šema DFS obilazaka
Za kraj, razmotrićemo uprošćenu šemu DFS obilazaka.
U sva tri slučaja, "držimo se leve strane" koliko god možemo i vraćamo korak unazad - pa "skrećemo desno" - "onda kada moramo".
Ispis je različit u sve tri situacije i za svaki čvor važi da će vrednost čvora biti ispisana (ili da će čvor biti ubačen u listu/niz i sl):
- u preorder obilasku - prvi put kada se pristupi čvoru
- u inorder obilasku - drugi put kada se pristupi čvoru
- u postorder obilasku - poslednji put kada se pristupi čvoru
Mogli biste nam zameriti što vam to nismo saopštili na samom početku i poštedeli vas čitanja više desetina redova (umesto samo prethodnih nekoliko), ali takav pristup ne smatramo ni izdaleka pravilnim - i takav pristup ne bi vam pomogao nimalo!
Verujemo da bi dobar deo čitalaca bio u stanju da okvirno "shvati poentu" uprošćene šeme (pri čemu bi se stvorio lažni utisak pravog razumevanja, koji smatramo veoma opasnim i štetnim za pravilan razvoj programerske veštine), ali, iz iskustva znamo da bi gotovo svi "promašili" pravi smisao.
Mi, naravno, ne želimo da naši čitaoci 'promaše' pravi smisao. :)
Međutim, do pravog razumevanja (i u programiranju, i inače u životu), dolazi se samo temeljitim radom, a ne prečicama!
Uprošćene šeme, kao što je šema koju ste maločas videli, dobro dođu (da ne kažemo, veoma dobro), ali - tek pošto neko temeljito 'pretrese' osnovne principe i usvoji ih (to jest, tek pošto neko, na pravi način, dođe do pravog razumevanja).
Sledeći koraci ....
Ako ste došli do ovih poslednjih redova, pretpostavićemo da tematiku obilazaka stabala smatrate (dovoljno) zanimljivom, ali, kao što smo nagovestili, "upotrebna vrednost" obilazaka u AVL stablu je gotovo iscrpljena onim što smo prikazali u članku.
Međutim, sada ste upoznati sa opštim principima (BFS i DFS obilazaka) i navedeni principi će dobro doći pri proučavanju algoritama za tumačenje algebarskih izraza i kreiranje stabala izraza (o kojima ćemo uskoro pisati), a dobro će doći i pri proučavanju drugih algoritama (o kojima ćemo pisati u nešto daljoj budućnosti), u kojima se pojavljuju obilasci stabala.
Što se tiče AVL stabla, "podižemo lestvicu", prelazimo na "ozbiljne teme" (svakako bar ponešto kompleksnije od dosadašnjih), i u narednom članku o implementaciji AVL algoritma - bavićemo se dodavanjem čvorova.