nav_dugme codeBlog codeBlog
  • početna Početna stranica
  • Sačuvani članci Sačuvani članci
  • Članci
     (spisak)
  • Kontakt
Povratak na vrh stranice

Info & povezani članci Info o članku - dugme

Info

trejler_sat Datum objave: 21.11.2020.

trejler_dokument Jezici: Java

trejler_teg_narandzasti Težina: 9/10

Java
algoritam
avl
stablo pretrage
binarno stablo pretrage
strukture podataka
o(logn)
optimizacija
teorija
saveti

Tema: AVL stablo

Visinski balansirano (AVL) stabloImplementacija - 1. deo - Osnovna strukturaImplementacija - 2. deo - PretragaImplementacija - 3. deo - Obilazak stablaImplementacija - 5. deo - Uklanjanje čvorova
Generator AVL Stabla (web aplikacija)

Povezani članci

Binarno stablo pretrageBinarna stabla i algebarski izrazi (stablo izraza)Strukture podatakaBFS i DFS - Pronalaženje putanje kroz lavirintShunting Yard - Implementacija - 1. deo - Prevođenje izraza iz infiksnog u postfiksni zapisKlase složenosti algoritama (O notacija)Izbor prvog programskog jezikaASCII, UNICODE i UTF - Predstavljanje znakova na računarimaUNIX Time - Predstavljanje datuma i vremena na računarimaKako napraviti syntax highlighter
Svi članci
Programming isn't about what you know; it's about what you can figure out.
Chris Pine

AVL Stablo - Implementacija - 4. deo - Dodavanje čvorova

Facebook LinkedIn Twitter Viber WhatsApp E-mail
zoom_plus zoom_minus bookmark
početna > Članci > Teorija

Uvod

U četvrtom (pretposlednjem) nastavku serijala o implementaciji algoritma AVL bavićemo se procedurom za dodavanje novih čvorova u stablo.

Da bismo čitaocima olakšali proces upoznavanja sa tematikom (koja je nezanemarljivo kompleksna), podelićemo algoritam na sledeće celine:

  • 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 ....

AVL dodavanje 01
Slika 1. - AVL stablo koje će biti korišćeno kao 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 je poznato 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) ....

AVL dodavanje 02
Slika 2. - Dodavanje čvora koji neće poremetiti balans stabla - pronalaženje pozicije za novi čvor - korak 1.

.... odgovarajuća pozicija za novi čvor je očigledno ('negde') u levom podstablu.

Koren levog podstabla postoji ....

AVL dodavanje 03
Slika 3. - Dodavanje čvora koji neće poremetiti balans stabla - pronalaženje pozicije za novi čvor - korak 2.

.... š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:

AVL dodavanje 04
Slika 4. - Dodavanje čvora koji neće poremetiti balans stabla - postavljanje čvora na pronađenu poziciju.

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, potrebno je proveriti kako dolikuje - algoritamski).

Novi čvor ima faktor balansiranosti 0 ....

AVL dodavanje 05
Slika 5. - Dodavanje čvora koji neće poremetiti balans stabla - ažuriranje faktora balansiranosti - korak #1.

.... faktori balansiranosti u "ostatku stabla" nisu poznati ("unapred"), međutim, nije potrebno proveravati 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 će upravo preci biti ispitani).

Čvor #5 sada ima faktor balansiranosti 0:

AVL dodavanje 06
Slika 6. - Dodavanje čvora koji neće poremetiti balans stabla - ažuriranje faktora balansiranosti - korak #2.

Koreni čvor ima faktor balansiranosti -1 (i dalje):

AVL dodavanje 07
Slika 7. - Dodavanje čvora koji neće poremetiti balans stabla - ažuriranje faktora balansiranosti - korak #3.

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.

Usputno podsećanje: klasa koju koristimo za čvorove beleži visinu i faktor balansiranosti (i koristi metodu za ažuriranje navedenih polja), i stoga su ispunjeni tehnički preduslovi za implementaciju algoritama za dodavanje i uklanjanje čvorova.

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):

AVL dodavanje 08
Slika 8. - Dodavanje čvora koji će poremetiti balans stabla - pronalaženje pozicije za novi čvor - korak 1.

.... niti će mesto za novi čvor biti koren desnog podstabla.

AVL dodavanje 09
Slika 9. - Dodavanje čvora koji će poremetiti balans stabla - pronalaženje pozicije za novi čvor - korak 2.

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":

