AVL Stablo - Implementacija - 4. deo - Dodavanje čvorova
Uvod
U četvrtom (pretposlednjem) nastavku serijala o implementaciji algoritma AVL, bavićemo se procedurom za dodavanje novih čvorova u AVL stablo.
U pitanju je prilično kompleksan postupak, i stoga (da bismo čitaocima olakšali proces upoznavanja sa tematikom), podelićemo algoritam 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, uglavnom prilično jednostavni za razumevanje i implementaciju (sami po sebi), što naravno i jeste razlog zašto je preporučljivo da se veći problemi dele na manje i jednostavnije potprobleme.
Kažemo "uglavnom", budući da je deo procedure koji je namenjen rebalansiranju čvorova, ipak prilično kompleksan (za razliku od ostalih delova), ume da 'zada muke' svima koji se sa ovakvim postupkom prvi put susreću, i stoga ćemo (kada dođe vreme), upravo postupku za rebalansiranje 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 ....
.... pri čemu ćemo detaljno razmotriti promene u strukturi stabla, u situaciji 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, a pošto čvor #4 (očigledno) ne može zauzeti poziciju postojećeg čvora - i 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 od vrednosti koja se dodaje u stablo (4), potrebno je '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 se ne popunjavaju '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 (drugim rečima: 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 ("baš") mogli 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 čvora #15 (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 čvora #22:
.... ali, budući da je i u korenu levog podstabla pronađen postojeći čvor, sledi 'skretanje ulevo'.
Na kraju (na mestu korena levog podstabla čvora #17), pronađena je odgovarajuća pozicija 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, čvor #15 ima faktor balansiranosti -2 (što prelazi 1 po apsolutnoj vrednosti), i upravo je ovo čvor na kome praktično 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 se obavlja 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 se ažurira č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 (nije teško 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 uobičajenih rotacija, koristićemo drugačiji, pomalo eklektičan postupak.
Kao što smo videli u uvodnom članku o AVL stablima, potrebno je samo da DD struktura ....
.... ili DL struktura ....
.... bude svedena 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);
// Na kraju, preostaje provera ....
/* ---------------------------------------- */
/* 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 disbalansiranih č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 (tj. 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 (tj. 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, da naglasimo još jednom - krajnje vredno truda). :)