AVL Stablo - Implementacija - 3. deo - Obilazak stabla
Uvod
Operacije obilaska, tipično nisu prvo što nekome može pasti na pamet kada se govori o stablima čija je primarna namena pretraga, ali, značaj operacija obilaska sasvim je nezanemarljiv i u AVL stablima (i drugim sličnim stablima).
Takođe, obilasci stabla su veoma zanimljivi sami po sebi (kao deo opšteg obrazovanja), i veoma su 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, i te kako su bitne u slučaju implementacije algoritma Shunting Yard, kao i u stablima izraza (srodni algoritmi kojima smo posvetili zasebne članke).
Obilazak stabla - osnovne ideje
Obilazak stabla je operacija koja podrazumeva pristup svakom pojedinačnom elementu (tipično, uz što manji broj poseta), što se dalje može iskorititi za ispis sadržaja stabla, kreiranje statičkog niza ili liste (koji su popunjeni 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 (kao što smo objasnili u pomenutom članku), prevashodno su algoritmi za pretragu (Breadth/Depth First Search; eng. - pretraga), ali, nazivi BFS i DFS se 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 (tj. ispisuje) koreni čvor, potom, dva direktna potomka korenog čvora, zatim, potomci direktnih potomaka korenog čvora, i nadalje (redom), ostatak stabla (nivo-po-nivo), sve do 'listova' (to jest, čvorova koji nemaju potomke).
Kao što je poznato od ranije, implementacija BFS obilaska podrazumeva korišćenje reda za čekanje (queue), a sam postupak koji ćemo prikazati, prilično je zanimljiv za razmatranje.
Algoritam započinje smeštanjem korenog čvora u red za čekanje, nakon čega sledi petlja koja ima sledeća svojstva:
- u svakoj iteraciji, na početku se uzima u obradu (i uklanja iz reda), element sa početka reda, posle čega se pronalaze direktni potomci izdvojenog elementa i smeštaju 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 koreni čvor (čvor #10):
.... 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 pronalaze se 'potomci' čvora #10 (čvorovi #5 i #15), i smeštaju se u red za čekanje:
Već na ovom mestu možemo uvideti zašto koreni čvor nije odmah "uzet u razmatranje" (bez ubacivanja u red), jer - ukoliko se koreni čvor smesti u red i ukoliko se potom pokrene petlja (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
Shodno ranije navedenim pravilima, jasno je da "čudni" korak ubacivanja korenog čvora u red - posle čega se ubačeni čvor odmah uklanja iz reda - zapravo ima smisla, jer takav postupak predstavlja (kao što smo već nagovestili), praktičan način organizacije petlje, koji podrazumeva da 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 potomci se smeštaju u red (zapravo, samo jedan potomak - čvor #7):
Sledeći čvor koji se preuzima iz reda je čvor #15 ....
.... vrednost 15 se ispisuje, a u red se smeštaju 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 čvor #12 takođe nema potomke, samo se ispisuje vrednost 12 i nastavlja se sa preuzimanjem čvorova iz reda ....
Vrednost sledećeg čvora (#22), dodaje se u ispis, a zatim se čvorovi #17 i #24 (potomci čvora #22), smeštaju u red:
Čvor #17 (koji je preuzet iz reda), nema potomke ....
.... isto važi za čvor #24 ....
.... i stoga nije bilo dodavanja novih čvorova u red (ali, naravno, vrednosti čvorova #17 i #24 su dodate u ispis).
Takođe, budući da je red za čekanje ispražnjen ....
.... algoritam izlazi iz petlje, što znači da je BFS obilazak stabla završen.
BFS obilazak - implementacija
BFS obilazak stabla može se implementirati na sledeći način:
public void BFS_Ispis() {
Queue<Cvor> red, sledeci, pom;
red = new LinkedList<Cvor>();
sledeci = new LinkedList<Cvor>();
boolean reseno = false;
red.add(this.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 detaljniju diskusiju o DFS algoritmima, iznećemo jedno opšte 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 i sl), DFS algoritmi nisu baš skroz jednostavni za razumevanje pri prvom susretu, * ali, zato je implementacija DFS algoritama - pod uslovom da onaj ko piše implementaciju dobro razume rekurziju - krajnje jednostavna.
DFS obilasci podrazumevaju pronalaženje elemenata (a u primerima koje razmatramo, i ispis) - "po dubini" stabla.
U praktičnom smislu, bilo koji DFS obilazak (koji navodimo), podrazumeva da se algoritam "drži leve strane stabla" dokle god je moguće, a udesno se prelazi onda kada nije moguće dalje prelaziti ulevo (naravno, uz povratak jedan korak unazad, na poslednju "raskrsnicu" - pre nego što se 'skrene desno').
Najlakše će biti da princip obilaska sagledamo preko sledeće 'šeme' (slika ipak vredi "toliko-i-toliko" reči):
Opisani princip pristupanja čvorovima stabla omogućava tri različite varijante DFS obilaska (tj. tri različita redosleda obrade):
- 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 #15, #12, #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 se vrednost korenog čvora podstabla (5):
.... a zatim, budući da čvor #5 nema levo ("zeleno") podstablo, ispisuje se desno podstablo (u praktičnom smislu - samo čvor #7):
Budući da su obrađeni koren stabla (čvor #10) i levo podstablo, na redu je desno podstablo.
U desnom podstablu, prvo se ispisuje koren podstabla (čvor #15):
.... zatim, levo podstablo (praktično, samo čvor #12) ....
.... i, na kraju, krajnje desno podstablo.
U "krajnjem desnom podstablu", prvo se ispisuje koreni čvor (č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 biti krajnje jednostavna (pod uslovom da dobro razumete rekurziju) ....
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 sa tim da vas uopšte nismo 'prevarili'. :)
Ako se dvoumite oko implementacije koju ste videli, pokušajte (u mislima ili na papiru), da 'provučete' stablo iz primera kroz prikazani program.
Kao što vidimo, sve funkcioniše (doslovno) onako kako smo naveli na početku, pri čemu za svaki čvor važi:
- prvo se ispisuje vrednost datog čvora
- nakon prethodnog koraka, ispisuje se 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 (budući da nije kompletno)?
Odgovor je (ponovo) - 'biće ispisano shodno ranije navedenim pravilima'. :)
S obzirom na to da ne postoji levo podstablo (prvobitnog levog podstabla), prvo se ispisuje koreni čvor podstabla (čvor #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, algoritam se vraća korak unazad, na čvor #5.
Pošto je čvor #5 (već) rešen, sledi još jedan korak unazad, skroz do korenog čvora početnog stabla (čvor #10).
Sada, kada je rešeno celo levo podstablo početnog stabla (u čijem korenu stoji č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, prelazi se na desno podstablo:
Čvor #15 ima levo podstablo, pa algoritam prvo prelazi 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 (ukoliko podstablo postoji, pristupilo bi se rekurzivnom obilasku levog podstabla) - i tek potom bi čvor #12 bio ispisan.
Posle navedenih koraka, drugi rekurzivni poziv bi pokušao da ispiše desno podstablo (čvora #12), ali, budući da nijedno od dva podstabla ne postoji, posle neuspešne probe ispisa desnog podstabla, sledi povratak na čvor #12.
Pošto je čvor #12 rešen, može se ispisati i vrednost čvora #15 (s obzirom na to da je celo levo podstablo ovog čvora rešeno).
Pošto je čvor #15 ispisan, obilazak se usmerava na desno podstablo čvora #15 ....
Praktično - odmah će biti ispisan čvor #17, ali, u implementaciji bi se to desilo tek pošto se završi rekurzivni obilazak 'nepostojećeg levog podstabla' * (postupak ne prikazujemo na slikama).
Na red za ispis dolazi čvor #22 ....
.... i, na kraju, čvor #24:
Kao i do sada, zelena boja sugeriše da je čvor #24 drugi po 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 u delo 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:
Shodno navedenim pravilima, obrada korenog čvora ostaje 'za sam kraj', a u obzir se prvo uzima levo podstablo:
Čvor #5, kao koren podstabla, poslednji je po redu za ispis u podstablu kome pripada; levog podstabla nema .... što praktično znači da se prvo 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, sledi povratak na čvor #5 i ispis vrednost čvora:
Međutim, po povratku na koreni čvor, vrednost 10 se ne može ispisati, budući da (još uvek) nije rešeno desno podstablo ....
.... i stoga se obilazak usmerava (upravo), na desno podstablo:
Koreni čvor (15) se u prvom koraku preskače, i prelazi se na koren levog podstabla (čvor #12).
U praktičnom smislu, čvor #12 se ispisuje odmah (a "ispod haube": preko rekurzivnih obilazaka je ustanovljeno da čvor #12 nema podstabla).
Sledi povratak "jedan korak unazad" i provera čvora #15 * ....
.... ali, može se samo konstatovati da vrednost 15 još uvek nije na redu za ispis, i stoga je potrebno prvo obraditi desno podstablo čvora #15:
U "poslednjem podstablu", prvo se rešava levo podstablo, što (u praktičnom smislu) znači da se vrednost 17 ispisuje odmah (budući da čvor #17 nema podstabla):
Čvor #22 (na koji se algoritam vraća u sledećem koraku) ....
.... ponovo se mora preskočiti (shodno pravilima) ....
Desno podstablo čvora #22 ("baš poslednje desno podstablo" početnog stabla) ....
.... praktično sadrži samo čvor #24, čija se vrednost može odmah ispisati (budući da čvor #24 takođe nema podstabla).
Sledi "povratak unazad", prema korenom čvoru: prvo se ispisuje čvor #22 ....
.... zatim, čvor #15 ....
.... i, na kraju, koreni čvor (č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 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, "algoritam se drži leve strane" koliko god je moguće, i vraća se korak unazad - pa zatim "skreće desno" - onda kada je skretanje udesno neizbežno.
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 na tome što vam nismo još na početku naveli 'prečice' (čime bismo vas 'poštedeli' čitanja više desetina redova (umesto nekoliko prethodnih)), ali, takav pristup ne smatramo ni izdaleka pravilnim - i takav pristup ne bi vam zapravo pomogao.
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 čitaoci ovog članka '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 (a nadamo se, i do razumevanja :)), pretpostavićemo da tematiku obilazaka stabala smatrate (dovoljno) zanimljivom, ali, kao što smo još ranije konstatovali, "upotrebna vrednost" obilazaka u AVL stablu gotovo je iscrpljena onim što smo prikazali u članku.
Međutim, sada ste upoznati sa opštim principima BFS i DFS obilazaka.
Navedeni principi dobro će doći pri proučavanju algoritama za tumačenje algebarskih izraza i kreiranje stabala izraza (o kojima ćemo uskoro pisati), a takođe će dobro doć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", tj. prelazimo na "ozbiljne teme" (svakako bar ponešto kompleksnije od dosadašnjih): u narednom članku o implementaciji algoritma AVL - bavićemo se dodavanjem čvorova.