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:

• osnovna struktura čvorova i stabla
• pretraga stabla
• obilazak stabla
• dodavanje čvorova
• uklanjanje čvorova

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

Osnovnu strukturu AVL stabla možemo definisati preko dve klase:

• Cvor - klasa koja definiše strukturu pojedinačnih čvorova
• Stablo - klasa koja sadrži referencu na koreni čvor i sve neophodne metode za rad sa stablom

U praksi, postoji više 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, a u praksi je sasvim uputno da se beleže i dodatni podaci, kao što su (na primer), visina podstabla (koje ima koren u posmatranom čvoru), i faktor balansiranosti.

Dakle, 'krajnji bilans' polja koja smo izabrali za implementaciju, je sledeći:

• celobrojna vrednost (preko koje je definisana pozicija čvora u stablu)
• 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;
	}
}
		
	

Konstruktor klase (kao što vidimo), namenjen je dodavanju 'listova' stabla - č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;
	}
}
		
	

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 pri pokretanju prima vrednost korenog čvora kao argument, a predvideli smo i konstruktor bez parametara (u člancima o implementaciji AVL stabla, takav konstruktor zapravo nećemo koristiti, ali, možda čitaocima "negde usput" zatreba).

Klasa Stablo je za sada prilično 'prazna', i stoga ćemo početi 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, i potom dobijeni rezultat uvećati za jedan.

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;
}
		
	

.... 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;
}
		
	

Faktor balansiranosti (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 implementirati funkciju za ažuriranje:

		
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;
}
		
	

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 inače (sigurni smo 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 šta je prava svrha takvog grananja (sledi dodatno objašnjenje).

Metoda za ažuriranje važan je deo metoda za dodavanje i uklanjanje čvorova, unutar kojih postoje rekurzivni pozivi čija je svrha obilazak stabla.

Shodno navedenom, jasno je da će neki od rekurzivnih poziva pokušavati da "skrenu" prema "praznim" delovima stabla (ni iz daleka retko), to jest, biće rekurzivnih poziva koji će pokušati da pristupe čvorovima koji ne postoje.

U takvim situacijama, svakako je neophodno 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.

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č - apsolutno je vredno truda. :))

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