Стр. 26 - Основы алгоритмов и структур данных
Упрощенная HTML-версия
24
ОСНОВЫ АЛГОРИТМОВ И СТРУКТУР ДАННЫХ
5
2
8
1
3
9
6
4
7
11
1
2
3
4
5
Уровни дерева
неудача
Рис. 13. Дерево бинарного поиска
Худшее время поиска равно высоте дерева, т.е. log
2
n
.
В среднем случае для успешного поиска потребуется (1+1/
n
)log
2
(
n
+1)-1,
т.е. O(log
2
n
).
Время неуспешного поиска больше, чем время успешного.
Очевидно, на поиск каждого ключа требуется столько операций, каков
уровень соответствующей вершины. Чтобы произошла неудача, необходимо
столько сравнений, каков уровень соответствующего листа минус 1.
4.3.3. Оптимальные деревья бинарного поиска
Допустим, обращение к разным ключам происходит с разной частотой,
иногда поиск выполнялся бы быстрее, если бы тяжелые ключи (часто искомые)
удалось расположить ближе к корню. Заметим, в дереве бинарного поиска
определяющую роль играют отношения ключей по горизонтали, а не по
вертикали. Из этого следует, что при желании из тех же ключей можно
построить и другое дерево бинарного поиска.
Пусть таблица содержит следующие имена:
i
1
2
3
4
5
x
i
2
3
5
9
12
B
i
5
6
1
2
4
x
i
– имена
