Стр. 27 - Основы алгоритмов и структур данных
Упрощенная HTML-версия
25
ОСНОВЫ АЛГОРИТМОВ И СТРУКТУР ДАННЫХ
B
i
– частоты обращения к именам
Построим обычное дерево бинарного поиска (заменим
z
:
x
i
на
i
).
3
1
4
2
5
Рис. 14. Дерево бинарного поиска
Определим среднее число операций при успешном поиске.
∑ ∑
∑
=
=
+=
=
n
i
i
n
i
i i
i
CP S
1
1
1)-
вершины
уровень
(
β
β
1
18
27 12*
18
4 1*
18
2 0*
18
1 2*
18
6 1*
18
5 1
+=
+ +
+
+ +=
S
Построим по этой же таблице другое дерево бинарного поиска:
2
5
4
1
3
Рис. 15. Дерево бинарного поиска
18
16 11*
18
4 2*
18
2 3*
18
1 0*
18
6 1*
18
5 1
opt
+= +
+ +
+ +=
S
