Стр. 31 - Основы алгоритмов и структур данных

Содержание 29
ОСНОВЫ АЛГОРИТМОВ И СТРУКТУР ДАННЫХ
Строим дерево по эвристике 3.
1
3
5 2
2
Рис. 19. Дерево, построенное по эвристике 3
Время поиска:
9 1 4 1 3 2 39
1 3 2 4 3 3
20 20 20 20 20 20 20
⋅ + ⋅ + ⋅ + ⋅ + ⋅ + ⋅ =
.
Известно следующее: бинарные деревья, сбалансированные по сумме
весов, при больших n, никогда не далеки от оптимальных.
Для большинства таблиц из экспериментов известно следующее: эвристика
2, балансирующая деревья по сумме весов, всегда даёт дерево близкое к
оптимальному. Эвристикой 1 можно пользоваться, когда частоты обращения к
вершинам до построения неизвестны заранее, либо когда мало отличаются.
Эвристика 3 дает худшее быстродействие поиска, если вся таблица или ее
фрагменты оказываются упорядоченными по вероятности.
Если 1 2 3 4 5 β β β β β > > > >то, вместо бинарного, имеем последовательный
поиск (бинарное дерево вырождается в унарное или список).
2
1
3
4
…
Рис. 20. Дерево вырожденное в список