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

58 Содержание
ОСНОВЫ АЛГОРИТМОВ И СТРУКТУР ДАННЫХ
В нашем примере алфавит D={0,1,2,3,4,5,6,7,8,9} имеет 10 символов, т.е.
каждой вершине будет соответствовать ветвь из 10 элементов.
λ * * * λ λ λ λ λ λ
0 1 2 3 4 5 6 7 8 9
λ λ λ λ * λ z3 λ λ λ
λ λ λ z4 λ λ λ * λ λ
λ * λ λ z2 λ λ λ λ λ
14
z6
18
z5
z1 4
корень
Рис. 62. Бор
Свойства боров.
1. Быстрый поиск, особенно в случае <неуспеха>.
2. Неэффективное использование памяти, особенно для вершин, далёких от
корня.
3. Для любого множества имён существует ровно одно дерево цифрового
поиска, а значит всего одна таблица – бор. Это исключает вопрос о построении
оптимального дерева поиска.
4. Алгоритмы поиска, включения, исключения просты.
Алгоритмы поиска / включения / исключения –написать самостоятельно!
Все методы последовательного и логарифмического поиска по сути
являются модификациями следующего общего алгоритма поиска:
сравниваем искомое имя z с некоторым ключом xi из таблицы, если они
совпадают, то – успех, в противном случае z сравниваем с другим именем xj и
т.д.
Очевидно, быстрее будут работать методы поиска, в которых по имени z
будет некоторым образом вычисляться адрес, по которому z должно храниться
в таблице. Тогда остаётся один раз проверить, имеется z по этому адресу или
нет.