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ženi ključ pronađen
vrednost -1 - ako traženi ključ nije pronađen u stablu

Takođe, budući da se stabla pretrage tipično koriste za pronalaženje obimnijih struktura sa više sadržaja - preko celobrojnih ključeva, 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 principi

Podsetićemo se prvo 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 čvor sa vrednošću 17 (pri čemu takav čvor 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.

U konkretnom primeru, 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 ključ 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 ključ za pretragu:

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

Traženi ključ pronađen je iz četiri pokušaja (pri čemu broj 4 predstavlja visinu stabla).

Pogledajmo u nastavku šta se događa pri pokušaju 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 čvor sa vrednošću 25 (ovoga puta takav čvor 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: *

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 će biti implementirani preko rekurzije.

Za "školsku" implementaciju sa 'brojačem 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 pomoćne metode (budući da koristimo rekurziju (na pomalo idiosinkratičan način)), 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, može se reći, konkretniji i praktičniji), koristićemo AVL stablo za pronalaženje slogova koji su povezani sa celobrojnim vrednostima čvorova.

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 dodati i kod za 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, pri čemu povratna vrednost (ponovo/očekivano) zavisi od toga da li je id osobe pronađen:

ukoliko se preko id-a pronađe osoba - povratna vrednost je referenca na objekat klase Osoba (čiji se id 'propušta' kroz AVL stablo kao kriterijum za pretragu)
ukoliko se ne pronađe traženi id - povratna vrednost je objekat sa sistemskom vrednošću null

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.

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, * međutim, š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.