AVL Stablo - Implementacija - 1. deo - Osnovna struktura

Uvod

Članak pred vama, prvi je u serijalu članaka posvećenih implementaciji AVL algoritma (za kreiranje visinski balansiranog binarnog stabla pretrage), a tema prvog nastavka je implementacija osnovne strukture AVL stabla i pomoćnih metoda u programskom jeziku Java.

U sledeća četiri nastavka, pisaćemo o:

Preporučujemo vam da pre čitanja svakog od članaka pokušate da samostalno implementirate metode koje su tema članka, ili u slučaju ovog prvog članka - i samu osnovnu strukturu.

Samo tako ćete moći da zapravo razumete ono što možete pročitati na ovim stranicama, a, u slučaju da sami uspete (što svakako želimo da se desi :) ), naći ćete potvrdu za vaša samostalna otkrića, ili podstrek za dalju diskusiju / razmišljanje, ukoliko se vaše samostalno rešenje po nečem razlikuje od onog koje ste videli na sajtu.

Struktura AVL stabla

Osnovnu strukturu AVL stabla definisaćemo preko dve klase:

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

Iako je moguće sve izvesti upotrebom samo jedne klase, izbećićemo ovakav 'akrobatski' pristup (moramo naravno priznati da ima neke lepote u takvom pristupu, ali - bićemo praktični).

Struktura čvora

Na grafikonima koje ste mogli videti u članku o AVL stablima deluje da svaki čvor sadrži (samo) jedan podatak, ali, u implementaciji (kao što znamo), mora ih biti bar tri. Osim same vrednosti, neophodno je da koristimo i reference na levi i desni čvor.

Takođe, osim ako ne želimo da 'svaki čas' računamo visinu levog i desnog podstabla i, preko njih, visinu stabla koja odgovara datom čvoru, morao beležiti i visinu (pod)stabla za dati čvor (ili preciznije: podstabla čiji je koren u datom čvoru).

Dakle, osnovni podaci koje praktično moramo beležiti su:

celobrojna vrednost
referenca na levi čvor
referenca na desni čvor
visina stabla

U situaciji kada bismo AVL stablo koristili za brzo pronalalaženje objekata određene klase po ključu, navedena celobrojna vrednost bila bi ključ, a referencu na datu klasu bismo morali dodati među polja klase Cvor (u članku o pretrazi stabla ćemo se osvrnuti na jednu ovakvu strukturu, ali ćemo inače koristiti obične int čvorove).