AVL dodavanje 10
Slika 10. - Dodavanje čvora koji će poremetiti balans stabla - pronalaženje pozicije za novi čvor - korak 3.

Pošto je nova vrednost (16), manja od 22, pretraga prelazi u levo podstablo čvora #22:

AVL dodavanje 11
Slika 11. - Dodavanje čvora koji će poremetiti balans stabla - pronalaženje pozicije za novi čvor - korak 4.

.... 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:

AVL dodavanje 12
Slika 12. - Dodavanje čvora koji će poremetiti balans stabla - postavljanje čvora na pronađenu poziciju.

Ako "pogledamo sliku", deluje da je ravnoteža narušena, ali (da se podsetimo), zadatak nećemo rešavati 'mi ljudi', već - računar.

Računarski program (koji ćemo prikazati na kraju), ustanoviće da li je (i gde) zapravo nastao disbalans, ažuriranjem označenih čvorova (koji predstavljaju pretke novog čvora).

Princip je isti kao u prethodnom primeru, ali: nakon dodavanja čvora 4 nije nastao disbalans, a ovoga puta je nastao (i biće rešen) ....

Čvor #16 (novi "list"), automatski je ažuriran pri dodavanju, i ima faktor balansiranosti 0.

AVL dodavanje 13
Slika 13. - Dodavanje čvora koji će poremetiti balans stabla - ažuriranje faktora balansiranosti novog čvora (čvor #16).

Sledeći po redu čvor, čvor #17, ima faktor balansiranosti 1 ....

AVL dodavanje 14
Slika 14. - Dodavanje čvora koji će poremetiti balans stabla - ažuriranje faktora balansiranosti direktnog pretka (čvor #17).

.... čvor #22 takođe ima faktor balansiranosti 1 ....

AVL dodavanje 15
Slika 15. - Dodavanje čvora koji će poremetiti balans stabla - ažuriranje faktora balansiranosti sledećeg pretka (čvor #22).

.... 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:

AVL dodavanje 16
Slika 16. - Dodavanje čvora koji će poremetiti balans stabla - ažuriranje faktora balansiranosti sledećeg pretka (čvor #15), pri čemu je ustanovljeno da je čvor #15 izgubio balans!

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)
AVL dodavanje 17
Slika 17. - Dodavanje čvora koji će poremetiti balans stabla - rebalansiranje disbalansiranog čvora #15 - pronalaženje čvorova koji učestvuju u rotaciji.

Kao što vidimo, u pitanju je struktura DL, koju smo i u uvodnom članku o AVL stablima koristili kao primer za balansiranje tri čvora.

Podsetićemo se u nastavku na to kako se rešava struktura DL, a kasnije ćemo prikazati kako se implementira DL rotacija (kao i druge rotacije).

Sa slike ćemo (privremeno) ukloniti faktore balansiranosti i fokusiraćemo se samo na podstrukturu koja učestvuje u balansiranju.

AVL dodavanje 18
Slika 18. - Dodavanje čvora koji će poremetiti balans stabla - rebalansiranje disbalansiranog čvora #15 - korak 1.

Uklonićemo privremeno (u prikazu), i veze između tri posmatrana čvora i njihovih podstabala ....

AVL dodavanje 19
Slika 19. - Dodavanje čvora koji će poremetiti balans stabla - rebalansiranje disbalansiranog čvora #15 - korak 2.

.... i potom se čvorovi balansiraju po šemi ACB iz uvodnog članka (u pitanju je DL rotacija):

AVL dodavanje 20
Slika 20. - Dodavanje čvora koji će poremetiti balans stabla - rebalansiranje disbalansiranog čvora #15 - korak 3.

Na slikama "vidimo" gde su podstabla, ali, u implementaciji se strogo mora voditi računa o tome gde (i kako) se privremeno čuvaju podstabla!

Posle DL rotacije, čvor #15 treba povezati sa "nekadašnjim" * levim podstablom ....

AVL dodavanje 21
Slika 21. - Dodavanje čvora koji će poremetiti balans stabla - rebalansiranje disbalansiranog čvora #15 - korak 4.

* Da se podsetimo: u implementaciji DL rotacije, veza između čvora sa najmanjom vrednošću i njegovog levog podstabla se ne raskida (jer za tim nema potrebe).

Novi čvor se pripaja čvoru #15, kao desno podstablo ....

AVL dodavanje 22
Slika 22. - Dodavanje čvora koji će poremetiti balans stabla - rebalansiranje disbalansiranog čvora #15 - korak 5.

Na kraju, čvor #22 treba (ponovo) povezati sa "starim" * desnim podstablom (čvor #24)

AVL dodavanje 23
Slika 23. - Dodavanje čvora koji će poremetiti balans stabla - rebalansiranje disbalansiranog čvora #15 - korak 6.

* Kao što smo (takođe) pominjali u uvodnom članku o AVL stablima, u implementaciji DL rotacije ne raskida se ni veza između čvora sa najvećom vrednošću i njegovog desnog podstabla (ni u ovom slučaju nema potrebe za razdvajanjem).

Posle rotacija, potrebno je 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).

AVL dodavanje 24
Slika 24. - Dodavanje čvora koji će poremetiti balans stabla - pregled čvorova koje je potrebno ažurirati.

Zarad preglednosti, prvo ćemo prikazati ažuriranje čvora koji nije na putanji od novog čvora prema korenu, i (praktično), čvor #22 u novoj situaciji ima faktor balansiranosti -1:

AVL dodavanje 25
Slika 25. - Dodavanje čvora koji će poremetiti balans stabla - ažuriranje faktora balansiranosti posle rebalansiranja - korak 1.

Čvor #16, kao novi čvor, ima faktor balansiranosti 0 ....

AVL dodavanje 26
Slika 26. - Dodavanje čvora koji će poremetiti balans stabla - ažuriranje faktora balansiranosti posle rebalansiranja - korak 2.

.... čvor #15 (nije teško izračunati), ima faktor balansiranosti 0 ....

AVL dodavanje 27
Slika 27. - Dodavanje čvora koji će poremetiti balans stabla - ažuriranje faktora balansiranosti posle rebalansiranja - korak 3.

.... čvor #17 takođe ima faktor balansiranosti 0 ....

AVL dodavanje 28
Slika 28. - Dodavanje čvora koji će poremetiti balans stabla - ažuriranje faktora balansiranosti posle rebalansiranja - korak 4.

.... i, na kraju, koreni čvor ponovo ima faktor balansiranosti -1.

AVL dodavanje 29
Slika 29. - Dodavanje čvora koji će poremetiti balans stabla - ažuriranje faktora balansiranosti posle rebalansiranja - korak 5 - stablo je ponovo u stanju balansa.

Kao što vidimo, ažuriranjem visina podstabala i proverom faktora balansiranosti, utvrđeno je ("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 ....

AVL - DD struktura
Slika 30. - Struktura DD (tj. A-B-C), sa kojom smo se upoznali u uvodnom članku.

.... ili DL struktura ....

AVL - DD struktura
Slika 31. - Struktura DL (tj. A-C-B), sa kojom smo se upoznali u uvodnom članku.

.... bude svedena na balansiranu strukturu, u kojoj: srednja vrednost predstavlja koreni čvor, najmanja vrednost stoji levo, a najveća desno ....

AVL - DD struktura
Slika 32. - Uravnotežena struktura tri čvora (B-A-C), sa kojom smo se (takođe) upoznali u uvodnom članku.

(Isti princip važi, naravno, i za "LL" i "LD" strukture.)

Metoda koju ćemo prikazati u nastavku, koja je specifično namenjena DD rotaciji, idejno se poklapa sa (jednostrukom) "D" rotacijom kakva se inače sreće u literaturi (figurativno, u oba slučaja je u pitanju "rotiranje" čvorova ukrug, za jedno mesto ulevo). *

Što se tiče LD ili DL rotacija, i njih možete implementirati na način koji se inače pominje u literaturi, preko DD rotacije koja sledi u nastavku (i LL rotacije koju možete implementirati samostalno (LL rotacija je "slika u ogledalu")).

* Ne dajte se zbuniti (nije greška): disbalansirana "DD" struktura se zapravo rešava "rotiranjem" ulevo (rotacija takođe nosi naziv po obliku disbalansirane strukture, a ne po smeru "rotiranja").

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 rotacijaDD(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;
}
		
	
Slika 33. - Implementacija - Metoda za obavljanje DD rotacije na disbalansiranom čvoru.

Metoda za DL rotaciju (za koju smo u ovom članku prikazivali primere sa slikama) ....

		
public Cvor rotacijaDL(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;
}
		
	
Slika 34. - Implementacija - Metoda za obavljanje DL rotacije na disbalansiranom čvoru.

.... nezanemarljivo je kompleksnija, i zahteva upotrebu pomoćnog čvora (bez koga veoma lako mogu nastati poveći problemi sa dereferenciranjem).

Budući da smo princip DL rotacije detaljno objasnili, i budući da su ovakvi članci (ipak) namenjeni programerima sa nezanemarljivim iskustvom i predznanjem, ostavićemo vam da sami detaljno proučite prikazane metode i 'pohvatate konce' (i da samostalno dodate metode za preostale dve rotacije). :)

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 rotacijaLL(c);
	}

	// LD:

	if (c.balansFaktor > 1  && c.levi.balansFaktor == -1) {
		return rotacijaLD(c);
	}

	// DD:

	if (c.balansFaktor < -1 && c.desni.balansFaktor == -1) {
		return rotacijaDD(c);
	}

	// DL:

	if (c.balansFaktor < -1 && c.desni.balansFaktor == 1) {
		return rotacijaDL(c);
	}

	// Ako nije bilo potrebe za balansiranjem ....
	
	return c; // .... samo će biti vraćen
			  //      pokazivač na čvor C. 
}
		
	
Slika 35. - Implementacija - Metoda za dodavanje novog čvora u stablo.

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 nekoliko važnih detalja.

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

