Стр. 58 - Основы алгоритмов и структур данных
Упрощенная HTML-версия
56
ОСНОВЫ АЛГОРИТМОВ И СТРУКТУР ДАННЫХ
4.8. Цифровой поиск (лексикографический поиск)
Лексикография – разбор ключей по символам.
Цифровой поиск основан на посимвольном слева направо рассмотрении
каждого ключа
x
.
Пример.
Пусть в таблице содержится следующий набор ключей:
х
1 – 1414,
х
2 – 144,
х
3 – 16,
х
4 – 23,
х
5 – 2718,
х
6 – 314.
Объединим эти последовательности в дерево: корень дерева соответствует
началу ключа, а дуги – символам.
1
2
3
4
6
x
3
3
7
1
х
7
x
4
1
4
1 4
x
2
4
8
x
6
x
1
x
5
Рис. 59. Дерево
В дереве цифрового поиска последовательность символов каждого ключа
получается при прохождении пути от корня дерева до некоторого места. При
включении нового ключа, по возможности от корня, используются имеющиеся
дуги.
Поиск в таком дереве ключа
z
=
d
1
d
2
…
d
n
начинается в корне и продолжается
сравниванием самого левого ещё не сравниваемого символа
d
j
с метками всех
ветвей, исходящих из текущего узла. Если
d
j
совпадает с меткой некоторой
ветви, то мы следуем по этой ветви к следующему узлу. Если ни одна ветка не
совпадает с
d
j
, то поиск заканчивается безуспешно. Если все символы
d
j
j
=1,…,
n
найдены, то поиск завершён успешно.
