Стр. 29 - Основы алгоритмов и структур данных
Упрощенная HTML-версия
27
ОСНОВЫ АЛГОРИТМОВ И СТРУКТУР ДАННЫХ
Для построения оптимального дерева можно воспользоваться методами
оптимизации и (или) методами исчерпывающего поиска с затратами времени
О(
2
n
)
÷
О(
3
n
), что не приемлемо для большинства практических задач. Поэтому
чаще пользуются так называемыми эвристическими алгоритмами,
позволяющими построить деревья достаточно близкими к оптимальному с
затратами О(
n
). Во всех эвристиках дерево изначально пустое.
4.3.4. Эвристики построений оптимальных деревьев
Эвристика 1
. К построенному дереву добавляем очередной узел так,
чтобы его левые или правые поддеревья имели максимально близкое
количество вершин, считая листья.
Эвристика 2
. К построенному дереву добавляем очередной узел так,
чтобы его левое и правое поддеревья имели максимально близкие суммы весов
(сумма вероятностей или сумма частот обращений).
Эвристика 3
. Помещаем наиболее часто используемые ключи ближе к
корню.
Пример
Есть таблица из 5 ключей со следующими вероятностями:
1
β
= 9/20,
2
β
= 1/20,
3
β
= 4/20,
4
β
= 1/20,
5
β
= 3/20.
4,0 0 α
= =
j
j
20/2 α
5
=
.
Простое, не оптимизированное дерево бинарного поиска (алгоритм 4).
3
4
2
5
1
Рис. 16. Не оптимизированное дерево бинарного поиска
