ВУЗ:
Составители:
111
в симметричном порядке слева направо.
Теорема В. Для 2
k–1
≤ N < 2
k
успешный поиск по алгоритму В тре-
бует минимум одно и максимум k сравнений, а неудачный поиск при
2
k–1
≤ N < 2
k
– 1 требует (k – 1) или k сравнений. ■
Заметим, что никакой другой метод поиска, основанный на сравне-
нии ключей, не может превзойти этот результат. Среднее время работы
алгоритма В в предположении равновероятных исходов поиска составля-
ет приблизительно (18 lgN – 16) u для успешного и (18 lgN + 12) u для
неудачного поиска.
Упражнения
1. Постройте бинарное дерево (подобное изображённому на
рис. 38), которое соответствует бинарному поиску в упорядоченной таб-
лице из десяти записей с ключами: 61, 87, 154, 170, 275, 426, 503, 509, 512
и 612. Проследите за поиском по алгоритму B ключей 50, 61, 72, 87, 112,
154, 163, 170 и 275, отслеживая при этом соответствующие поиску пути в
бинарном дереве.
20. ПОИСК ПО БИНАРНОМУ ДЕРЕВУ
Из предыдущего параграфа видно, что неявная структура бинарного
дерева облегчает понимание бинарного поиска. Однако рассмотренный
там метод годится в основном для таблиц фиксированного размера, по-
скольку последовательное расположение записей делает вставку и удале-
ние записей весьма трудоёмкими. В случае когда таблица динамически
изменяется, можно потратить на её постоянное упорядочение куда боль-
ше времени, чем сэкономить на бинарном поиске.
Явное использование структуры бинарного дерева для хранения
таблицы позволяет быстро вставлять и удалять записи, а также эффек-
тивно выполнять поиск. Заметим, что при этом требуется два дополни-
тельных поля ссылок в каждой записи таблицы.
Технологии поиска в растущей таблице часто называют алгоритма-
ми таблиц символов, так как ассемблеры, компиляторы и другие систем-
ные программы обычно применяют их для хранения пользовательских
символов. Например, ключом записи в компиляторе может быть сим-
вольный идентификатор переменной в некоторой программе на языке
FORTRAN или C, а остальная часть записи может содержать информацию
о типе переменной и её адресе. Алгоритм поиска со вставкой по дереву,
который будет рассмотрен ниже, достаточно эффективен в качестве алго-
ритма таблиц символов, особенно в приложениях, в которых может ока-
заться нежелательным вывод списка символов в алфавитном порядке.
…
1
0
2
1
2
N
N
Страницы
- « первая
- ‹ предыдущая
- …
- 109
- 110
- 111
- 112
- 113
- …
- следующая ›
- последняя »
