Algoritmy pre stromy

Vyhľadávanie zadanej hodnoty v strome

Popis
Ak chceme zahájiť vyhľadávanie v binárnom strome a zahrnúť do vyhľadávania všetky prvky stromu, musíme začať vyhľadávanie v koreni stromu. Prehľadávanie sa vykonáva pohybom v strome smerom k listom. Rozhodnutie o tom, v ktorej časti stromu bude vyhľadávanie pokračovať sa robí na základe hodnoty prvku v aktuálnom uzle a hodnote hľadaného prvku.

Vstupy algoritmu
Vstupom pre algoritmus musí byť strom alebo podstrom, v ktorom chceme vyhľadávať. Tento môže byť určený ukazovateľom na koreň stromu alebo podstromu. Ďalším vstupom je potom hľadaný prvok.

Princíp činnosti
Na začiatku je porovnaný hľadaný prvok s prvkom v aktuálnom uzle vstupného stromu. Ak sa tieto prvky rovnajú, algoritmus môžeme ukončiť. Ak je hľadaný prvok menší ako prvok v aktuálnom uzle, je zrejmé, že ak by sa hľadaný prvok v strome nachádzal, musí byť niekde v ľavom podstrome (medzi prvkami menšími ako v aktuálnom uzle). Preto za nasledujúci aktuálny uzol je vzatý ten, na ktorý ukazuje ukazovateľ na ľavý podstrom. Ak je hľadaný prvok väčší ako ten v aktuálnom uzle, pokračuje algoritmus vo vyhľadávaní v pravom podstrome. Za nasledujúci aktuálny uzol vezme uzol, na ktorý ukazuje ukazovateľ na pravý podstrom v momentálne aktuálnom uzle. Takto postupne prechádza stromom dovtedy, pokiaľ nenájde hľadaný prvok alebo aktuálny uzol už neobsahuje požadovaný ukazovateľ (požadovaný ukazovateľ je nulový).

Výstupy algoritmu
Ak sme našli hľadaný prvok, výstupom algoritmu môže byť logická premenná s hodnotou pravda alebo priamo ukazovateľ na uzol, v ktorom sa daný prvok nachádza. V prípade, že sa dostaneme pri prehľadávaní až k uzlom stromu, ktoré neobsahujú požadovaný ukazovateľ a hľadaný prvok sme nenašli, výstupom bude logická premenná s hodnotou nepravda alebo nulový ukazovateľ.

Vývojový diagram

Implementácia

 
//vyhladavanie zadanej hodnoty "hladany" v binarnom strome urcenom uzlom "uzol" pomocou cyklu while
//funkcia vracia ukazovatel na najdeny uzol (v pripade neuspechu vyhladavania vracia 0)
CUzol* najdi_cykl_uzol(CUzol* uzol, int hladany){
	while(uzol) {
		if (uzol->hodnota() > hladany) uzol=uzol->lavy();
		else if (uzol->hodnota() < hladany) uzol=uzol->pravy();
		else return uzol;
	}
	return 0;
}

Vizualizácie

Časová zložitosť
Pri vyhľadávaní ľubovoľného prvku urobíme najviac toľko krokov, akú hĺbku má vstupný strom. Ak je v binárnom vyhľadávacom strome n prvkov, potom hĺbka stromu je log(2) n. Pri priemernom úspešnom vyhľadávaní nájdeme hľadaný prvok podľa [4] na predposlednej úrovni a preto je počet porovnaní takéhoto vyhľadávania rádovo (log(2) n) – 1. Pri neúspešnom vyhľadávaní urobíme podľa [4] rádovo log(2) n porovnaní.