AVL Stablo - Implementacija - 1. deo - Osnovna struktura

Uvod

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

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

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

Samo tako ćete moći da zapravo razumete ono što možete pročitati, 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:

Cvor - klasa koja definiše strukturu pojedinačnih čvorova
Stablo - klasa 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 takav 'akrobatski' pristup (iako moramo priznati da u takvom pristupu ima neke lepote, ipak ćemo biti 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 - nije teško pretpostaviti - 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 č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 (što zapravo i jeste prava svrha stabala pretrage), navedena celobrojna vrednost bila bi ključ, a referencu na datu klasu bismo morali dodati među polja klase Cvor.

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 se moraju računati 'svaki čas' (tako što ćemo pristupati direktnim potomcima čvora, očitavati njihove visine i potom računati balans faktor č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 (a mi smo izabrali onaj koji ipak smatramo racionalnijim i koji i inače koristimo).

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" stabla). Takva promenljiva dobro će doći za isprobavanje u fazi učenja (a ne smeta ni inače).

Osnovni konstruktor prima kao argument vrednost korenog čvora, a predvideli smo i konstruktor bez parametara (za potrebe članka neće nam trebati, ali, možda čitaocima negde zatreba).

Klasa 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 osnovnu definiciju klase koji ste prethodno 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 je dovoljno tu vrednost samo uvećati za jedan, ali kao što se može videti ispod, metoda ima pet if grananja (umesto samo jednog if-a ili ternarnog operatora).

Moramo preduzeti dodatne korake, jer ne srećemo se u svim situacijama sa čvorovima koji imaju oba podstabla, a preko rekurzivnih poziva upućivaćemo metodu za ažuriranje i na čvorove koji uopšte ne postoje!

		
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, a u narednim člancima ćemo videti i kako i zašto), 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 smo naveli na početku - (preko ternarnog operatora) pronaći ćemo podstablo sa najvećom visinom, očitati visinu i datu vrednost uvećati za 1.

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 uklanjanju čvorova, podrazumeva se 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 čvor ima vrednost null, pre nego što pokušamo da mu pristupimo.

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

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, a 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 zadovoljstva 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.