AVL Stablo - Implementacija - 1. deo - Osnovna struktura

Uvod

Pošto smo se prethodno upoznali sa AVL stablima (visinski balansiranim binarnim stablima pretrage), prikazaćemo kroz nekoliko članaka kako se AVL stablo može implementirati u programskom jeziku Java. *

U ukupno pet nastavaka, pisaćemo o sledećim temama:

Preporučujemo da pre čitanja svakog od članaka pokušate da samostalno osmislite i implementirate postupke koji su tema članka (a u slučaju prvog članka, i samu osnovnu strukturu čvorova i stabla).

Dodatno 'mentalno angažovanje' (koje preporučujemo), važan je preduslov za postizanje pravog razumevanja tematike, a u slučaju da uspete da samostalno osmislite postupke (što svakako želimo da se desi 🙂), u člancima ćete naći potvrdu za vaša samostalna otkrića, ili podstrek za dalje razmišljanje, ukoliko se vaše rešenje po nečem razlikuje od rešenja koja ćemo prikazati.

Struktura AVL stabla

Osnovna struktura AVL stabla može se (praktično) definisati preko dve klase:

Cvor - klasa koja opisuje strukturu pojedinačnih čvorova
Stablo - klasa koja sadrži referencu na koreni čvor i sve neophodne metode za obavljanje operacija sa stablom

Postoji nekoliko 'tipičnih' načina za implementaciju AVL stabla, pri čemu je osnovna dilema: da li zapisivati dodatne podatke, ili, računati vrednosti 'na licu mesta' / u trenutku kada se ukaže potreba?

Dodatni podaci ne zauzimaju previše mesta, računanje ne oduzima previše vremena, a mi smo izabrali način koji podrazumeva zapisivanje dodatnih podataka, budući da takav pristup smatramo najpraktičnijim (i u fazi izučavanja teorije, i u praksi).

Struktura čvora

Na slikama koje ste mogli videti u uvodnom članku o AVL stablima, deluje da svaki čvor sadrži samo jedan podatak (celobrojnu vrednost), ali, u implementaciji (nije teško pretpostaviti), potrebno je beležiti bar tri podatka.

Osim celobrojne vrednosti, neophodno je da se među polja uvrste i reference na levi i desni čvor, s tim da je u praksi sasvim uputno da se beleže i dodatni podaci, kao što su (npr) visina podstabla (koje ima koren u posmatranom čvoru) i faktor balansiranosti.

Dakle, 'krajnji bilans' izabranih polja, je sledeći:

celobrojna vrednost ('ključ' za pretragu/dodavanje/uklanjanje)
referenca na levi čvor
referenca na desni čvor
visina podstabla (čiji je koren u posmatranom čvoru)
faktor balansiranosti

U situaciji kada bismo AVL stablo koristili za brzo pronalaženje objekata određene klase po ključu - što zapravo i jeste prava svrha stabala pretrage, celobrojna vrednost (koju vidimo "u kružićima", na slikama), bila bi ključ, a referenca na klasu (tj. 'objekte klase'), takođe bi bila dodata među polja klase Cvor.

Na sledećoj slici, prikazana je klasa koja odgovara prethodno opisanoj strukturi:

		
public class Cvor {
	public int  vrednost;
	public Cvor levi,
	            desni;
	public int  visina,
	            balansFaktor;
	
	public Cvor(int vrednost) {
		this.vrednost     = vrednost;
		this.levi         = null;
		this.desni        = null;
		this.visina       = 1;
		this.balansFaktor = 0;
	}
}

Slika 1. - Klasa koja predstavlja pojedinačni čvor u stablu.

Konstruktor klase namenjen je (kao što vidimo), dodavanju 'listova' stabla (tj. čvorova koji nemaju 'potomke'), i stoga je početna visina 'tek dodatih čvorova' 1, a faktor balansiranosti 0.

Struktura stabla u AVL implementaciji

Klasa koja definiše stablo krajnje je jednostavna, i podrazumeva da se strukturi stabla pristupa preko (samo) jednog polja - koje predstavlja referencu na koreni čvor.

		
public class Stablo {
	public  Cvor koren;
	private int  brojac;
	
	public Stablo(int vrednost) {
		this.koren  = new Cvor(vrednost);
		this.brojac = 0;
	}

	public Stablo() {
		this.koren  = null;
		this.brojac = 0;
	}
}

Slika 2. - Osnovna struktura klase Stablo (metode ćemo dodavati naknadno).

Dodali smo i promenljivu Brojac, koja broji korake u pretrazi, to jest, predstavlja svojevrstan "merač dubine pretrage" (takva promenljiva dobro će doći za isprobavanje u fazi učenja, a ne smeta ni inače).

Osnovni konstruktor prima (pri pokretanju) vrednost korenog čvora kao argument, a predvideli smo i konstruktor bez parametara (iako u člancima o implementaciji AVL stabla takav konstruktor zapravo nećemo koristiti, može se desiti da čitaocima "negde usput" zatreba).

Klasa Stablo je za sada prilično 'prazna', ali, počećemo da dodajemo metode ....

