Полная версия

Главная arrow Информатика arrow ИНТЕЛЛЕКТУАЛЬНЫЕ СИСТЕМЫ. ТЕОРИЯ ХРАНЕНИЯ И ПОИСКА ИНФОРМАЦИИ

  • Увеличить шрифт
  • Уменьшить шрифт


<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>

Бинарный поиск.

Теорема 18. Если I = (X,V,pnear 1) — первая задача о близости, Т — (0, Gi) — базовое множество, определяемое соотношениями (2.1), (2.3), то

Доказательство. Пусть V = {г/ь • • • > Ук}, причем записи упорядочены в порядке возрастания.

Построим ИГ D2(V), имеющий вид дерева, по аналогии с первым деревом бинарного поиска следующим образом.

Возьмем бинарное сбалансированное дерево с к концевыми вершинами, высоты ]log2 к[, все ребра которого ориентированы от корня к концевым вершинам.

Объявим все концевые вершины этого дерева листьями и сопоставим им слева направо в порядке возрастания элементы из V. Напомним, что говоря о дереве, мы подразумеваем некоторую его укладку, и направления “влево”, “вправо” определяются уже на этой укладке.

Для произвольной внутренней вершины 0 дерева D2(V) введем понятия Vp и ур, определяемые так же, как и в дереве Dl(V).

Объявим все внутренние вершины дерева D2(V) вершинами переключения и для каждой внутренней вершины 0 левому ребру, из нее выходящему, припишем 1, а правому — 2, а самой вершине припишем переключатель 9<,Ув(х).

ИГ D2(V) полностью определен.

Если обозначить через а, лист, которому приписана запись у», то по построению D2(V) легко видеть, что

Отсюда сразу следует, что ИГ D2(V) разрешает первую задачу О близости I = (X, V, Pnearl)-

Поскольку D2(V) есть дерево, в котором полустепень исхода любой вершины равна 2, то

Поскольку для любого запроса хX в дереве D2(V) только одна активная цепь, а длина любой цепи в D2(V) не превышает ]log2 к[, то для любого запроса хX

Откуда сразу следует, что

Нижняя оценка для Т(/, Т, 2к - 2) следует из второй леммы о сведении (лемма 11) и теоремы 9.

Тем самым теорема доказана.

 
<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>