Budući da smo ('preko slika') prikazivali 'intuitivne' i 'prirodne' postupke za izbor rotacija, * implementacija procedure za izbor rotacije mogla bi delovati kao vrlo komplikovan zahvat koji podrazumeva obilazak više čvorova (od prvog disbalansiranog čvora - prema čvoru čijim je dodavanjem narušen balans), međutim, kao što smo videli u gornjem bloku programskog koda (slika #35), ceo postupak se zapravo može svesti na jednostavno odlučivanje u dva koraka.

* Uradili smo tako, da bismo se što bolje razumeli implementaciju (tj. da bi bilo jasno 'kako i zašto' se prikazani postupci mogu svesti na jednostavno 'dvokrako odlučivanje').

Pre svega, za sam 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.

* Da se podsetimo: apsolutna vrednost faktora ravnoteže bilo kog čvora (u pravilno implementiranom AVL stablu), neće biti veća od 2, jer, čim faktor balansiranosti nekog čvora dostigne 2 (po apsolutnoj vrednosti), odmah se pokreće procedura za rebalansiranje (drugim rečima: i vrednost 2 se može sresti samo neposredno nakon dodavanja ** novog čvora).

** .... ili nakon uklanjanja čvora (ali to će biti tema za naredni članak).

Za "L" rotacije (tj. situacije u kojima "preteže" levo podstablo posmatranog čvora), posmatra se faktor balansiranosti direktnog levog potomka, pri čemu važe sledeća pravila:

  • 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že sledeća pravila:

  • 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 (na početku jeste pomalo komplikovano, ali, da naglasimo još jednom - krajnje vredno truda). :)

