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

Содержание 57
ОСНОВЫ АЛГОРИТМОВ И СТРУКТУР ДАННЫХ
В практических примерах часто одно имя zk может быть префиксом
другого имени zl, например, 314 и 314192. Тогда дерево содержит цепочку дуг:
._3_._1_._4_._1_._9_._2_. Пометим дуги, которым может соответствовать конец
имени, звёздочкой (*). ._3_._1_._4*_._1_._9_._2*_. Теперь при поиске имени
z=314 приводит к < успех>, а при имени z=31419 приводит к <неуспех >.
Вместо подстановки звёздочек, иногда дополняют имена таким образом,
чтобы ни одно имя не было префиксом другого. Например, добавляют в конце
имени нетерминальный символ (который не может быть ни в одном ключе).
Пусть “_” не встречается в ключах. При добавлении нового ключа в дерево
будем дописывать к нему “_” и тогда ключам будут соответствовать только
листовые страницы.
1 3
2
x7 _ 4 6 3 7 1
1 4 _ _ 1 4
x3 x 4 8 _
4 _ x6
_ x2 _
x1 x5
Рис. 60. Дерево
Рассмотрим вопрос о быстродействии метода цифрового поиска. Если
сравнение каждого очередного символа dj осуществляется путём
последовательного просмотра всех дуг, исходящих из текущего узла, то такой
метод будет медленнее, чем метод последовательного перебора, в котором на
каждом шаге сравниваются два имени zk и zl целиком. Рассмотрим способ,
позволяющий выбрать для dj соответствующую дугу за одну элементарную
операцию, которая может быть выполнена за время, не зависящее от числа
исходящих дуг.
Поставим в соответствие каждому узлу дерева вектор с компонентами для
каждой буквы алфавита } ,..., , {2 1 n d dd D = . Заметим, что в любом имени zi могут
быть использованы далеко не все буквы алфавита D. Очередной символ dj из
имени zi используется для определения индекса соответствующей компоненты
этого вектора. Сама компонента указывает на следующий узел дерева.
Представленное таким образом дерево называется бором (от слова выборка).
Построим бор для дерева, изображённого на рис 61.
Неуспех, как и раньше, будем обозначать λ.
Кроме того, поддеревья, не имеющие ветвлений, будем обозначать
эллипсом с вписанными в него индексами дуг.