Uvod
U četvrtom (pretposlednjem) nastavku serijala o implementaciji AVL algoritma, bavićemo se procedurom za dodavanje čvorova u AVL stablo i budući da je sam postupak prilično kompleksan, podelićemo ga na nekoliko celina:
- pronalaženje odgovarajuće pozicije za novi čvor
- kreiranje novog čvora i postavljanje na odgovarajuću poziciju
- provera balansa direktnih predaka novog čvora
- rebalansiranje stabla (u slučaju da je, u 3. koraku, pronađen čvor čiji je balans narušen)
Kada se posmatra 'razbijena' procedura, može se primetiti da su delovi iz kojih se procedura sastoji, sami po sebi, uglavnom prilično jednostavni za razumevanje i implementaciju (što naravno i jeste razlog zašto je preporučljivo da se veći problemi dele na manje i jednostavnije potprobleme).
Kažemo "uglavnom", jer (za razliku od ostalih), deo procedure namenjen rebalansiranju čvorova (ipak) je prilično kompleksan, i ume da zada 'muke' svima koji se sa ovakvim postupkom prvi put susreću, i stoga ćemo (kada dođe vreme), upravo postupku rebalansiranja posvetiti posebnu pažnju.
Dodavanje čvorova - teorija
Da bismo što bolje razumeli proceduru za dodavanje čvorova u AVL stablo, posmatraćemo stablo koje smo do sada koristili za primer ....
.... i detaljno ćemo razmotriti šta se sa stablom dešava kada se dodaju dva nova čvora:
- čvor sa vrednošću 4 - koji neće poremetiti ravnotežu
- čvor sa vrednošću 16 - koji će dovesti stablo u stanje disbalansa
Razume se, u svemu nas zanima algoritamski postupak opšteg tipa, koji važi u bilo kojoj situaciji.
Dodavanje čvora koji ne remeti balans stabla
Kao što znamo od ranije, pronalaženje pozicije za novi čvor, svodi se (u praktičnom smislu) - na pretragu.
Pretraga koja se obavlja zarad dodavanja, počinje od korenog čvora, i pošto čvor #4 (očigledno) ne može zauzeti poziciju postojećeg čvora - a pri tom je nova vrednost (4), manja od vrednosti čvora koji se trenutno ispituje (10) ....
.... odgovarajuća pozicija za novi čvor je očigledno ("negde") u levom podstablu.
Koren levog podstabla postoji, što znači da se novi čvor ne može smestiti na poziciju koju zauzima čvor #5 ....
.... a budući da je vrednost čvora u korenu levog podstabla (5), veća je od vrednosti koja se dodaje u stablo (4), mora se 'skrenuti' levo, nakon čega se ponovo ispituje da li je pronađena prikladna pozicija za novi čvor.
Ovoga puta pronađena je odgovarajuća pozicija i čvor se može smestiti:
Međutim, preostaje pitanje - šta se desilo sa balansom (ostalih) čvorova?!
Naizgled (na slici), deluje da je sve u redu, ali, da napomenemo još jednom, AVL stabla ne popunjavaju korisnici ručno/direktno (na "školskim" primerima malog obima, preko "slika"), već se postupak odvija po algoritmu, nad stablima sa stotinama, hiljadama, a neretko i milionima čvorova (dakle, novu situaciju u stablu moramo proveriti kako dolikuje - algoritamski).
Novi čvor ima faktor balansiranosti 0 ....
.... za ostatak stabla ne znamo, međutim, ne mora nas zanimati celokupan "ostatak stabla".
Kao što je poznato od ranije, dodati čvor može narušiti faktore balansiranosti isključivo svojih predaka - ali ne i ostalih čvorova (i stoga ćemo upravo pretke i ispitati).
Čvor #5 sada ima faktor balansiranosti 0 ....
.... a koreni čvor i dalje ima faktor balansiranosti -1:
Balans je očuvan, ali, budući da kroz prethodni primer nismo mogli ("baš") da naučimo šta treba raditi kada dodavanje novog čvora izbaci stablo iz stanja ravnoteže, razmotrićemo i komplikovaniji primer.
Dodavanje čvora koji remeti balans stabla
Kada pogledamo stablo ("na slici"), nije teško uvideti da će dodavanje čvora #16 narušiti ravnotežu (to jest, dovesti do toga da stablo "poprilično pretegne" na desnu stranu), međutim, potrebno je iznaći algoritam koji će doći do istog "zaključka".
Pretraga koja se obavlja zarad dodavanja, ponovo počinje od korena (što neće biti mesto za novi čvor):
.... niti će mesto za novi čvor biti koren desnog podstabla.
Pretraga prelazi u desno podstablo (budući da je vrednost koja se dodaje veća od 15), ali, koren desnog podstabla takođe je "zauzet":
Pošto je nova vrednost (16), manja od 22, pretraga prelazi u levo podstablo:
.... ali, budući da je i na ovom mestu pronađen postojeći čvor, sledi 'skretanje ulevo'.
Na kraju (na mestu korena levog podstabla čvora #17), pronađeno je mesto za novi čvor ....
.... međutim, "kada gledamo sliku" - deluje da je ravnoteža narušena.
Da bismo proverili da li je - i gde - (zapravo) nastao disbalans, potrebno je ažurirati sve označene čvorove.
Čvor #16 (novi "list"), automatski je ažuriran pri dodavanju i njegov faktor balansiranosti je 0.
Sledeći po redu čvor, čvor #17, ima faktor balansiranosti 1 ....
.... čvor #22 takođe ima faktor balansiranosti 1 ....
.... ali zato čvor #15 ima faktor balansiranosti -2 (što, po apsolutnoj vrednosti, prelazi 1), i upravo je ovo čvor na kome nastaje disbalans celog stabla:
Kao što znamo od ranije, ravnoteža se može povratiti balansiranjem tri čvora:
- samog čvora na kome je nastao disbalans (#15)
- sledeća dva čvora u smeru ka čvoru čijim je dodavanjem nastao disbalans (#22, #17)
Kao što vidimo, u pitanju je struktura DL (koju smo i u uvodnom članku o AVL stablima koristili kao primer za balansiranje tri čvora).
Sa slike ćemo (privremeno) ukloniti faktore balansiranosti i fokusirati se samo na podstrukturu koja učestvuje u balansiranju.
Uklonićemo privremeno (u prikazu), i veze između tri posmatrana čvora i njihovih podstabala
.... i potom obaviti balansiranje čvora po šemi ACB iz uvodnog članka (u pitanju je DL rotacija):
Posle DL rotacije, čvor #15 biće povezan sa svojim "nekadašnjim" * levim podstablom ....
Novi čvor će biti pripojen čvoru #15, kao desno podstablo ....
Na kraju, čvor #22 će (ponovo) biti povezan sa svojim "starim" * desnim podstablom (čvor #24)
Sada je potrebno ažurirati faktore balansiranosti svih relevantnih čvorova (naravno ne celog stabla), ali, pitanje je: šta se sve mora obuhvatiti?
Potrebno je (i dovoljno), osvežiti samo faktore balansiranosti čvorova na putu od novog čvora do korenog čvora (#16, #15, #17, #10), kao i faktor balansiranosti trećeg čvora koji je učestvovao u DL rotaciji (#22).
Prvo ćemo ažurirati čvor koji nije na putanji od novog čvora prema korenu, i (praktično), čvor #22 u novoj situaciji ima faktor balansiranosti -1:
Čvor #16, kao novi čvor, ima faktor balansiranosti 0 ....
.... čvor #15 (lako ćemo to izračunati), ima faktor balansiranosti 0 ....
.... čvor #17 takođe ima faktor balansiranosti 0 ....
.... i na kraju, koreni čvor ponovo ima faktor balansiranosti -1.
Kao što vidimo, ažuriranjem visina čvorova i proverom faktora balansiranosti, ustanovili smo ("algoritamskim putem"), da je stablo ponovo u ravnoteži (i sada možemo pristupiti implementaciji).
Dodavanje čvorova - Implementacija
Pre svega, razmotrićemo metode za obavljanje rotacija.
Izbeći ćemo pristup (uobičajen u literaturi, i nimalo pogrešan), koji podrazumeva da se dve kompleksnije rotacije ("LD" i "DL"), svode na uzastopno pokretanje osnovnih rotacija ("LD" kao "L" > "D", a "DL" kao "D" > "L").
Umesto toga, koristićemo drugačiji, (pomalo eklektičan) pristup.
Kao što smo videli u uvodnom članku o AVL stablima, potrebno je samo da DD strukturu ....
.... ili DL strukturu ....
.... svedemo na balansiranu strukturu, u kojoj srednja vrednost predstavlja koreni čvor, najmanja vrednost je levo, a najveća desno:
(Isti princip važi, naravno, i za "LL" i "LD" strukture.)
Rotacije
Metoda za DD rotaciju (koja je prilično jednostavna, i stoga je nismo u ovom članku prikazivali na slikama), podrazumeva preusmeravanje pokazivača u tri koraka:
public Cvor Rotacija_DD(Cvor C) {
Cvor B = C.Desni;
C.Desni = B.Levi;
B.Levi = C;
System.out.printf("DD(%d)\n", C.Vrednost);
Azuriranje(C);
Azuriranje(B);
return B;
}
Metoda za DL rotaciju (za koju smo u ovom članku prikazivali primere sa slikama) ....
public Cvor Rotacija_DL(Cvor C) {
Cvor P = new Cvor(0);
Cvor B = C.Desni.Levi;
P.Levi = B.Levi;
P.Desni = B.Desni;
B.Desni = C.Desni;
B.Levi = C;
B.Desni.Levi = P.Desni;
B.Levi.Desni = P.Levi;
System.out.printf("DL(%d)\n", C.Vrednost);
Azuriranje(C);
Azuriranje(B.Desni);
Azuriranje(B);
return B;
}
.... nezanemarljivo je kompleksnija, i zahteva upotrebu pomoćnog čvora (bez koga veoma lako mogu nastati poveći problemi sa dereferenciranjem).
Dodavanje
Metoda za dodavanje novog čvora, može se implementirati na sledeći način:
public Cvor Dodavanje(Cvor C, int Vrednost) {
// Ako je preko rekurzije pronađena pozicija
// na koju može biti dodat novi cvor, sledi ....
if (C == null) return new Cvor(Vrednost);
// Ako pozicija nije pronađena, nastavlja se
// pretraga ....
if (Vrednost < C.Vrednost) {
C.Levi = Dodavanje(C.Levi, Vrednost);
}
else {
if (Vrednost > C.Vrednost) {
C.Desni = Dodavanje(C.Desni, Vrednost);
}
else {
return C;
}
}
// Posle rekurzije, sledi ažuriranje visine i
// faktora balansiranosti ....
Azuriranje(C);
/* ---------------------------------------- */
/* ROTACIJE U SLUČAJU DISBALANSA */
/* ---------------------------------------- */
// LL:
if (C.BalansFaktor > 1 && C.Levi.BalansFaktor == 1) {
return Rotacija_LL(C);
}
// LD:
if (C.BalansFaktor > 1 && C.Levi.BalansFaktor == -1) {
return Rotacija_LD(C);
}
// DD:
if (C.BalansFaktor < -1 && C.Desni.BalansFaktor == -1) {
return Rotacija_DD(C);
}
// DL:
if (C.BalansFaktor < -1 && C.Desni.BalansFaktor == 1) {
return Rotacija_DL(C);
}
// Ako nije bilo potrebe za balansiranjem ....
return C; // .... samo će biti vraćen
// pokazivač na čvor C.
}
Sam kod sadrži korisna objašnjenja u komentarima (koja mogu biti dovoljna da razjasne sve delove koda u potpunosti), ali, osvrnućemo se dodatno na važnije detalje.
Struktura metode za dodavanje čvorova
U osnovnom smislu, metoda za dodavanje čvorova podeljena je na dva dela:
- deo u kome se traži pozicija za novi čvor
- deo u kome se proverava balans stabla posle dodavanja (i u kome se, po potrebi, rebalansira stablo)
U prvom delu (koji se tiče pronalaženja pozicije), važe sledeća pravila:
- ako čvor koji se trenutno ispituje, ne postoji, znači da je u prethodnom koraku pretraga "skrenula" prema praznom podstablu, i stoga će novi čvor biti dodat - upravo kao koren ("do tada praznog") podstabla
- ukoliko je vrednost koja se dodaje manja, dalja pretraga se usmerava na levo podstablo
- ukoliko je vrednost koja se dodaje veća, dalja pretraga se usmerava na desno podstablo
U drugom delu (provera balansa):
- prvo se proverava da li je dati čvor kandidat za pokretanje jedne od četiri metode za rebalansiranje (to jest, da li na datom čvoru postoji disbalans)
- ako je balans narušen, biće pokrenuta odgovarajuća metoda za rebalansiranje
Algoritam za izbor rotacija za rebalansiranje
Iako provera nebalansiranih čvorova (u smislu izbora jedne od četiri 'rotacije' za rebalansiranje), može - na prvi pogled - delovati kao vrlo komplikovana procedura koja zahteva obilazak više čvorova (od prvog disbalansiranog čvora - prema čvoru čijim je dodavanjem narušen balans), ceo postupak se zapravo može obaviti u dva koraka.
Pre svega, za posmatrani čvor važe sledeća pravila:
- ako čvor ima faktor balansiranosti -1, 0, ili 1, čvor je balansiran i nije kandidat za rotacije
- ako čvor ima faktor balansiranosti 2, * u pitanju je jedna od L rotacija
- ako čvor ima faktor balansiranosti -2, * u pitanju je jedna od D rotacija
.... posle čega samo još treba proveriti potomke (da bi bila određena konkretna rotacija koju je potrebno implementirati u datoj situaciji.
Za "L" rotacije (situacije u kojima "preteže" levo podstablo posmatranog čvora), posmatra se faktor balansiranosti direktnog levog potomka, pri čemu važi:
- ako je faktor balansiranosti levog potomka 1, u pitanju je LL rotacija
- ako je faktor balansiranosti levog potomka -1, u pitanju je LD rotacija
Za "D" rotacije (situacije u kojima "preteže" desno podstablo posmatranog čvora), posmatra se faktor balansiranosti direktnog desnog potomka, pri čemu važi:
- ako je faktor balansiranosti desnog potomka - 1, u pitanju je DD rotacija
- ako je faktor balansiranosti desnog potomka 1, u pitanju je DL rotacija
Na kraju, ako pažljivo sagledamo metodu za dodavanje čvorova, videćemo ponovo da je rekurzija (baš kao i u prethodnom članku sa DFS obilascima), mehanizam koji omogućava efikasno rešavanje problema, pri čemu je ceo postupak relativno jednostavan i prilično elegantan (što bi se reklo - 2:0 za rekurziju). :)
Sledeći koraci ....
Ovoga puta, pozabavili smo se nezanemarljivo kompleksnim mehanizmom za dodavanje čvorova u AVL stablo (koji srećom nema previše komplikovanu implementaciju).
U sledećem nastavku (poslednjem u serijalu), pozabavićemo se još kompleksnijim mehanizmom za uklanjanje čvorova (jeste pomalo komplikovano na početku, ali, još jednom - krajnje vredno truda).