AVL Stablo - Implementacija - 5. deo - Uklanjanje čvorova
Uvod
Za kraj serijala o implementaciji AVL stabla u programskom jeziku Java, ostavili smo operaciju uklanjanja - najmanje korišćenu od svih operacija i najkomplikovaniju za implementaciju.
Namerno nismo hteli da izbegnemo 'antimarketinški' uvod koji ste prethodno pročitali; naravno - ne iz želje da nekoga demotivišemo, već zato da bismo vašu budnost, pažnju i koncentraciju, doveli na odgovarajući nivo, pre nego što se upustimo u proučavanje procedure koja ima potencijal da "namuči" gotovo sve programere koji se prvi put sa njom susreću (što je razlog da se izazov shvati ozbiljno).
Međutim, ukoliko ste uspešno ispratili i dobro razumeli dosadašnje članke (pogotovo ako ste dobro razumeli proceduru za dodavanje čvorova), i ukoliko uložite odgovarajuću količinu truda i vremena - ni u ovom slučaju rezultati neće izostati ....
Uklanjanje čvora - teorija
Uklanjanje čvora je operacija koja podrazumeva da određeni čvor nestaje iz stabla (na neposredan način, ili, tako što drugi čvor zauzme mesto uklonjenog čvora), posle čega je potrebno: ustanoviti da li je AVL stablo i dalje u stanju balansa i - ukoliko je balans narušen - sprovesti proceduru za rebalansiranje.
Kao što smo već nagovestili, u pitanju je prilično kompleksan mehanizam - sa kojim ćemo se upoznavati postepeno - a ovoga puta koristićemo veće i 'razgranatije' stablo (u odnosu na stabla koja smo do sada koristili):
Pre nego što počnemo da navodimo pravila za uklanjanje čvorova, toplo preporučujemo da prekinite za trenutak sa čitanjem i sami pokušate da razradite (u glavi ili na papiru), postupke za uklanjanje različitih čvorova iz stabla.
Obratite pažnju na faktore balansiranosti čvorova (pre i posle uklanjanja), i pronađite prvo čvorove koji se mogu ukloniti na neposredan način, tako da balans ne bude narušen.
Pronađite potom i druge čvorove, koji se (sami po sebi) mogu ukloniti neposredno, ali, posle čijeg uklanjanja dolazi do narušavanja balansa.
Na kraju, pronađite i čvorove koji se ne mogu ukloniti neposredno - bez potrebe za preduzimanjem daljih koraka (već su u pitanju čvorovi posle čijeg uklanjanja je potrebno "ispremeštati" veći broj okolnih čvorova) - i probajte da iznađete rešenje i za takve situacije.
Za neke čvorove imaćete odgovor odmah (uklanjanje određenih čvorova utiče na ostatak stabla: veoma malo, ili čak nimalo), dok će vam neki drugi čvorovi zadavati više "muke", * budući da uklanjanje određenih čvorova - i te kako menja strukturu stabla.
Kada završite sa razmatranjem potencijalnih situacija do kojih može doći pri uklanjanju čvorova, nastavljamo sa izlaganjem ....
Nekoliko jednostavnih i očiglednih primera
U stablu koje koristimo, najmanji problem izaziva (potencijalno) uklanjanje čvora #16 (što ste najverovatnije zaključili i sami), i upravo to će biti prvi primer koji ćemo razmotriti.
Prvo je potrebno osloboditi memoriju koju zauzima čvor #16, i zatim na čvoru #17 ukinuti referencu na levo podstablo (jednostavno: zadati polju Levi vrednost null) - posle čega je čvor 16 uklonjen iz stabla.
Neposredno uklanjanje je samo prvi korak, a da bismo bili sigurni da je stablo i dalje balansirano, potrebno je preračunati faktore balansiranosti svih čvorova na koje je uklanjanje čvora moglo uticati.
Ako se pitate: koji čvorovi se moraju uzeti u obzir, odgovor je (kao i kod procedure dodavanja) - direktni preci.
Međutim, sama procedura ispitivanja i rebalansiranja, nije "skroz" ista kao kod dodavanja (ima dodatnih "začkoljica", to jest, može biti potrebe za dodatnim koracima, i o svemu ćemo detaljnije diskutovati u nastavku).
Čvorovi koje treba proveriti (na putanji od uklonjenog čvora do korena), označeni su plavom bojom, a posle ažuriranja faktora balansiranosti ....
.... vidimo da uklanjanjem čvora #16 - balans stabla nije narušen.
Sledeći primer biće malo komplikovaniji: vraćamo se na početno stablo (vraćamo nazad čvor #16), i ovoga puta uklanja se čvor #17 (u idejnom smislu - čvor koji ima levo podstablo).
U praktičnom smislu, navedeno podstablo je jedan list (čvor #16), ali, procedura za uklanjanje ne razlikuje se od procedure koja bi bila primenjena kada bi u pitanju bilo razgranato podstablo.
Ovoga puta, procedura za uklanjanje je sledeća: budući da čvor (17) ima samo jedno podstablo, koren tog podstabla može neposredno zameniti čvor koji se uklanja, i stoga se direktnom pretku čvora #17 (čvoru #15) ....
.... može direktno pripojiti levo podstablo čvora #17 (kao što smo već naveli, u pitanju je praktično samo čvor #16):
Naravno, ostaje provera balansa, ali, posle ažuriranja faktora balansiranosti ....
.... može se zaključiti da je stablo i dalje u ravnoteži.
Do sada smo iscrpeli jednostavne primere (situacije u kojima je postupak "očigledan"), i stoga ćemo se u nastavku baviti (kompleksnijim) procedurama opšteg tipa.
Uklanjanje čvorova - opšte smernice
Pre svega, kada je u pitanju sam čvor koji se uklanja, postoje tri osnovne situacije:
- čvor koji se uklanja je list (nema potomke)
- čvor koji se uklanja ima jedno podstablo
- čvor koji se uklanja ima oba podstabla
U bilo kojom od tri navedena slučaja, posle uklanjanje čvora pristupa se ažuriranju faktora balansiranosti svih predaka (pri čemu se potencijalno preduzimaju i dodatni koraci):
- ako algoritam ni na jednom mestu ne naiđe na čvor koji je potrebno balansirati, može se zaključiti da je stablo u stanju balansa (i nema potrebe za preduzimanjem daljih koraka)
- ako algoritam naiđe na određeni čvor koji je potrebno balansirati, primenjuje se jedna od četiri procedure za balansiranje čvora i nastavlja se sa ažuriranjem faktora balansiranosti (i, po potrebi - rebalansiranjem), i svih preostalih čvorova
Situacija #2 je drugačija od one koja nastaje posle dodavanja čvora (to su "začkoljice" koje smo naveli u prethodnom odeljku), i veoma je bitno razumeti, da - u slučaju procedure koja se primenjuje posle uklanjanja čvora - rebalansiranje prvog disbalansiranog čvora, neće obavezno uspostaviti balans celog stabla, već je potrebno da se i preci bliži korenu takođe ispitaju i - po potrebi - rebalansiraju (što ćemo kasnije i pokazati na primeru).
Procedura za uklanjanje čvora koji nema potomke (uklanjanje 'lista')
Procedura za uklanjanje čvora koji nema potomke je sledeća:
- preko metode za pretragu, potrebno je pronaći referencu na čvor koji se uklanja (ukoliko vrednost koja se uklanja ne postoji u stablu, procedura za uklanjanje se prekida)
- memoriju koju pronađeni čvor zauzima, potrebno je osloboditi (kao što smo već naveli, ako se implementacija obavlja u programskom jeziku Java, ovaj korak je automatizovan)
- na čvoru koji je direktni predak čvora koji se uklanja, potrebno je ukinuti referencu na čvor koji se uklanja (u Javi: postaviti vrednost reference na
null) - potrebno je ažurirati faktore balansiranosti svih predaka uklonjenog čvora
- ukoliko se pronađe čvor sa narušenim balansom - potrebno je primeniti proceduru za rebalans čvora
Primer uklanjanja 'lista', koji prikazuje situaciju u kojoj uklanjanje čvora ne remeti balans stabla, videli smo u prvom delu prethodnog odeljka (uklanjanje čvora #16).
Pogledajmo sada komplikovaniji primer uklanjanja 'lista', koji podrazumeva rebalansiranje stabla.
Primer uklanjanja 'lista' koji podrazumeva rebalansiranje stabla
Vratićemo se na početnu postavku stabla, i uklonićemo čvor #12 (list):
Uklanjanjem čvora #12 nastaje disbalans, ali, vidimo da je u pitanju disbalans "lokalnog karaktera" (poremetili smo samo čvor #15):
Problem se rešava DL rotacijom i (kao što vidimo), posle ažuriranja visine i faktora balansiranosti svih relevantnih čvorova ....
.... možemo zaključiti da je AVL stablo ponovo u stanju ravnoteže (čak smo malo i 'popravili' desnu stranu).
Procedura za uklanjanje čvora sa jednim podstablom
Procedura za uklanjanje čvora sa jednim podstablom je sledeća:
- preko metode za pretragu, potrebno je pronaći referencu na čvor koji se uklanja (ukoliko vrednost koja se uklanja ne postoji u stablu, procedura za uklanjanje se prekida)
- pokazivač (na direktnom pretku), koji je pokazivao na čvor koji se uklanja, povezuje se sa direktnim potomkom čvora koji se uklanja
- memoriju koju zauzima čvor koji se uklanja, potrebno je osloboditi
- potrebno je ažurirati faktore balansiranosti svih predaka uklonjenog čvora
- ukoliko se pronađe čvor sa narušenim balansom - potrebno je primeniti proceduru za rebalans čvora
U prvom odeljku razmotrili smo i primer uklanjanja čvora sa jednim podstablom (uklanjanje čvora #17), pri čemu, kao i u najjednostavnijem primeru uklanjanja lista (čvor #16), nije bio poremećen balans stabla nakon uklanjanja.
Ovoga puta, uklonićemo čvor #22, posle čega će biti potrebno obaviti i rebalans stabla.
Primer uklanjanja čvora sa jednim podstablom (koji podrazumeva rebalansiranje stabla)
Ponovo se vraćamo na početnu postavku stabla i uklanjamo čvor #22 (čvor sa jednim podstablom):
Čvor #22 se uklanja, a pokazivač na čvoru #18, koji je pre uklanjanja pokazivao na čvor #22, povezuje se sa čvorom #24.
Posle ažuriranja stabla, primećuje se da je disbalans nastao na čvoru #18:
Problem se rešava LD rotacijom čvora #18 ....
.... posle čega je stablo ponovo u ravnoteži.
Procedura za uklanjanje čvora sa oba podstabla
Procedura za uklanjanje čvora koji ima oba podstabla, nešto je kompleksnija:
- preko metode za pretragu, potrebno je pronaći referencu na čvor koji se uklanja (ukoliko vrednost koja se uklanja ne postoji u stablu, procedura za uklanjanje se prekida)
- preko metode za pronalaženje inorder sledbenika (prva sledeća veća vrednost u stablu), pronalazi se čvor koji će u stablu zameniti čvor koji se uklanja
- čvor koji se uklanja, preuzima osnovnu celobrojnu vrednost od svog inorder sledbenika
- za čvor koji predstavlja inorder sledbenika, pokreće se procedura za uklanjanje (koja podrazumeva postupak iz jednog od dva prethodna poglavlja, budući da inorder sledbenik ne može imati oba podstabla)
U praktičnom smislu: iz stabla se uklanja (celobrojna) vrednost koja se navodi kao kriterijum za uklanjanje, ali, zato je sam čvor koji se uklanja - inorder sledbenik.
Primer uklanjanja čvora koji ima oba podstabla - sa jednostavnim rebalansiranjem
Da bismo bolje razumeli relativno složenu proceduru uklanjanja čvora sa oba podstabla, razmotrićemo primer uklanjanja korenog čvora (čvor #10):
Budući da se podstabla oko čvora #10 ne mogu "tek tako prespajati" (što bi "potencijalno", "trebalo raditi" * u slučaju kada bismo doslovno uklonili navedeni čvor, bez preduzimanja dodatnih koraka), potrebno je prvo pronaći inorder sledbenika, to jest - čvor sa prvom sledećom većom vrednošću (u primeru koji razmatramo, inorder sledbenik je čvor #12):
U sledećem koraku, vrednost inorder sledbenika (12), * kopira se na mesto čvora čija se vrednost koristi kao kriterijum za uklanjanje ....
Budući da je (u sledećem koraku), potrebno ukloniti iz stabla prvobitni čvor #12 (u AVL stablu ne smeju postojati duplikati), može se primetiti da procedura za uklanjanje čvora koji ima oba podstabla, u praktičnom smislu podrazumeva - uklanjanje inorder sledbenika - uz prethodno preuzimanje vrednosti inorder sledbenika (i ostalih podataka, ukoliko postoje).
Prema pravilima koja smo već naveli, (prvobitni) čvor #12 ....
.... kao inorder sledbenik čvora #10, može imati najviše jedno podstablo (jer, u suprotnom, neki drugi čvor iz levog podstabla bio bi inorder sledbenik), i stoga se procedura za uklanjanje čvora #12, svodi na jednu od dve jednostavnije procedure (u konkretnom slučaju, u pitanju je procedura za uklanjanje čvora bez potomaka).
Posle uklanjanje čvora #12, potrebno je proveriti faktore balansiranosti direktnih predaka (čvorova #15, #18), i faktor balansiranosti nekadašnje pozicije čvora #10 (na kojoj je sada vrednost 12):
Primećujemo da je čvor #15 izgubio balans ....
.... ali, taj problem se lako rešava DL rotacijom.
Posle ažuriranja faktora balansiranosti relevantnih čvorova ....
.... može se konstatovati da je stablo (ponovo) u stanju balansa.
Videćemo još i to da je procedura za pronalaženje inorder sledbenika veoma jednostavna za implementaciju, ali, pre nego što se time pozabavimo, pogledaćemo još dva specifična slučaja sa kojima se možemo sresti pri uklanjanju čvorova.
Primer uklanjanja 'lista' - sa kompleksnim rebalansiranjem
Kada smo na početku govorili o uklanjanju listova, spomenuli smo da takvo uklanjanje takođe može pokrenuti složenu proceduru rebalansiranja, što ćemo u nastavku prikazati preko primera.
Posle uklanjanja čvora #4 ....
.... nastaje disbalans ("DL" struktura):
Disbalans levog podstabla rešava se primenom DL rotacije ....
.... međutim, za razliku od procedure za dodavanje čvora, kod koje bi rebalansiranje jednog čvora ("prvog" čvora na kome je nastao disbalans), povratilo balans celog stabla, u slučaju rebalansiranja koje sledi posle uklanjanja čvora - primećujemo da je moguće zateći situaciju u kojoj su i dalji preci - takođe u stanju disbalansa (u ovom slučaju, samo koreni čvor):
Naravno, kao što smo prethodno naveli, procedura za uklanjanje čvora podrazumeva naknadnu proveru (i rebalansiranje, po potrebi), svih predaka - a ne samo najbližeg disbalansiranog pretka.
Budući da koreni čvor stabla (čvor #10), 'preteže' na desnu stranu, pri čemu koreni čvor desnog podstabla (čvor #18), ima faktor balansiranosti 1, može se zaključiti da je rešenje za ovakav disbalans - DL rotacija korenog čvora:
Kao i do sada, 'odvezaćemo' podstabla i posmatraćemo čvorove koji učestvuju u "DL" rebalansu kao običnu "A-C-B" šemu ....
.... u sledećem koraku, potrebno je rebalansirati tri izabrana čvora ....
.... i zatim vratiti podstabla na odgovarajuća mesta:
Kada se faktori balansa ažuriraju ....
.... može se zaključiti da je stablo ponovo u stanju ravnoteže:
Pre nego što pređemo na implementaciju algoritma za uklanjanje čvorova, pogledajmo još jednu zanimljivu situaciju.
Primer uklanjanja lista koji ima komplementarno podstablo sa faktorom balansiranosti 0
U poslednjem primeru, koristićemo početno stablo sa ponešto izmenjenom strukturom ....
.... pri čemu se (ponovo) uklanja čvor #4:
Budući da ovoga puta čvor #16 ne postoji, vidimo da je za rebalansiranje celog stabla (pošto uklonimo čvor #4) - dovoljno da se rebalansira čvor #5, ali, budući da dolazimo u pomalo čudnu situaciju (do kakve ne može doći posle dodavanja čvora) ....
.... nastaje dilema: da li je na ovom mestu potrebno primeniti "DD" rotaciju, ili "DL" rotaciju?
Međutim, zapravo je svejedno koja će rotacija biti primenjena (i videćemo koliko je lako to rešiti u implementaciji).
Balans se može povratiti preko DD rotacije:
.... a može se povratiti i preko DL rotacije:
Za sam kraj, naravno ....
Implementacija
Postupak za pronalaženje inorder sledbenika najavili smo kao proceduru koja je veoma jednostavna za implementaciju, i nadamo se da vas po tom pitanju nećemo 'prevariti'. :)
Pronalaženje inorder sledbenika
Budući da se inorder sledbenik nalazi u desnom podstablu čvora koji se uklanja, * metoda kao argument prima koren desnog podstabla, i potom se traži najmanja vrednost (koja se nalazi "skroz levo").
Cvor PronalazenjeSukcesora(Cvor C) {
if (C == null) return;
Cvor P = C;
while (P.Levi != null) {
P = P.Levi;
}
return P;
}
Uklanjanje čvora
Sama metoda za uklanjanje čvorova, može se podeliti u nekoliko delova:
- pronalaženje čvora
- izbor postupka za uklanjanje, s obzirom na broj potomaka pronađenog čvora
- pomoćna provera stanja čvora
- ažuriranje visine i faktora balansiranosti čvora
- provera faktora balansiranosti i rebalansiranje po potrebi
Cvor UklanjanjeCvora(Cvor C, int Vrednost) {
// Prvi uslov je tu "za svaki slučaj" (takođe,
// na ovom mestu možemo implementirati i poruku
// o tome da tražena vrednost nije pronađena
// u stablu) ....
if (C == null) return C;
// 1. Ukoliko procedura nije "pala" već na
// prethodnom uslovu, prvo je potrebno pronaći
// čvor koji nosi traženu vrednost:
if (Vrednost < C.Vrednost) {
C.Levi = UklanjanjeCvora(C.Levi, Vrednost);
}
if (Vrednost > C.Vrednost) {
C.Desni = UklanjanjeCvora(C.Desni, Vrednost);
}
// Ukoliko se do ovog mesta ne pronađe čvor sa
// traženom vrednošću, proradiće - u sledećem
// rekurzivnom pozivu - prvi if (koji smo na početku
// označili uz komentar: "za svaki slučaj") ....
// 2. Kada se čvor pronađe, ulazi se
// u sledeće grananje:
if (Vrednost == C.Vrednost) {
// Ukoliko pronađeni čvor nema potomke,
// dodeljuje mu se (preko pomoćnog čvora)
// vrednost null
if (C.Levi == null && C.Desni == null) {
Cvor P1 = null;
}
// Ako pronađeni čvor ima samo levo podstablo,
// biće zamenjen (preko pomoćnog čvora), svojim
// levim podstablom
if (C.Levi != null && C.Desni == null) {
Cvor P1 = C.Levi;
}
// Ako pronađeni čvor ima samo desno podstablo,
// biće zamenjen (preko pomoćnog čvora), svojim
// desnim podstablom
if (C.Levi == null && C.Desni != null) {
Cvor P1 = C.Desni;
}
// Ukoliko pronađeni čvor ima oba podstabla,
// potrebno je pronaći direktnog inorder
// sledbenika, preuzeti vrednost inorder
// sledbenika, i zatim pokrenuti proceduru za
// uklanjanje inorder sledbenika
if (C.Levi != null && C.Desni != null) {
Cvor P2 = pronalazenjeSukcesora(C.Desni);
C.Vrednost = P2.Vrednost;
C.Desni = UklanjanjeCvora(C.Desni, P2.Vrednost);
}
else {
// Ako čvor nema nijedno podstablo, dobiće
// vrednost koja je, u prethodnom delu,
// pripremljena preko pomoćnog čvora P1
C = P1;
}
}
// 3. Ne dajte da vas ovaj naizgled nepotrebni
// if zbuni: u određenim okolnostima, u toku
// izvršavanja metode, čvor se dereferencira
// (vrednost čvora postavlja se na null),
// i stoga je donji if - i te kako neophodan.
if (C == null) return C;
// 4. Ažuriranje visine i faktora balansiranosti,
// obavezno je (i očekivano)
Azuriranje(C);
// 5. Koristićemo iste procedure za rebalans
// koje smo koristili za dodavanje čvorova,
// ali, if-ovi koji pokreću metode, nešto su
// drugačiji (uz razlike na koje smo se
// prethodno osvrnuli).
if (C.BalansFaktor > 1 && C.Levi.BalansFaktor >= 0) {
return RotacijaLL(C);
}
if (C.BalansFaktor > 1 && C.Levi.BalansFaktor < 0) {
return RotacijaLD(C);
}
if (C.BalansFaktor < -1 && C.Desni.BalansFaktor <= 0) {
return RotacijaDD(C);
}
if (C.BalansFaktor < -1 && C.Desni.BalansFaktor > 0) {
return RotacijaDL(C);
}
return C;
}
Budući da je programski kod iz gornjeg odeljka 'izdašno prokomentarisan', nećemo se previše zadržavati na dodatnim objašnjenjima.
Međutim (da ipak ne propustimo da pomenemo), vidimo ponovo da je (upravo) rekurzija, mehanizam koji omogućava da se efikasno 'prođe' kroz pretke čvora koji se uklanja (sad je već 3:0 za rekurziju). :)
Zaključak
Ovim člankom završili smo opis implementacije AVL stabla (koja obuhvata sve uobičajene operacije koje se u AVL stablima javljaju).
Za vežbu, pokušajte da implementirate AVL stablo u nekom programskom jeziku "koji nije Java".
Ako nas pitate, mogli biste prvo probati C ("teža varijanta"), a potom (na primer), i Python i/ili JavaScript ("lakša varijanta", ali, nije bez izazova).