Na sledećoj slici možete videti Java klasu koja odgovara opisanoj strukturi:

									
public class Cvor {
	public int  Vrednost;
	public Cvor Levi,
	            Desni;
	public int  VisinaLevi,
	            VisinaDesni,
	            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čne čvorove u stablu.

Konstruktor klase je (kao što vidimo) predviđen dodavanju 'listova' stabla (čvorova koji nemaju svoju 'decu' čvorove i čija je visina 1, a balans faktor 0), a primećujemo i određene dodatke.

Izabrali smo da čvorovi u našoj implementaciji beleže još nekoliko podataka:

visinu levog podstabla
visinu desnog podstabla
balans faktor

Postoji razlog protiv ovakvog pristupa (u nekim implementacijama AVL stabla, ove vrednosti se ne beleže), a to je naravno - dodatno memorijsko zauzeće koje nije zanemarljivo.

Međutim, postoji i razlog za ovakav pristup. Ukoliko se navedene vrednosti nigde ne beleže za dati čvor, to znači da moraju da se računaju 'svaki čas' (tako što ćemo pristupati njegovim direktnim potomcima, očitavati njihove visine i potom računati balans faktor datog čvora), a vreme koje je potrebno za takva izračunavanja - takođe nije zanemarljivo.

Ni jedan od ova dva pristupa nije pogrešan (niti previše problematičan), tako da nije previše bitno koji ćemo izabrati.

Mi smo izabrali onaj koji ipak smatramo racionalnijim i (bićemo iskreni) onaj koji nam se, jednostavno rečeno, više dopada intuitivno.

Struktura stabla u AVL implementaciji

Osnovna struktura stabla koju ćemo ovde izneti je krajnje jednostavna i podrazumeva samo jednu 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" stable). Takva promenljiva dobro će nam doći budući da je ovo školski primer implementacije AVL stabla (a ne smeta ni inače).

Osnovni konstruktor prima kao argument vrednost korenog čvora, a predvideli smo i konstruktor bez parametara (nama, za naše primere, neće trebati, ali, možda vama negde zatreba).

Klase Stablo je za sada poprilično 'prazna', pa ćemo polako početi da je popunjavamo metodama (u nastavku nećemo više, zarad preglednosti, prikazivati okvir klase koji ste ovde mogli videti, već samo metode za operacije kojima je serijal o AVL implementaciji posvećen, a njih naravno treba smestiti u telo klase).

Pomoćna metoda za ažuriranje visine

Pre svih ostalih 'zvaničnih' metoda, dodaćemo i dve pomoćne:

metodu za ažuriranje visine podstabla čiji je koren u datom čvoru
metodu za ažuriranje balans faktora

Metode ćemo (kao što smo već nagovestili) smeštati unutar klase Stablo.

Osnovna ideja je (naravno), da računamo visinu tako što ćemo proveriti koje od dva podstabla (levo ili desno) ima veću visinu, posle čega bismo tu vrednost samo uvećali za jedan, ali, kao što vidite, naša metoda ima pet if-ova, umesto recimo jednog ternarnog operatora (koji stoji tek na kraju).

Ovako moramo raditi jer ne srećemo se u svim situacijama sa čvorovima koji imaju oba podstabla, a takođe, preko rekurzivnih poziva upućivaćemo ovu metodu i na čvorove koji uopšte ne postoje.

Ako se u ovom trenutku dvoumite oko ovakvog pristupa (nije vam baš sve i baš skroz jasno), nemojte brinuti i smatrajte to dobrim znakom - to znači da ste podsvesno počeli da shvatate o čemu se sve mora voditi računa u implementaciji jedne ovakve strukture podataka (a nejasnoće će se razjasniti daljim proučavanjem).

									
public void AzuriranjeVisine(Cvor C) {
	
	// 1. Nepostojeći čvor:

	if (C == null) return;
	
	// 2. "List" stabla:

	if(C.Levi == null && C.Desni == null) {
		C.Visina = 1;
		return;
	}
	
	// 3. Čvor koji ima samo levo podstablo:

	if(C.Desni == null) {
		C.Visina = C.Levi.Visina + 1;
		return;
	}

	// 4. Čvor koji ima samo desno podstablo:

	if(C.Levi == null) {
		C.Visina = C.Desni.Visina + 1;
		return;	
	}
	
	// 5. Svi ostali čvorovi:

	C.Visina = (C.Levi.Visina >= C.Desni.Visina)?
	            C.Levi.Visina + 1 :
	            C.Desni.Visina + 1;
}

Slika 3. - Metoda za ažuriranje visine podstabla čiji je koren u datom čvoru.

Razmotrimo svih pet delova:

Ako dođe do toga da pokušamo da pristupimo čvoru koji ne postoji (kao što rekosmo malopre, za sada je samo bitno znati da će program dolaziti u takve situacije), jednostavno treba da odstupimo i ne radimo ništa dalje (komentar 1. u kodu).

Ukoliko je čvor list (komentar 2.), to jest, nema ni jedno ni drugo podstablo, njegova visina je 1 i to je upravo ono što metoda vraća (i naravno prekida izvršavanje).

Ukoliko čvor nema jedno od dva podstabla (komentari 3. i 4.), vratićemo visinu postojećeg podstabla uvećanu za 1. I na kraju ....

U svim ostalim situacijama (komentar 5.), uradićemo ono što sve vreme želimo da uradimo - koristićemo ternarni operator.

Pomoćna metoda za ažuriranje balans faktora

Pomoćna metoda za ažuriranje balans faktora je, u idejnom smislu, gotovo identična metodi za ažuriranje visine koju smo prethodno opisali, samo što ovoga puta ažuriramo balans faktor.

Takođe, kao što ćemo videti u člancima posvećenim dodavanju i brisanju čvorova, podrazumeva da ćemo, pre pozivanja metode za računanje balans faktora, pozivati / izvršavati metodu za računanje visine.

									
public void AzuriranjeBalansFaktora(Cvor C) {

	// 1. Nepostojeći čvor:

	if(C == null) return;
	
	// 2. "List" stabla:

	if(C.Levi == null && C.Desni == null) {
		C.BalansFaktor = 0;
		return;
	}

	// 3. Čvor koji ima samo levo podstablo:
	
	if(C.Desni == null) {
		C.BalansFaktor = C.Levi.Visina;
		return;
	}

	// 4. Čvor koji ima samo desno podstablo:
	
	if(C.Levi == null) {
		C.BalansFaktor = -C.Desni.Visina;
		return;
	}

	// 5. Svi ostali čvorovi:

	C.BalansFaktor = C.Levi.Visina - C.Desni.Visina;
}

Slika 4. - Metoda za ažuriranje balans faktora datog čvora.

Znamo od ranije da se balans faktor računa kao razlika visine levog i desnog podstabla.

Kada na grafikonima (u uvodnom članku o AVL implementaciji ili drugde) zapazimo da određenom čvoru fali jedno ili oba podstabla, možemo (idejno) balans faktor i dalje računati kao VL - VD (visine podstabala), uzimajući da je visina podstabla koje nedostaje 0 (a - 0 = a; 0 - a = -a; 0 - 0 = 0).

U implemetaciji ne možemo postupati tako jer visina 0 nije zapisana nigde. Ne smemo 'tek tako' pokušavati da pristupimo null čvorovima (podstablima koja ne postoje), 'nadajući se najboljem' (tome da za određeno brojčano polje vrati default vrednost - 0), jer null čvorovi - (doslovno) ne postoje, pa stoga i u ovoj metodi moramo proveravati da li je čvor null, pre nego što pokušamo da mu pristupimo.

Upravo zato je "petostepeno odlučivanje" i dalje tu.

Zaključak

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. Ostatak implementacije svakako nije "baš skroz jednostavan" i predstavlja (znamo to iz iskustva), krajnje solidan zalogaj za mlade programere.

Ali, samostalna implemetacija bilo kog od delova AVL stabla (da ne govorimo o samostalnoj implementaciji celog stabla sa svim funkcijama), predstavlja, sa druge strane, veliki izvor zadovljstva i podstrek za dalji napredak (poverujte nam na reč - apsolutno je vredno truda).

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