Visinski balansirano (AVL) stablo
Uvod
U članku o binarnoj pretrazi pokazali smo da binarna stabla pretrage omogućavaju efikasno pronalaženje elemenata, međutim, jasno je da stablo koje se koristi za pretragu mora imati optimalnu strukturu (i pri tom nije teško naslutiti da optimalna struktura ne nastaje "sama od sebe").
U sledećim redovima, detaljnije ćemo se upoznati sa teorijom binarnih stabala pretrage, nakon čega ćemo prikazati postupak za kreiranje visinski balansiranog stabla (koje predstavlja jednu od mogućih struktura za efikasno pretraživanje). *
Opšta struktura i problematika pretrage
Podsetićemo se (za početak) na osnovne smernice koje se tiču strukture binarnih stabala pretrage (nakon čega ćemo se upoznati i sa pravilima za dodavanje čvorova):
- binarno stablo je struktura podataka sastavljena iz međusobno povezanih čvorova, u kojoj svaki čvor može imati najviše dva "potomka" ("potomak" ili "dete" = povezani čvor na sledećem nivou hijerarhije)
- čvorovi u binarnom stablu mogu pokazivati samo na svoje direktne potomke (odnosno, ne mogu pokazivati na čvorove sa prethodnih nivoa hijerarhije ili druge nasumične čvorove)
- u binarnom stablu pretrage, * za bilo koji čvor važi da su sve vrednosti u levom podstablu manje od vrednosti datog čvora, dok za vrednosti sa desne strane važi da su veće
Međutim, nije dovoljno samo da binarno stablo pretrage bude "tehnički ispravno" (shodno prethodno navedenim pravilima).
U binarnom stablu koje se zapravo može koristiti za efikasno pronalaženje elemenata - mora postojati optimalan raspored elemenata (ili, prosto rečeno "balans"), koji je prvo potrebno uspostaviti, a potom i održavati.
Na sledećoj slici vidimo (moguću) strukturu binarnog stabla, koje je visinski balansirano (i kao takvo, moglo bi se koristiti za pretragu).
Sa druge strane, ako se pri kreiranju stabla čvorovi (na primer) samo dodaju po rastućem redosledu i pri tom se ne vodi računa o balansu stabla - vrlo lako može nastati i struktura koja nije balansirana ....
.... i takva struktura u praktičnom smislu predstavlja - ništa drugo nego običnu ulančanu listu!
Ako se pitate kako - u programu koji je namenjen kreiranju binarnog stabla - može nastati struktura koja se jedva imalo razlikuje od obične liste, recimo da "nije teško" (naprotiv, vrlo je lako).
Pravila za dodavanje čvorova
U praktičnom smislu, pravila za dodavanje novog čvora podrazumevaju - pretragu - do "praznog mesta" na koje novi čvor može biti dodat, i - ukoliko se u stablo dodaje čvor kome je pripisana pozitivna celobrojna vrednost koja ne postoji u stablu * - zagarantovano je da će za takav čvor biti pronađeno odgovarajuće mesto.
Da bismo se upoznali sa opštim postupkom za kreiranje binarnog stabla, razmotrićemo dva primera.
U prvom primeru, nasumično ćemo dodavati elemente (ali izabrali smo redosled koji dovodi do povoljnog ishoda), dok ćemo u drugom primeru elemente dodavati redom ('po veličini') - i videćemo zašto takav redosled ne pogoduje kreiranju balansiranog stabla pretrage.
Primera nasumičnog kreiranja balansiranog stabla
Za sam početak, nećemo se "praviti" (još uvek), da obavljamo pretragu, i samo ćemo postaviti prvi čvor (10) - u koren stabla:
Međutim, već u drugom koraku potrebno je (doslovno) tražiti odgovarajuće mesto za novi čvor (5), a budući da je nova vrednost manja od vrednosti korenog čvora, i budući da je koren levog podstabla korenog čvora slobodan, novi čvor će biti direktan (levi) potomak korenog čvora:
Po istom principu (samo što se ovoga puta "skreće" na suprotnu stranu), nova vrednost (15), koja je veća od vrednosti korenog čvora, može se dodati kao koren desnog podstabla korenog čvora:
Za dodavanje vrednosti 12, prelazi se u desno podstablo korenog čvora (pošto je nova vrednost veća od 10), a zatim, kada se čvor #15 uporedi sa novom vrednošću (i pošto novi čvor ima manju vrednost), jasno je da novi čvor treba da bude postavljen kao direktan levi potomak čvora #15:
Poslednji čvor nosi vrednost koja je veća, i od 10, i od 15, i stoga se postavlja kao koren desnog podstabla čvora #15:
Pogledajmo šta bi se desilo da smo iste elemente pokušali da dodamo po rastućem redosledu ....
Primer nasumičnog kreiranja disbalansiranog stabla
Naveli smo da se vrednosti: 5, 10, 12, 15 i 22, mogu dodavati u binarno stablo - prema pravilima za dodavanje čvorova u binarno stablo, ali, tako da rezultat bude (u praktičnom smislu) - kreiranje strukture koja je gotovo isto što i jednostruko ulančana lista (sledi prikaz postupka).
Na samom početku (baš kao i u prvom primeru), stablo je prazno i čvor #5 se dodaje kao koreni čvor:
Čvor #10 (sa vrednošću koja je veća od 5), postavlja se desno od korenog čvora (kao koren desnog podstabla):
Čvor #12 (koji nosi vrednost veću, i od 5, i od 10), dodaje se kao koren desnog podstabla čvora #10:
Čvor #15 se dodaje (shodno pravilima), kao koren desnog podstabla čvora #12:
Pravila važe (naravno) i za čvor #22, koji sadrži vrednost koja je veća od 15, i stoga se novi čvor postavlja kao koren desnog podstabla čvora #15:
Dakle, oba stabla su formirana prema propisima za kreiranje binarnih stabala (sasvim nedvosmisleno), ali, visina prvog stabla može se izraziti kao log2 n - gde je n broj elemenata, dok za drugo stablo važi da se visina poklapa sa brojem elemenata (i zato je ranije navedeno da ovakvo "stablo", u praktičnom smislu, predstavlja samo običnu listu).
Kratka analiza
S obzirom na mali broj elemenata, druga prikazana struktura ne predstavlja (pre)veliki problem, jer je visina porasla za svega dva "sprata", ali, u stablu sa (primera radi) milion elemenata, razlika bi bila drastična:
- balansirano binarno stablo sa milion čvorova, ima visinu 20
- nebalansirano binarno stablo (sa istim brojem elemenata), može imati visinu 1000000
Razlika je "jasna" i "očigledna" već na prvi pogled, međutim, podsetićemo se na ovom mestu šta je (prava) "poenta" dobro organizovanih struktura podataka i efikasnih algoritama ....
Brojevi koji su navedeni u gornjoj listi imaju različite vrednosti i jedan od njih je (veoma nedvosmisleno) veći, ali, takva razlika može delovati "apstraktno" i (najprostije rečeno) nevažno - sve dok se ne dovede u realnu vezu sa izvršavanjem računarskih programa.
Što se tiče konkretnog primera, još u uvodnom članku o binarnim stablima zaključili smo da pretraga velikih ulančanih lista može potrajati više minuta, dok pretraga odgovarajućeg binarnog stabla (sa istim brojem elemenata), traje najviše nekoliko desetina mikrosekundi (to jest, primetno manje od jednog hiljaditog dela sekunde). *
Budući da povoljno vreme izvršavanja zavisi od pravilne strukture stabla (koja se ne uspostavlja "sama od sebe" (videli smo i zašto je tako)), jasno je da se nakon dodavanja elemenata u stablo, moraju preduzimati dodatni koraci.
Algoritam AVL (koji je objavljen 1962. godine ** i imenovan prema prezimenima autora), *** podrazumeva: proveru balansa pri dodavanju svakog novog čvora, i korekciju balansa - tamo gde je potrebno, čime se postiže da binarno stablo pretrage održi visinski balans bez obzira na broj čvorova.
Faktor balansiranosti
Kada navedemo da se stablo smatra visinski balansiranim, radi se o tome da na svakom čvoru postoji visinska ravnoteža između levog i desnog podstabla (koja su povezana sa datim čvorom), odnosno, za svaki čvor važi da je razlika između visine levog podstabla i visine desnog podstabla (datog čvora), manja ili jednaka 1 po apsolutnoj vrednosti (to jest, dozvoljeno je da razlika bude -1, 0 ili 1).
U implementaciji čvorova visinski balansiranog binarnog stabla, navedena razlika se tipično naziva faktor balansiranosti (ali, ponekad i "balans faktor", ili "faktor ravnoteže"):
BalansFaktor = VisinaLevogPodstabla - VisinaDesnogPodstabla;
Na sledećem primeru vidimo faktore balansiranosti čvorova iz stabla:
Svi "listovi" u AVL stablima * imaju faktor balansiranosti 0 (0 - 0 = 0), a u primeru koji razmatramo, listovi su čvorovi: #5, #12 i #22.
Čvor #15 takođe ima faktor balansiranosti 0: sa leve strane nalazi se jedan čvor, a isto važi i za desnu stranu, međutim (da budemo precizniji), ono što je važnije u opštem smislu, jeste to da oba podstabla čvora #15 imaju visinu 1 (u svakom slučaju, faktor balansiranosti je 0: 1 - 1 = 0).
Na kraju, faktor balansiranosti za čvor #10 je -1: sa leve strane je podstablo visine 1, dok je visina desnog podstabla 2 (na prvom nivou je čvor #15; na drugom nivou su čvorovi #12 i #22), i stoga je faktor balansiranosti za čvor #10: 1 - 2 = -1.
Pogledajmo kako dodavanje novog čvora (sa vrednošću 7), utiče na balans stabla:
Po pravilima za dodavanje novih čvorova, čvor #7 se dodaje na prikazanu poziciju ("a ne neku drugu"), zato što je vrednost 7:
- manja od 10 (zbog čega je pretraga u prvom koraku prešla na levo podstablo korenog čvora) i istovremeno ....
- veća od 5 (zbog čega je pretraga posle čvora #5 "skrenula desno")
Budući da koren desnog podstabla čvora #5 nije postojao (pre dodavanja čvora #7), to jest, budući da je desno podstablo bilo "prazno", čvor #7 postaje koren desnog podstabla čvora #5:
Struktura stabla naizgled deluje korektno (i dalje), ali, potrebno je proveriti faktor balansiranosti svih čvorova:
U odnosu na koreni čvor (#10), situacija je sledeća: desno podstablo se nije promenilo, dok je visina levog podstabla porasla za jedan; čvor #5 nema više faktor balansiranosti 0, već -1, a promenio se i faktor balansiranosti korenog čvora (nova vrednost je 0).
U svakom slučaju, balans stabla nije narušen.
U prethodnom koraku smo dodali vrednost koja je (donekle) nasumična, a u nastavku ćemo dovesti stablo u stanje disbalansa, dodavanjem vrednosti (u svakom koraku), koja je veća od najveće vrednosti koja je trenutno prisutna u stablu.
Posmatrajmo detaljno, kada (tačno) i kako (zapravo), nastaje neravnoteža.
Posle dodavanja čvora #24 ....
.... vidimo ("na slici") da stablo blago preteže na desnu stranu, ali, i dalje deluje da balans nije narušen.
Ako proverimo faktore balansiranosti ....
.... možemo potvrditi da je odokativna procena bila korektna: posmatrajući od korenog čvora prema desnoj strani stabla, svi čvorovi osim novog "lista" (#24), sada imaju faktor balansiranosti -1, što odgovara "pretezanju" na desnu stranu, ali, stablo je i dalje u stanju ravnoteže.
Dodajemo još jedan čvor:
.... i sada se već intuitivno može proceniti da je ravnoteža narušena ("tako deluje").
Ako preračunamo faktore balansiranosti ....
.... vidimo da ne samo da deluje da je stablo u stanju neravnoteže - već stablo i jeste u stanju neravnoteže.
Čvor #25 ima faktor balansiranosti 0 (u pitanju je list), čvor #24 ima faktor balansiranosti -1 (0 - 1 = -1), ali zato čvor #22 ima faktor balansiranosti -2 (0 - 2 = -2)!
Naravno, dodavanjem novog čvora (#25), poremećena je ravnoteža: ne samo čvora #22, već i ostalih čvorova predaka - sve do korena!
Da bi stablo bilo vraćeno u stanje ravnoteže, potrebno je povratiti balans 'najnižeg' čvora (to jest najbližeg pretka novododatog čvora) - čiji je balans poremećen (dakle, traži se 'prvi' čvor koji ima faktor balansiranosti 2 ili -2 (u konkretnom primeru koji razmatramo, u pitanju je čvor #22)):
Ukoliko "zarotiramo" (tj. promenimo raspored) tri čvora, pri čemu se u obzir uzimaju: "najniži" čvor sa poremećenom ravnotežom, i dva direktna potomka na putanji prema čvoru čije je dodavanje poremetilo ravnotežu stabla (na prethdonoj slici: tri obojena čvora), dovešćemo nebalansirani čvor (#22), zajedno sa njegovim podstablima - u stanje ravnoteže:
Međutim (što je važnije), deluje da smo prethodnim postupkom postigli da se celo stablo vrati u stanje ravnoteže i - ako proverimo faktor balansiranosti (svih) čvorova ....
.... vidimo da se celo stablo zaista i jeste vratilo u ravnotežu - balansiranjem (samo) "prvog" čvora na kome je direktno nastao disbalans.
Kako se kreira visinski balansirano ("samobalansirajuće") binarno stablo?
Opšti princip generisanja visinski balansiranog stabla pretrage, može se naslutiti praćenjem prethodnih primera:
- čvorovi se dodaju jedan po jedan *
- odmah posle dodavanja novog čvora, proverava se balans stabla (odnosno, ažurira se i proverava faktor balansiranosti svih relevantnih čvorova)
- čim se pronađe (prvi) čvor koji je u neravnoteži, navedeni čvor se balansira - i time se (automatski) dovodi u ravnotežu i ostatak stabla
Videli smo da postoje situacije u kojima, posle dodavanja novog čvora, stablo prestaje da deluje "lepo" i balansirano (kao do tada), ali - i dalje ostaje balansirano (shodno pravilima o strukturi AVL stabla), i na kraju smo videli kako i kada zapravo nastaje disbalans.
Videli smo takođe, kako se rešavanjem jednog čvora, može uspostaviti ravnoteža celog stabla.
Međutim, može delovati da je rešenje koje smo primenili donekle proizvoljno (iako deluje sasvim logično), ali, na sreću, kao što smo već nagovestili, bilo koji novonastali disbalans, zapravo se može rešiti (tj. mora se rešiti - odmah - čim nastane), "rotiranjem" svega tri čvora.
Shodno navedenom, za početak ćemo posvetiti pažnju binarnim stablima koja imaju najviše tri čvora, međutim (što je najvažnije), u nastavku ćemo videti da principi koji se tiču nastajanja i rešavanja disbalansa u stablu sa tri čvora - važe i u slučaju bilo koje "razgranatije" strukture.
U primeru ćemo koristiti slova alfabeta A, B i C (umesto brojčanih vrednosti).
Redom ćemo dodavati elemente, pri čemu ćemo proučiti sledeće kombinacije: ABC, ACB, BAC (preostale tri kombinacije: ili su skoro identične - u slučaju kombinacija BAC i BCA, ili predstavljaju "sliku u ogledalu" - u slučaju preostale dve).
Struktura DD (LL)
Samostalni čvor (tj. čvor koji nije povezan sa drugim čvorovima), uvek ima faktor balansiranosti 0, pa preostaje samo da primetimo (na vrlo "tautologičan način"), da je stoga i celo stablo koje se sastoji od samo jednog čvora, takođe (savršeno) balansirano.
Kada se doda novi čvor (koji po pravilima za dodavanje čvorova "odlazi desno"), ravnoteža više nije 'idealna', ali (takođe shodno pravilima), stablo je i dalje u stanju balansa.
Treći čvor (C), koji se dodaje desno od čvora B, doveo je koreni čvor (A) - a time i celo stablo - u stanje disbalansa.
U implementaciji, struktura koju smo predstavili kao "ABC", označava se kao "DD" (desno-desno), što odgovara redosledu dodavanja čvorova koji učestvuju u proceduri balansiranja.
Pogledajmo takođe i kombinaciju ACB.
Struktura DL (LD)
Prvi korak (u smislu dodavanja i uočenog balansa), isti je kao malopre:
Drugi čvor se ponovo dodaje desno (simbolično, "C je veće od A"), stablo blago "preteže" udesno, ali, i dalje je sve u ravnoteži.
Dodavanje trećeg čvora ....
.... ponovo je poremetilo ravnotežu korenog čvora, odnosno, celog stabla!
U implementaciji, struktura koju smo predstavili kao "ACB", označava se kao "DL" (desno-levo), što i ovoga puta odgovara redosledu dodavanja čvorova koji učestvuju u proceduri balansiranja.
Pogledajmo još i kako bi izgledalo kreiranje stabla dodavanjem čvorova po redosledu B-A-C.
Optimalna struktura (šablon za "rotacije")
U prvom koraku, kao i do sada - potpuna ravnoteža.
Nakon dodavanja drugog čvora, stablo blago "preteže" ulevo, ali, ravnoteža je i dalje očuvana.
Međutim, dodavanje trećeg čvora - ne samo da neće dodatno poremetiti stablo (kao u prethodna dva slučaja), već zapravo dovodi do uspostavljanja ravnoteže.
Osnovna ideja za balansiranje podrazumeva da se bilo koja struktura od svega tri čvora, * u kojoj je čvor na najvišoj poziciji disbalansiran, dovodi u ravnotežu na sledeći način:
- čvor srednje vrednosti (B), postavlja se na najvišu poziciju
- čvor najmanje vrednosti (A), pripaja se čvoru B sa leve strane
- čvor najveće vrednosti (C), pripaja se čvoru B sa desne strane
Još je bolje ukoliko uvidimo (kao što smo već nagovestili), da se prikazani postupak može primeniti na bilo kom mestu na kome je nastao disbalans, * u stablu proizvoljne strukture, to jest: pravila za rebalansiranje važe za bilo koju strukturu od tri čvora od kojih je najviši čvor u neravnoteži.
U svakom slučaju, "rotiranje čvorova" se mora obaviti vrlo pažljivo, i strogo se mora voditi računa o tome da podstabla čvorova koji učestvuju u balansiranju, budu (posle celog zahvata), pravilno raspoređena ....
Balansiranje tri čvora sa podstablima (opšta šema)
Početna situacija je sledeća ("DL" struktura):
Čvorovi A, B i C su "obični" čvorovi, dok su Al, Bl, Bd i Cd zapravo podstabla proizvoljne visine i složenosti (naravno, tako da važe prikazani faktori balansa).
Celo stablo je bilo u ravnoteži dok čvor A nije postao disbalansiran dodavanjem čvora u desno podstablo Čvora B (Bd), pri čemu zatičemo situaciju sa slike.
Osvrnimo se (još jednom), na prethodno navedena pravila:
- kada se doda novi čvor (u primeru koji razmatramo, proizvoljni čvor u podstablu Bd), potrebno je ažurirati faktor balansiranosti svih čvorova predaka
- novododati čvor može poremetiti faktor balansiranosti svojih predaka, ali, ne može poremetiti faktor balansiranosti ostalih čvorova
- stablo se dovodi u ravnotežu, balansiranjem tri čvora
U konkretnom primeru, čvor A (koji je izgubio balans), prvi je od tri čvora koji direktno učestvuju u proceduri balansiranja, a preostala dva čvora su čvorovi na putanji od čvora A do čvora čijim je dodavanjem stablo dovedeno u stanje neravnoteže (to su, redom, čvorovi C i B).
Za početak, čvorovi A, B i C postavljaju se u ravnotežni poredak: čvor srednje vrednosti je na vrhu, najmanja vrednost je levo, a najveća desno ....
.... i sada, kada su čvorovi A, B i C u ravnoteži, pitanje je šta treba uraditi sa njihovim podstablima?!
Budući da podstabla ne sadrže nasumične vrednosti, već, vrednosti koje su (i dalje) u precizno definisanim odnosima sa čvorovima A, B i C, neće biti problem da podstablima pronađemo nova mesta.
Levo podstablo čvora A (Al) ....
.... sadrži vrednosti koje su manje od vrednosti čvora A, a takođe se može primetiti i to da je levi pokazivač čvora A slobodan.
Shodno navedenom, podstablo Al može se (samo) vratiti na staro mesto.
Desno podstablo čvora C (Cd), sadrži vrednosti koje su veće od vrednosti čvora C, desni pokazivač čvora C je takođe slobodan, i stoga će podstablo Cd ....
.... takođe samo biti vraćeno na staro mesto.
Šta će biti sa podstablom Bl, budući da levi pokazivač čvora B sada pokazuje na čvor A (to jest, budući da više nije slobodan)?
Potrebno je potražiti "prirodno" mesto za podstablo Bl.
Levi pokazivač čvora B jeste zauzet, ali, setimo se da su sve vrednosti u podstablu Bl manje od B - ali istovremeno veće od A, pa, ako pažljivije pogledamo, videćemo da je desni pokazivač čvora A slobodan - i upravo to će biti novo mesto za podstablo Bl (čime Bl praktično postaje Ad).
Što se tiče podstabla Bd ....
.... primenjuje se isti princip: vrednosti čvorova iz stabla Bd su (istovremeno) veće od vrednosti čvora B i manje od vrednosti čvora C, i stoga se stablo Bd postavlja levo od čvora C (praktično: Bd postaje Cl).
Primer balansiranja čvorova (sa brojčanim vrednostima)
Na kraju, pogledajmo i primer sa konkretnim vrednostima (koji odgovara šemi koju smo prethodno opisali).
Posle dodavanja čvora #22, stablo je postalo disbalansirano na korenom čvoru (#17).
Čvorovi: #17 (čvor A u prethodnoj šemi), #25 (C) i #20 (B), učestvovaće neposredno u operaciji balansiranja, dok će njihova podstabla: Al (#4, #1), Bl (#19), Bd (#21, #22) i Cd (#32, #39), takođe pratiti prethodnu šemu.
Prvo je potrebno postaviti čvorove B (#20), A (#17) i C (#25) u ravnotežni raspored, i potom treba razmotriti strukturu podstabala.
Podstablo Al ....
..... ostaje levo od čvora A.
Podstablo Cd .....
.... ostaje desno od čvora C.
Levo podstablo čvora B ....
.... pripaja se čvoru A sa desne strane ....
.... a desno podstablo čvora B ....
..... pripaja se čvoru C sa leve strane ....
.... posle čega je (celo) stablo, ponovo u ravnoteži.
Kratak rezime ....
Još jednom: pod uslovom da se procedura balansiranja primeni na 'najniži' (tj. 'prvi') čvor na kome je nastao disbalans - celo stablo će biti vraćeno u stanje ravnoteže (a algoritam važi, shodno prethodno navedenom kontekstu, za bilo koju poziciju u stablu na kojoj nastane disbalans).
Za kraj, ostavljamo vam (za vežbu i proveru razumevanja navedenog gradiva), da uredite niz iz članka o binarnoj pretrazi, u binarno stablo pretrage - dodavanjem elemenata redom (a od dodatnih primera koje izaberete sami - samo može biti koristi). :)
U skorije vreme, takođe ćemo uobličiti i mini-serijal o implementaciji AVL stabla (u programskom jeziku Java) ....