Autor članka Nikola Vukićević Za web portal codeblog.rs
Napomena: Tekstovi, slike, web aplikacije i svi ostali sadržaji na sajtu codeblog.rs (osim u slučajevima gde je drugačije navedeno) predstavljaju intelektualnu svojinu autora sajta codeblog.rs i zabranjeno je njihovo korišćenje na drugim sajtovima i štampanim medijima, kao i bilo kakvo drugo korišćenje u komercijalne svrhe, bez eksplicitnog pismenog odobrenja autora.
© 2020-2025. Sva prava zadržana.
Facebook LinkedIn Twitter Viber WhatsApp E-mail
početna > Članci > AVL Stablo - Implementacija - 4. deo - Dodavanje čvorova
codeBlog codeBlog
Sajt posvećen popularizaciji kulture i veštine programiranja.
Napomena: Tekstovi i slike na sajtu codeblog.rs (osim u slučajevima, gde je drugačije navedeno) predstavljaju intelektualnu svojinu autora sajta codeblog.rs i zabranjeno je njihovo korišćenje na drugim sajtovima i štampanim medijima, kao i bilo kakvo drugo korišćenje u komercijalne svrhe, bez eksplicitnog odobrenja autora.
© 2020-2025. Sva prava zadržana.
Facebook - logo
Instagram - logo
LinkedIn - logo
Twitter - logo
E-mail
Naslovna
   •
Uslovi korišćenja
   •
Obaveštenja
   •
FAQ
   •
Kontakt