Strukture podataka i algoritmi: Stabla pretrazivanja

Strukture podataka i algoritmi

8 Pretrazivanje, jos jednom

Pre nego sto proucimo jos neke tehnike pretrazivanja, potrebno je da razmotrimo operacije na stablima - a posebno, nacine obilaska stabla.

8.1 Obilazak stabla

Binarno stablo se moze obici na nekoliko nacina:

pre-order	Obradi (poseti) koren Prodji kroz levo podstablo, Prodji kroz desno podstablo
in-order	Prodji kroz levo podstablo, Obradi koren Prodji kroz desno podstablo
post-order	Prodji kroz levo podstablo, Prodji kroz desno podstablo Obradi koren

Ako standardno uredjeno binarno stablo obidjemo pomocu in-order procedure, tada cemo proci kroz sve cvorove u sortiranom poretku.

Stabla rasclanjavanja izraza

Ako predstavimo izraz:

A*(((B+C)*(D*E))+F)

kao stablo:

tada ce njegov post-order obilazak dati: A B C + D E * * F + * sto je poznata reverzna poljska notacija koju koriste kompajleri za izracunavanje izraza.

Stabla pretrazivanja

Videli smo kako se gomile mogu koristiti da bi se odrzavalo balansirano stablo kod prioritetnih redova (i time sve operacije imale slozenost O(logn)). A sta ako bismo stablo hteli da koristimo za smestanje informacija koje treba samo koristiti, ali ne i brisati? Zelimo da budemo u mogucnosti da svaki objekat brzo pronadjemo u takvom stablu na osnovu njegovog kljuca. Procedura za pretrazivanje u binarnom stablu:

tree_search(tree T, Key key) {
    if (T == NULL) return NULL;
    if (key == T->root) return T->root;
    else
        if (key < T->root) return tree_search( T->left, key );
        else               return tree_search( T->right, key );
    }

je jednostavna i daje O(log n) pretrazivanje sve dok je stablo balansirano. Medjutim, dodavanjem objekata u stablo lako mozemo doci do nebalansiranog stabla!

Ovo se desava ako
dodajemo slova

A B C D E F

ovim redom u stablo:

Nije bas dobro balansirano!

Kljucni pojmovi

Pre-order obilazak stabla: Obilazenje stabla na nacin: koren | levo podstablo | desno podstablo
In-order obilazak stabla: Obilazenje stabla na nacin: levo podstablo | koren | desno podstablo
Post-order obilazak stabla: Obilazenje stabla na nacin: levo podstablo | desno podstablo | koren