Visinski balansirano (AVL) stablo
Uvod
U članku o binarnoj pretrazi pokazali smo da binarna stabla 'načelno omogućavaju' efikasno pronalaženje elemenata, međutim, videli smo takođe da prethodna konstatacija važi samo ukoliko stablo ima optimalnu strukturu - koja ne nastaje "sama od sebe".
U sledećim redovima, prvo ćemo se upoznati detaljnije sa teorijom binarnih stabala pretrage, nakon čega ćemo se upoznati sa postupkom za kreiranje visinski balansiranog stabla.
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 od međusobno povezanih čvorova, u kojoj svaki čvor može imati najviše jednog "pretka" i najviše dva "potomka" ("predak" ili "roditelj" = povezani čvor na prethodnom nivou hijerarhije; "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, a vrednosti u desnom podstablu 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 struktura koja nije balansirana ....
.... i vidimo da 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 nova vrednost uporedi sa već dodatim čvorom #15 (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 čvor #22 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 (čija je vrednost veća od 5), postavlja se desno od korenog čvora (kao koren desnog podstabla):
Čvor #12 (sa vrednošću koja je veća, 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 (sa vrednošću 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 se struktura ovakvog "stabla" praktično poklapa sa strukturom ulančane liste).
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 veći (sasvim nedvosmisleno), ali, takva razlika može ipak 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 najčešće/gotovo nikad ne uspostavlja "sama od sebe" (usput smo videli i zašto je tako)), jasno je da se nakon dodavanja određenog elementa u stablo - moraju preduzimati dodatni koraci.
Algoritam AVL (koji je objavljen 1962. godine ** i nazvan 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ćoj slici ....
.... prikazani su faktori balansiranosti čvorova u stablu sa početka članka, a u nastavku sledi kraća analiza prikazanih vrednosti.
Svi "listovi" * u AVL stablu (to jest, u konkretnom primeru, čvorovi #5, #12 i #22), imaju faktor balansiranosti 0 (u smislu, 0 - 0 = 0).
Č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 "skrenula desno" posle čvora #5)
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; faktor balansiranosti čvora #5 nije više 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, uzastopnim dodavanjem dve nove vrednosti (od kojih su obe veće od najveće dotadašnje vrednosti 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ć može intuitivno 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 čiji je balans poremećen, ili, drugim rečima, traži se 'prvi' tj. najbliži predak dodatog čvora 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 prethodnoj 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 dodatog čvora i svih njegovih predaka) **
- č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?!
Ipak, 'na sreću' (i 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, iako ćemo za početak posvetiti pažnju binarnim stablima koja imaju najviše tri čvora, nešto kasnije ćemo videti da principi koji se tiču nastajanja i rešavanja disbalansa u stablu sa svega tri čvora - važe i u slučaju "razgranatijih" struktura.
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 (i 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 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 (i 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.
Dodavanjem trećeg čvora ....
.... ponovo je poremećena ravnoteža 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 (pri kreiranju strukture B-A-C), 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, dodavanjem trećeg čvora, ne samo da se prethodna neravnoteža neće 'dodatno pokvariti' (kao u prethodna dva slučaja), već zapravo dolazi do uspostavljanja potpune 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, tj. strogo se mora voditi računa o tome da podstabla čvorova koji učestvuju u balansiranju budu pravilno raspoređena (posle celog zahvata) ....
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 nakon dodavanja novog čvora u desno podstablo Čvora B (Bd), pri čemu zatičemo situaciju sa slike.
Osvrnimo se (još jednom), na osnovna pravila koja smo navodili u dosadašnjem toku članka:
- kada se doda novi čvor (u primeru koji razmatramo, proizvoljni čvor u podstablu Bd), potrebno je ažurirati faktor balansiranosti svih čvorova predaka
- novi/'tek dodati' č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 ako uzmemo u obzir to da je levi pokazivač čvora A slobodan, podstablo Al se može (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)?
Rešenje je da se potraži "prirodno" mesto za podstablo Bl.
Levi pokazivač čvora B jeste zauzet, ali (da se podsetimo), sve vrednosti u podstablu Bl su manje od B i istovremeno veće od A, pri čemu možemo primetiti i to 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 šemu iz prethodnog poglavlja.
Prvo je potrebno postaviti čvorove B (#20), A (#17) i C (#25), u ravnotežni raspored ....
.... nakon čega se razmatra ostatak strukture.
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 stanju ravnoteže.
Kratak rezime ....
Da se podsetimo: 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 direktno nastaje disbalans).
Za kraj, ostavljamo vam (za vežbu i proveru razumevanja prikazanog 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) ....