Grafy a tabuľky

Vyhľadávanie zadanej hodnoty v strome

Priemerné počty porovnaní vybraných implementácií

 
//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* CStrom::najdi_cykl_uzol(CUzol* uzol, int hladany){
	while (++p_a_porovnani_ && uzol) {
		++p_a_cyklov_;		
		if (++p_b_porovnani_ && uzol->hodnota() > hladany) uzol=uzol->lavy();
		else if (++p_b_porovnani_ && uzol->hodnota() < hladany) uzol=uzol->pravy();
		else return uzol;
	}
	return 0;
}
Počet porovnaní, cyklov a času trvania algoritmu pre úspešné vyhľadávanie.
počet uzlov v strome p_a_porovnani_ p_b_porovnani_ p_a_cyklov_ čas
15 3,267 5,400 3,267 0,3805
127 6,055 9,583 6,055 0,6930
1.023 9,010 14,02 9,010 1,027
8.191 12,00 18,50 12,00 1,324
65.535 15,00 23,00 15,00 1,638
Pri hľadaní v cykle je najdôležitejším nameraným údajom počet cyklov algoritmu. Najmä od neho totiž závisí čas vyhľadávania. Počet cyklov je pri úspešnom vyhľadávaní v priemernom prípade rovný (log(2) n)-1.
 
Počet porovnaní, cyklov a času trvania algoritmu pre neúspešné vyhľadávanie s p=0,9.
počet uzlov v strome p_a_porovnani_ p_b_porovnani_ p_a_cyklov_ čas
15 4,933 6,067 4,000 0,4159
127 7,795 10,22 6,882 0,7084
1.023 10,82 14,85 9,910 1,037
8.191 13,82 19,40 12,91 1,345
65.535 16,87 23,89 15,91 1,664
Počet cyklov je pri zväčša neúspešnom vyhľadávaní v priemernom prípade rovný (log(2) n). Toto číslo totiž vyjadruje priemernú hĺbku stromu.
 
 
//vyhladavanie zadanej hodnoty "hladany" v binarnom strome urcenom uzlom "uzol" pomocou rekurziou
//funkcia vracia ukazovatel na najdeny uzol (v pripade neuspechu vyhladavania vracia 0)  
CUzol* CStrom::najdi_rek_uzol(CUzol* uzol, int hladany){
	++p_a_volani_;
	if (++p_a_porovnani_ && !uzol) return 0;
	else if (++p_b_porovnani_ && uzol->hodnota() > hladany) 
		return najdi_rek_uzol(uzol->lavy(), hladany);
	else if (++p_b_porovnani_ && uzol->hodnota() < hladany) 
		return najdi_rek_uzol(uzol->pravy(), hladany);
	else return uzol;
}
Počet porovnaní, cyklov a času trvania algoritmu pre úspešné vyhľadávanie.
počet uzlov v strome p_a_porovnani_ p_b_porovnani_ p_a_volani_ čas
15 3,267 5,400 3,267 0,4573
127 6,055 9,583 6,055 0,8597
1.023 9,010 14,02 9,010 1,301
8.191 12,00 18,50 12,00 1,732
65.535 15,00 23,00 15,00 2,190
Pri každom volaní sa delí vyhľadávací problém na polovičný. Počet volaní je preto pri úspešnom vyhľadávaní približne rovný (log(2) n)-1. -1 je na konci z toho dôvodu, že vyhľadávanie v priemernom prípade skončí na predposlednej úrovni v strome.
 
Počet porovnaní, cyklov a času trvania algoritmu pre neúspešné vyhľadávanie s p=0,9.
počet uzlov v strome p_a_porovnani_ p_b_porovnani_ p_a_volani_ čas
15 4,933 6,067 4,933 0,5588
127 7,795 10,22 7,795 0,9370
1.023 10,82 14,85 10,82 1,380
8.191 13,82 19,40 13,82 1,811
65.535 16,87 23,89 16,87 2,279
Počet volaní je pri neúspešnom vyhľadávaní približne rovný (log(2) n). Je to preto, lebo aby algoritmus s určitosťou došiel k záveru, že hľadaná hodnota sa v strome nenachádza, musí sa dostať až na najnižšiu úroveň (do najväčšej hĺbky) v strome.
 
 

Závislost dĺžky času trvania algoritmu od veľkosti vstupného pola
Pre oba typy algoritmu, vyhľadávanie pomocou cyklu a aj rekurzie platí, že čas vykonávania algoritmu závisí od veľkosti stromu logaritmicky. Vyhľadávanie v strome s veľkosťou 65.535 uzlov trvá len približne 2ms.
  15 127 1.023 8.191 65.535
úspešné vyhľadávanie rekurziou 0,4570 0,8600 1,301 1,732 2,190
neúspešné vyhľadávanie s p=0,9 rekurziou 0,5590 0,9370 1,380 1,811 2,279
úspešné vyhľadávanie cyklom 0,3810 0,6930 1,027 1,324 1,638
neúspešné vyhľadávanie s p=0,9 cyklom 0,4160 0,7080 1,037 1,346 1,664
 
 
Poznámka: Algoritmy boli testované na počítači s procesorom AMD Athlon(tm) XP 1700+ a s 256 MB operačnou pamäťou pod operačným systémom Windows XP. Všetky časy uvedené v tabuľke sú v mikrosekundách.