Za kraju uvodnog članka (odnosno, pre nego što se posvetimo glavnim metodama, u narednim člancima), osmislićemo i implementirati pomoćnu metodu za ažuriranje visine podstabla i faktora balansiranosti.

Pomoćna metoda za ažuriranje

Osnovna ideja za računanje visine podrazumeva sledeće korake:

proveriti koje od dva podstabla (levo ili desno), ima veću visinu
uvećati dobijeni rezultat za 1

Prethodno navedena ideja, sama po sebi jeste korektna, međutim, ukoliko program pokuša da neposredno očita visinu podstabla koje ne postoji (to jest, ako bilo koji od dva pokazivača, Levi ili Desni, pokazuje na null čvor) ....

		
if (c.levi.visina > c.desni.visina) {
	c.visina = c.levi.visina + 1;
}
else {
	c.visina = c.desni.visina + 1;
}

Slika 3. - Pokušaj računanja visine podstabla (osnovna ideja je korektna, sama po sebi, ali - u praksi - mogu nastati problemi ukoliko pokušamo da pokrenemo gornji kod bez prethodne provere levog i desnog podstabla).

.... lako se može desiti da dođe do greške u izvršavanju programa!

Da ne bismo dolazili u situacije u kojima program 'puca' (sasvim opravdano), zbog pokušaja pristupa nepostojećim čvorovima, implementiraćemo prvo pomoćnu metodu za očitavanje visine podstabla (čiji je koren u čvoru koji se predaje kao argument pri pozivu funkcije):

		
public int ocitavanjeVisine(Cvor c) {
	if (c == null) return 0;

	return c.visina;
}

Slika 4. - Pomoćna metoda za očitavanje visine podstabla (čiji je koren - čvor koji se predaje kao argument).

Metoda za ažuriranje biće korišćena i za računanje faktora balansiranosti (što je vrednost koja, kao što je poznato od ranije, takođe zavisi od visine levog i desnog podstabla), i - budući da su sada ispunjeni uslovi za uredno očitavanje svih podataka - možemo prikazati programski kod:

		
public void azuriranje(Cvor c) {
	// 1. Za 'nepostojeće čvorove':
	if (c == null) return;
	
	// 2. Očitavanje visine za oba podstabla:
	int visinaL = ocitavanjeVisine(c.levi);
	int visinaD = ocitavanjeVisine(c.desni);

	// 3. Ažuriranje podataka:
	c.visina       = (visinaL > visinaD)? visinaL + 1 : visinaD + 1;
	c.balansFaktor = visinaL - visinaD;
}

Slika 5. - Metoda za ažuriranje visine i faktora balansiranosti podstabla (referenca na koreni čvor podstabla predaje se kao argument).

Algoritam je jednostavan:

ukoliko se funkciji preda nepostojeći čvor, prekida se izvršavanje (komentar #1)
u nastavku, očitavaju se visine levog i desnog podstabla (komentar #2)
na kraju, računa se visina podstabla (čiji je koren u posmatranom čvoru), kao i faktor balansiranosti (komentar #3)

U idejnom smislu, poslednje dve naredbe (#3), svakako su najvažnije, međutim, poslednje dve naredbe ne mogu se izvršiti bez pripreme podataka (#2), ali - to su stvari koje čitaoci sasvim dobro razumeju i bez dodatne napomene (verujemo da je tako).

Pravu zabunu može izazvati samo (naizgled čudan i ni izdaleka intuitivan) if koji primećujemo na početku, ali, ako 'malo bolje razmislimo o svemu', nije teško uvideti da takvo grananje praktično omogućava pravilno funkcionisanje ('glavnih') metoda koje koriste metodu za ažuriranje:

metoda za ažuriranje je (primera radi), važan deo metoda za dodavanje i uklanjanje čvorova, unutar kojih postoje rekurzivni pozivi čija je svrha obilazak stabla
ukoliko, u okviru dve navedene metode, neki od rekurzivnih poziva pokuša da "skrene" prema "praznom" delu stabla, to jest, ukoliko rekurzivni poziv funkcije pokuša da pristupi čvoru koji ne postoji (što ni izdaleka nije redak događaj), potrebno je da postoji "zaštitni mehanizam"

Sledeći koraci ....

Kao što vidimo, čak i osnovni koraci u radu sa AVL stablom podrazumevaju određen nivo promišljanja i vođenja računa o detaljima, i u najmanju ruku se može reći da ostatak implementacije takođe nije "baš skroz jednostavan" i predstavlja (znamo to iz iskustva), krajnje solidan zalogaj za mlade programere koji se prvi put susreću sa implementacijama sličnog obima.

U praksi, mnogi (nažalost) odustanu i 'pre nego što su počeli' (od toga da samostalno implementiraju AVL stablo ili neku drugu strukturu podataka), međutim, samostalna izrada bilo kog od "delova implementacije" AVL stabla (da ne govorimo o samostalnoj implementaciji svih delova), predstavlja takođe i veliki izvor zadovoljstva i veliki podstrek za dalji napredak.

(Poverujte nam na reč: nije mnogo teško - i pri tom je apsolutno vredno truda. :))

U sledećem nastavku, pisaćemo o implementaciji pretrage u AVL stablu.

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.