AVL Stablo - Implementacija - 2. deo - Pretraga

Uvod

U drugom nastavku serijala o implementaciji algoritma AVL bavićemo se pretragom stabla, odnosno, pronalaženjem određenog čvora preko pripisane celobrojne vrednosti.

Osnovna metoda koju ćemo pisati ima povratni tip int, a konkretne povratne vrednosti, biće:

celobrojna vrednost koja predstavlja 'dubinu' stabla na kojoj je tražena vrednost pronađena (to jest, broj koraka pretrage) - pod uslovom da je tražena vrednost pronađena
vrednost -1 - ako tražena vrednost nije pronađena u stablu

Takođe, budući da se stabla pretrage tipično koriste za pronalaženje obimnijih struktura sa više sadržaja (u takvom stablu, celobrojne vrednosti su samo ključevi za pretraživanje), prikazaćemo i implementaciju sa strukturom čvora koja je dopunjena klasom sa dodatnim podacima.

U navedenim okolnostima, funkcija (naravno) ne vraća celobrojnu vrednosti, već - referencu na pronađeni čvor (ili vrednost null, ako čvor nije pronađen).

Pretraga stabla - Osnovni princip

Podsetimo se na opšte smernice koje smo naveli u članku o binarnom stablu pretrage:

pretraga počinje od korenog čvora i praktično se usmerava prema potencijalnoj lokaciji traženog čvora
ukoliko čvor sa traženom vrednošću nije pronađen na mestu na kome se traži u određenom koraku (za početak u korenom čvoru), prelazi se u levo podstablo - ukoliko je tražena vrednost manja, ili desno podstablo - ukoliko je tražena vrednost veća - i potom se pretraga nastavlja po istom obrascu *

Na kraju pretrage (koja se obavlja po gore opisanoj proceduri), nastaje jedna od dve moguće situacije:

čvor sa traženom vrednošću uspešno je pronađen u najviše log(n) koraka
utvrđeno je da tražena vrednost ne postoji u stablu (takođe u najviše logn koraka)

Zarad temeljitosti, prikazaćemo ponovo postupak pretrage binarnog stabla, kroz dva primera (prvo ćemo tražiti element koji postoji u stablu, a zatim i element koji ne postoji u stablu).

Pretraga stabla u kome postoji traženi element

U prvom primeru, tražimo vrednost 17, koja postoji u sledećem stablu ....

AVL pretraga 01 — Slika 1. - Primer stabla koje će biti korišćeno u pretrazi.

Na samom početku, proverava se koreni čvor:

AVL pretraga 02 — Slika 2. - Pretraga vrednosti koja postoji u stablu - korak 1. - proverava korenog čvora.

Koreni čvor ne sadrži traženu vrednost, tražena vrednost (17), veća je od vrednosti korenog čvora (10), i stoga se iz pretrage može isključiti koreni čvor i celo levo podstablo korenog čvora ....

AVL pretraga 03 — Slika 3. - Pretraga vrednosti koja postoji u stablu - korak 2. - pošto je tražena vrednost veća, iz dalje pretrage može se isključiti koreni čvor i celo njegovo levo podstablo.

.... i potom se pretraga usmerava na desno podstablo (u kome se tražena vrednost nalazi - ili ne nalazi).

Vrednost korenog čvora desnog podstabla (15) ....

