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 još je jasnije da optimalna struktura ne nastaje "sama od sebe".
U sledećim redovima prikazaćemo postupak za kreiranje visinski balansiranog stabla (jedne od mogućih * struktura za efikasno pretraživanje), a u bliskoj budućnosti usmerićemo se i na detaljnu implementaciju AVL stabla.
Opšta struktura i problematika pretrage
Podsetićemo se (za početak), na osnovne smernice iz uvodnog članka, koje se tiču strukture binarnih stabala pretrage (a u nastavku ćemo se upoznati 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).
Najvažnija osobina binarnog stabla, koje se zapravo može koristiti za efikasno pronalaženje elemenata, je - optimalan raspored elemenata (ili, prosto rečeno - "balans"), koji se prvo mora 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 redom 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
Pravila za dodavanje novog čvora podrazumevaju (u praktičnom smislu) - 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 - 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 sada šta bi se desilo da smo iste elemente pokušali da dodamo redom ....
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.
Pogledajmo postupak.
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 naravno važe i za čvor #22 (koji se 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).
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
.... a u uvodnom članku o binarnim stablima, detaljno smo se upoznali sa time kako bi takva razlika u strukturi uticala na vreme pretrage!
Primenom procedure za proveru balansa (koja se obavlja pri dodavanju svakog novog čvora), i korekcijom balansa - tamo gde je potrebno - postiže se 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 svaki čvor odlikuje visinska ravnoteža između levog i desnog podstabla, odnosno - za svaki čvor važi da je razlika između visine levog podstabla i visine desnog podstabla, 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, a na drugom nivou, č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 postaće 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, a u primeru koji razmatramo, to je čvor #22):
Ukoliko "zarotiramo" (tj. promenimo raspored), tri čvora, gde je prvi čvor, najniži čvor sa poremećenom ravnotežom, a preostala dva čvora su direktni potomci 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?
Praćenjem prethodnih primera, može se naslutiti opšti princip generisanja visinski balansiranog stabla pretrage:
- č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 dodavanje 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 (srećom), kao što smo već nagovestili, bilo koji novonastali disbalans, zapravo se može rešiti (tj. mora 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 (umesto brojčanih vrednosti), slova alfabeta A, B i C.
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 iz 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.
Dodavanjem 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 ravnotežu (kao u prethodna dva slučaja), već - zapravo dovodi do uspostavljanja potpune ravnoteže.
Osnovna ideja za balansiranje je sledeća: bilo koja struktura od svega tri čvora, u kojoj je čvor na najvišoj poziciji disbalansiran, može se dovesti u ravnotežu tako što se čvor srednje vrednosti (B), postavlja na najvišu poziciju, čvor najmanje vrednosti (A), pripaja se čvoru B sa leve strane, a čvor najveće vrednosti (C), pripaja se čvoru B sa desne strane.
Još je bolje ukoliko uvidimo (kao što smo ranije 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.
Međutim, sve 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 koja direktno učestvuju u proceduri balansiranja, a u balansiranju će učestvovati i sledeća dva čvora 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.
S obzirom na navedeno, 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 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.
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 za bilo koju poziciju u stablu (shodno prethodno navedenom kontekstu), 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). :)