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.
Priznajemo, nismo se baš mnogo trudili da izbegnemo 'antimarketinški'/'neoptimistični' 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 - uvodna 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, pri čemu ćemo koristiti stablo koje je veće i 'razgranatije' u odnosu na stabla koja smo do sada koristili:
Pre nego što počnemo da navodimo pravila za uklanjanje čvorova, toplo preporučujemo da (pre prelaska na naredni odeljak članka) prekinete 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 mogu ukloniti neposredno (sami po sebi), 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" izvestan 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 - i pri tom je postupak 'očigledan'), ali, neki drugi čvorovi zadavaće vam 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, a zatim se na čvoru #17 ukida referenca na levo podstablo (tako što se polju levi zadaje vrednost null) - posle čega je čvor 16 uklonjen iz stabla.
Neposredno uklanjanje je samo prvi korak, odnosno, potrebno je preračunati faktore balansiranosti svih čvorova na koje je uklanjanje čvora moglo uticati - da bismo bili sigurni da je stablo i dalje balansirano.
Na ovom mestu postavlja se pitanje koji čvorovi se moraju uzeti u obzir, a odgovor je (kao i u slučaju procedure za dodavanje čvorova) - direktni preci, međutim, sama procedura ispitivanja i rebalansiranja, nije "skroz ista" kao pri dodavanju čvorova (ima dodatnih "začkoljica", to jest, može biti potrebe za dodatnim koracima - o čemu ćemo detaljnije diskutovati nešto kasnije u članku).
Čvorovi koje treba proveriti (na putanji od uklonjenog čvora do korena), označeni su plavom bojom, a posle ažuriranja faktora balansiranosti ....
.... vidimo da nakon uklanjanja čvora #16 - balans stabla nije narušen.
Sledeći primer biće za nijansu komplikovaniji: vraćamo se na početno stablo (tj. vraćamo nazad čvor #16), ali, ovoga puta ćemo ukloniti č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 (tj. 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 kom 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 (što znači da 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 pomenuli 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 preko odgovarajućih primera).
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 sa vrednošću koja je predata kao 'ključ' za uklanjanje (ukoliko navedeni ključ 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 rebalansiranje čvora
U prvom primeru u članku (uklanjanje čvora #16), prikazana je situacija u kojoj uklanjanje čvora ne remeti balans stabla.
U nastavku, sledi 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 se da primetiti), posle ažuriranja visine i faktora balansiranosti svih relevantnih čvorova ....
.... AVL stablo je 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 sa vrednošću koja predstavlja ključ za uklanjanje (ukoliko navedeni ključ 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 rebalansiranje č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 (tj. č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 nastao disbalans 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
U prethodnim odeljcima, detaljno smo opisali dve jednostavnije procedure (sa kojima smo se okvirno upoznali još na početku, preko uvodnih primera), međutim, procedura za uklanjanje čvora koji ima oba podstabla, nešto je kompleksnija i podrazumeva drugačiji način razmišljanja, jer nije moguće samo ukloniti čvor i potom 'prespajati' okolne čvorove i podstabla.
Umesto 'očiglednog' postupka (koji u ovom slučaju nije moguć), obavlja se 'posredni'/'zaobilazni' postupak uz pronalaženje čvora koji može zameniti čvor čija se vrednost predaje kao kriterijum za uklanjanje:
- preko metode za pretragu, potrebno je pronaći referencu na čvor sa vrednošću koju treba ukloniti iz stabla (ukoliko navedena vrednost tj. navedeni ključ, 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 je predviđen za uklanjanje
- čvor sa vrednošću koja se koristi kao kriterijum za uklanjanje, preuzima osnovnu celobrojnu vrednost od svog inorder sledbenika
- inorder sledbenik se uklanja iz stabla - što podrazumeva postupak iz jednog od dva prethodna odeljka (budući da inorder sledbenik ne može imati oba podstabla)
Ukratko: iz stabla se uklanja celobrojna vrednost koja se navodi kao kriterijum (tj. 'ključ') za uklanjanje, ali, sam čvor koji se uklanja - zapravo je inorder sledbenik.
Postupak koji smo ukratko opisali nije trivijalan, * te stoga sledi detaljnija analiza.
Primer uklanjanja čvora koji ima oba podstabla - sa jednostavnim rebalansiranjem
Da bismo što bolje razumeli relativno složenu proceduru uklanjanja čvora sa oba podstabla, razmotrićemo primer uklanjanja korenog čvora (čvor #10):
Kao što smo prethodno nagovestili, čvor #10 se ne može ukloniti neposredno (nakon čega bi se "prespajala" podstabla i sl), i stoga je prvo potrebno pronaći inorder sledbenika, * to jest - čvor sa prvom sledećom većom vrednošću.
U primeru koji razmatramo, inorder sledbenik je čvor #12:
Kada se pronađe inorder sledbenik, navedeni čvor zauzeće mesto čvora koji se uklanja, što praktično znači da se vrednost inorder sledbenika (u ovom slučaju 12), ** kopira na mesto čvora čija se vrednost koristi kao kriterijum za uklanjanje ....
.... nakon čega sledi ostatak procedure.
Budući da je u sledećem koraku potrebno ukloniti iz stabla prvobitni čvor #12 (jer u AVL stablu ne smeju postojati duplikati (!)), možemo još jednom 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 bi u suprotnom neki drugi čvor iz desnog podstabla bio inorder sledbenik), i stoga se procedura za uklanjanje čvora #12 svodi na jednu od dve jednostavnije procedure.
Posle uklanjanje čvora #12, potrebno je proveriti: faktore balansiranosti direktnih predaka (tj. č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 (kao što smo već videli), primenom DL rotacije.
Posle rotacije i ažuriranja faktora balansiranosti relevantnih čvorova ....
.... može se konstatovati da je stablo (ponovo) u stanju balansa.
Videćemo i to da je procedura za pronalaženje inorder sledbenika veoma jednostavna za implementaciju, ali, pre nego što se pozabavimo navedenom procedurom, razmotrićemo i 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 odmah prikazati preko primera.
Posle uklanjanja čvora #4 ....
.... nastaje disbalansirana "DL" struktura:
Disbalans levog podstabla rešava se primenom DL rotacije ....
.... međutim, za razliku od procedure za dodavanje čvora, u kojoj rebalansiranje jednog čvora ("prvog" čvora na kome je nastao disbalans), uspostavlja 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 konkretnom primeru, samo je još koreni čvor u stanju disbalansa):
Naravno, kao što smo još ranije najavili, procedura za uklanjanje čvora podrazumeva naknadnu proveru (i rebalansiranje, po potrebi), svih predaka - ne samo najbližeg disbalansiranog pretka.
Budući da stablo 'preteže' na desnu stranu (na samom korenom čvoru), 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 treba 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:
Primer uklanjanja lista koji ima komplementarno podstablo sa faktorom balansiranosti 0
Pre nego što pređemo na implementaciju algoritma za uklanjanje čvorova, razmotrićemo još jednu zanimljivu situaciju.
U poslednjem primeru, koristićemo početno stablo sa ponešto izmenjenom strukturom ....
.... pri čemu se (ponovo) uklanja čvor #4:
S obzirom na to da čvor #16 ovoga puta ne postoji, vidimo da je za rebalansiranje celog stabla (pošto se ukloni č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 na ovom mestu treba 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
Kao što smo mogli videti u dosadašnjem toku članka, postupak za uklanjanje čvorova je relativno kompleksan u idejnom smislu, ali (za razliku od (recimo) implementacije metode za dodavanje čvorova), implementacija metode za uklanjanje čvorova nije ni iz daleka 'komplikovana', već samo 'obimna'.
Najpraktičnije: pošto napišemo metodu za pronalaženje inorder sledbenika (što sledi direktno u nastavku), preostaje samo da svaku situaciju koju smo do sada naveli, povežemo sa odgovarajućim programskim kodom.
Pronalaženje inorder sledbenika
Postupak za pronalaženje inorder sledbenika najavili smo kao proceduru koja je veoma jednostavna za implementaciju, i stoga se nadamo da po tom pitanju nećemo izneveriti vaša očekivanja. :)
Budući da se inorder sledbenik nalazi u desnom podstablu čvora koji se uklanja, * metoda prima koren desnog podstabla kao argument, 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 na 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 zbuni donji if
// (koji naizgled deluje nepotrebno):
// u određenim okolnostima, u toku
// izvršavanja metode, promenljiva C dobija
// sistemsku vrednost null, i stoga je
// sledeći if - i te kako neophodan.
if (c == null) return c;
// 4. Ažuriranje visine i faktora balansiranosti,
// predstavlja obavezan (i očekivan) korak.
azuriranje(c);
// 5. Koristićemo iste procedure za rebalans
// koje smo koristili pri dodavanju č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 zadržavati na dodatnim objašnjenjima.
Međutim (da ipak ne propustimo da pomenemo): vidimo ponovo da je rekurzija mehanizam koji omogućava da se efikasno 'prođe' kroz pretke čvora koji se uklanja (sada 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 želite izazov, mogli biste prvo probati C ("teža varijanta"), a potom (na primer), i Python i/ili JavaScript (svakako ponešto jednostavnije od implementacije u C-u, ali, nije trivijalno).