AVL pretraga 04 — Slika 4. - Pretraga vrednosti koja postoji u stablu - korak 3. - prelazak na koren desnog podstabla (i provera čvora #15).

.... manja je od 17, i stoga se iz dalje pretrage isključuje: i čvor #15, i levo podstablo čvora #15:

AVL pretraga 05 — Slika 5. - Pretraga vrednosti koja postoji u stablu - korak 4. - budući da je tražena vrednost veća, iz dalje pretrage isključuje se čvor #15 i njegovo levo podstablo.

Pretraga prelazi na koren desnog podstabla prethodno ispitivanog čvora ....

AVL pretraga 06 — Slika 6. - Pretraga vrednosti koja postoji u stablu - korak 5. - prelazak na čvor #22 (koren desnog podstabla čvora #15).

.... i budući da je ispitivana vrednost (22), veća od tražene, iz pretrage se isključuje čvor #22 i desno podstablo čvora #22 ....

AVL pretraga 07 — Slika 7. - Pretraga vrednosti koja postoji u stablu - korak 6. - budući da je tražena vrednost manja, iz dalje pretrage isključuje se čvor #22 i njegovo desno podstablo.

.... nakon čega se prelazi u levo podstablo.

Na kraju, u korenu levog podstabla čvora #22 ....

AVL pretraga 08 — Slika 8. - Pretraga vrednosti koja postoji u stablu - korak 7. - prelazak na čvor #17 (koren levog podstabla čvora #22).

.... pronađena je vrednost koju smo naveli kao kriterijum za pretragu:

AVL pretraga 09 — Slika 9. - Pretraga vrednosti koja postoji u stablu - korak 8 - Tražena vrednost je pronađena.

Tražena vrednost pronađena je iz četiri pokušaja (pri čemu je 4 - visina stabla).

Pogledajmo u nastavku šta se događa ukoliko pokušamo da pronađemo čvor koji ne može biti pronađen.

Pretraga stabla u kome ne postoji traženi element

U drugom primeru tražimo vrednost 25 - koja ne postoji u stablu, i ponovo se prvo proverava koreni čvor:

AVL pretraga 10 — Slika 10. - Pretraga vrednosti koja ne postoji u stablu - korak 1. - pretraga (ponovo) počinje od korenog čvora.

Budući da je tražena vrednost veća od 10, iz dalje pretrage se isključuje koreni čvor, kao i celo levo podstablo:

AVL pretraga 11 — Slika 11. - Pretraga vrednosti koja ne postoji u stablu - korak 2. - budući da je tražena vrednost veća, iz dalje pretrage isključuje se koreni čvor i njegovo levo podstablo.

Pretraga prelazi na vrh desnog podstabla korenog čvora:

AVL pretraga 12 — Slika 12. - Pretraga vrednosti koja ne postoji u stablu - korak 3. - prelazak na koren desnog podstabla (čvor #15).

Pošto se na vrhu desnog podstabla nalazi vrednost koja je manja od 25 (čvor #15), iz dalje pretrage se isključuje čvor #15 i njegovo levo podstablo (za sada je sve isto kao u prvoj pretrazi) ....

AVL pretraga 13 — Slika 13. - Pretraga vrednosti koja ne postoji u stablu - korak 4. - budući da je tražena vrednost veća, iz dalje pretrage isključuje se čvor #15 i njegovo levo podstablo.

Pretraga prelazi na desno podstablo ....

AVL pretraga 14 — Slika 14. - Pretraga vrednosti koja ne postoji u stablu - korak 5. - prelazak na čvor #22 (koreni čvor desnog podstabla čvora #15).

.... i budući da je ispitivana vrednost (22), manja od tražene vrednosti, odbacuje se levo podstablo čvora #22 (kao, naravno, i sam čvor #22).

AVL pretraga 15 — Slika 15. - Pretraga vrednosti koja ne postoji u stablu - korak 6. - budući da je tražena vrednost veća, iz dalje pretrage isključuje se čvor #22 i njegovo levo podstablo.

Sledi prelazak na koren desnog podstabla čvora #22 (čvor #24) ....

AVL pretraga 16 — Slika 16. - Pretraga vrednosti koja ne postoji u stablu - korak 7. - prelazak na čvor #24 (koreni čvor desnog podstabla čvora #22)

.... ali, na navedenoj poziciji takođe nije pronađena tražena vrednost ....

AVL pretraga 17 — Slika 17. - Pretraga vrednosti koja ne postoji u stablu - korak 8. - budući da tražena vrednost nije pronađena, iz dalje pretrage isključuje se čvor #24 i njegovo 'levo podstablo'.

Preostaje pokušaj prelaska na desno podstablo čvora #24 ....

AVL pretraga 18 — Slika 18. - Pretraga vrednosti koja ne postoji u stablu - korak 9. - Na slici vidimo da desno podstablo čvora #24 ne postoji, ali, računar "ne vidi sliku", i stoga mora pokušati da pristupi i desnom podstablu ("u potrazi za informacijama").

.... međutim, budući da na mestu desnog podstabla uopšte nije pronađen ikakav čvor ....

AVL pretraga 19 — Slika 19. - Pretraga vrednosti koja ne postoji u stablu - korak 10 - Pri pokušaju prelaska na desno podstablo čvora #24, računar nailazi na nepostojeći (null) čvor, čime je praktično - algoritamskim putem - ustanovljeno da vrednost 25 ne postoji u stablu.

.... može se zaključiti da čvor sa traženom vrednošću (25) - ne postoji u stablu.

Pretraga stabla - Implementacija

Pošto smo se podsetili na osnovne principe pretrage, prikazaćemo kako se mogu implementirati dve varijante funkcije za pretragu:

prvo ćemo se osvrnuti na osnovnu implementaciju sa 'običnim' celobrojnim čvorovima
nakon toga, prikazaćemo implementaciju koja koristi složenije čvorove kojima je pripisana klasa sa dodatnim podacima.

Osnovna pretraga

Metodu za pretragu pozivaćemo uz predavanje korenog čvora u svojstvu argumenta (naravno, predaje se i vrednost koju pretražujemo), a prelasci na leva i desna podstabla biće implementirani preko rekurzije.

Za "školsku" implementaciju u kojoj koristimo 'brojač koraka', biće potrebna i pomoćna metoda ProveraCvora - koja je zapravo radna metoda (koja rekurzivno sprovodi korake pretrage):

		
public int pretraga(int vrednost, Cvor c) {
	this.brojac = 0;
	return proveraCvora(vrednost, c);
}

public int proveraCvora(int vrednost, Cvor c) {
	// 1.
	if (c == null) {
		return -1;
	}

	// 2.
	this.brojac++;

	// 3.
	if (c.vrednost == vrednost) {
		return this.brojac;
	}

	// 4.
	if (vrednost < c.vrednost) {
		return proveraCvora(vrednost, c.levi);
	}

	// 5.
	if (vrednost > c.vrednost) {
		return proveraCvora(vrednost, c.desni);
	}

	return -1;
}

Slika 20. - Implementacija metode za pretragu.

Kao što vidimo, metoda Pretraga poziva radnu metodu ProveraCvora, uz prethodno resetovanje brojača, a vidimo i to da metoda za proveru čvorova doslovno sprovodi u delo principe koje smo definisali na početku:

prvi if proverava da li čvor koji je predat kao argument - uopšte postoji (ako metoda naiđe na nepostojeći čvor, može se zaključiti da pretraga nije dala rezultat, i stoga metoda treba da vrati vrednost -1)
u sledećem koraku, brojač se uvećava za 1 (i upravo je broj koraka pretrage, podatak koji osnovna verzija metode za pretragu potencijalno treba da vrati)
ako je vrednost pronađena (komentar #3), metoda vraća broj koraka u pronalaženju tražene vrednosti, a ako vrednost nije pronađena, preostaje neki od poslednja dva koraka (komentari #4 i #5):
- ako je tražena vrednost manja, pretraga se usmerava na levo podstablo
- ako je tražena vrednost veća, pretraga se usmerava na desno podstablo

Bez korišćenja dve metode (budući da koristimo rekurziju), ne bismo mogli realizovati resetovanje brojača pri svakom pozivu, na iole praktičan i elegantan način.

Pretraga polja baze podataka čiji su ključevi čvorovi AVL stabla

U drugom primeru (koji je, reklo bi se, konkretniji i praktičniji), koristićemo AVL stablo za pronalaženje slogova koji koriste čvorove AVL stabla kao ključeve.

Dodaćemo u program (privremeno, samo za ovaj primer), klasu Osoba ....

AVL čvorovi osoba 01 — Slika 21. - Struktura klase Osoba (klasa sadrži podatke koje ćemo pretraživati preko AVL stabla).

.... koju ćemo povezati sa klasom Cvor, posle čega će stablo imati sledeću strukturu ....

AVL čvorovi osoba 02 — Slika 22. - Struktura AVL stabla sa dopunjenim čvorovima.

Sada možemo zapisati klasu Osoba koja će sadržati (glavne) podatke koje skladištimo, i možemo (privremeno) dopuniti klasu Cvor:

		
public class Osoba {
	public int    id;
	public string ime,
	              prezime,
	              email;

	/*
	Konstruktor je izostavljen
	zarad preglednosti
	*/
}

public class Cvor {
	public int vrednost; // Primarni ključ (ID)
	public Cvor levi, desni;

	public int visina,
	           balansFaktor;

	public osoba osobaPodaci;

	/*
	I na ovom mestu je
	(zarad preglednosti)
	izostavljen konstruktor
	*/
}

Slika 23. - Implementacija klase Osoba i dopunjene klase Cvor.

Metoda za pretragu takođe će pretrpeti izmene.

Povratna vrednost biće:

referenca na objekat klase Osoba (čiji id će biti 'propušten' kroz AVL stablo kao kriterijum za pretragu) - ukoliko se pronađe osoba sa datim id-om
objekat sa sistemskom vrednošću null - ukoliko osoba sa traženim id-om nije pronađena

Budući da ovoga puta ne koristimo brojač koraka, sve se može realizovati preko (samo) jedne rekurzivne metode:

		
public Osoba pretraga(int id, Cvor c) {
	if (c == null) return null;

	if (c.Vrednost == id) {
		return c.osobaPodaci;
	}

	if (c.vrednost < id) {
		return pretraga(id, c.levi);
	}

	if (c.vrednost > id) {
		return pretraga(id, c.desni);
	}
}

Slika 24. - Implementacija metode Pretraga, koja pronalazi čvor koji je povezan sa int vrednošću iz AVL stabla (ili vraća vrednost null, ako element nije pronađen).

Kao što vidimo, pretraga čvorova koji 'nose' dodatne podatke, takođe sprovodi u delo principe koji su opisani u uvodnim poglavljima (po svojoj strukturi, poslednja funkcija koju smo videli je gotovo identična prvobitno prikazanoj funkciji za pretragu 'običnih' celobrojnih čvorova, ali, u praktičnom smislu - znatno je svrsishodnija).

Sledeći koraci ....

Verujemo da će stariji i iskusniji čitaoci, po želji (ili, još bolje, u skladu sa potrebama, nekog samostalnog projekta i sl. :)), biti u stanju da preprave i ostale metode koje ćemo implementirati, tako da budu prilagođene radu sa kompleksnijim čvorovima koji nose dodatne podatke, tj. objekte. *

Što se tiče budućih članaka, vratićemo se (zarad preglednosti), na pisanje jednostavnijih funkcija koje ne vraćaju pokazivače (već int vrednosti).

U sledećem nastavku obradićemo četiri metode za obilazak stabla

preko algoritma BFS
preko algoritma DFS - u tri varijante (preorder, inorder i postorder)

Do tada, za vežbu, probajte da implementirate metodu pretrage na iterativni način (bez rekurzije, uz upotrebu petlji).

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.