Kapitola 3.

Vyhľadávanie v binárnych stromoch

 
 
Binárne stromy sú abstraktné dátové štruktúry prispôsobené na vyhľadávanie. Každý uzol stromu môže mať najviac dvoch potomkov, na ktorých ukazujú jeho ukazovatele. Okrem toho ešte uchováva hodnotu prvku. V ľavom podstrome ľubovoľného uzla sa nachádzajú iba prvky menšie ako v uzle a v pravom podstrome sa nachádzajú iba prvky väčšie ako v uzle. Každý podstrom je potom samostatným binárnym stromom.
 
Výstupom týchto algoritmov býva zväčša ukazovateľ na uzol, ktorý obsahuje hľadanú hodnotu. V prípade, že sa v strome nenachádza hľadaná hodnota, je algoritmom vrátený nulový ukazovateľ. Výstupom môže byť aj logická premenná odpovedajúca úspešnosti vyhľadávania. Počet uzlov v strome budeme označovať písmenom n.

Zoznam stránok venujúcich sa stromom

Porovnanie algoritmov pre stromy

Triedy použité na analýzu a testovanie vybraných algoritmov

Ako môžeme vidieť, členskými premennými triedy sú počty porovnaní, cyklov (pre algoritmy využívajúce cyklus) a volaní (pre algoritmy využívajúce rekurziu). Toto budú hneď po čase trvania algoritmu najdôležitejšie ukazovatele jeho efektívnosti. 
 
//uzol pre binarne stromy
class CUzol {
	int hodnota_;	//hodnota uzla
	CUzol* lavy_;	//ukazovatel na laveho nasledovnika
	CUzol* pravy_;	//ukazovatel na praveho nasledovnika
public:
.
.
.
};

//binarny strom	
class CStrom{
	CUzol* koren_;	//ukazovatel na koren stromu
	//statisticke premenne
	int p_a_porovnani_;
	int p_b_porovnani_;
	int p_a_cyklov_;
	int p_a_volani_;
public:
.
.
.
};