58
ОСНОВЫ АЛГОРИТМОВ И СТРУКТУР ДАННЫХ
В нашем примере алфавит
D
={0,1,2,3,4,5,6,7,8,9} имеет 10 символов, т.е.
каждой вершине будет соответствовать ветвь из 10 элементов.
λ * * * λ λ λ λ λ λ
0 1 2 3 4 5 6 7 8 9
λ λ λ λ * λ
z
3
λ λ λ
λ λ λ
z
4
λ λ λ * λ λ
λ * λ λ
z
2
λ λ λ λ λ
14
z
6
18
z
5
z
1
4
корень
Рис. 62. Бор
Свойства боров.
1. Быстрый поиск, особенно в случае <
неуспеха
>.
2. Неэффективное использование памяти, особенно для вершин, далёких от
корня.
3. Для любого множества имён существует ровно одно дерево цифрового
поиска, а значит всего одна таблица – бор. Это исключает вопрос о построении
оптимального дерева поиска.
4. Алгоритмы поиска, включения, исключения просты.
Алгоритмы поиска / включения / исключения –написать самостоятельно!
Все методы последовательного и логарифмического поиска по сути
являются модификациями следующего общего алгоритма поиска:
сравниваем искомое имя
z
с некоторым ключом
x
i
из таблицы, если они
совпадают, то – успех, в противном случае
z
сравниваем с другим именем
x
j
и
т.д.
Очевидно, быстрее будут работать методы поиска, в которых по имени
z
будет некоторым образом вычисляться адрес, по которому
z
должно храниться
в таблице. Тогда остаётся один раз проверить, имеется
z
по этому адресу или
нет.
1...,50,51,52,53,54,55,56,57,58,59 61,62,63,64,65,66,67,68,69,70,...106