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

Содержание 51
ОСНОВЫ АЛГОРИТМОВ И СТРУКТУР ДАННЫХ
8
20
16 12 11
30
18
15 10
35 25 40
Рис. 52. Пример DB-дерева с ссылками на брата
Алгоритмы с DB-деревьями являются частными случаями алгоритмов с B-
деревьями.
4.7. Двумерный поиск
В задаче многомерного поиска каждый ключ Р есть вектор из двух или
более компонент: Р=(р1 ,…,рn ).
В общем случае задача многомерного поиска решается путём синтеза из k
компонент одной единственной компоненты и далее решается задача
одномерного поиска.
Рассмотрим задачу двумерного поиска: каждый ключ состоит из двух
компонент x и y, р=(х,у). Для двумерного поиска возможны специальные
решения. Для такой задачи можно использовать бинарные деревья, так как они
являются двумерными структурами, поскольку каждая вершина имеет 2
координаты: по высоте и ширине.
Вначале рассмотрим варианты использования бинарных деревьев в
одномерных задачах.
1-й случай.
Деревья бинарного поиска.
Такое дерево удовлетворяет следующим условиям (управляется
следующими инвариантами): пусть р - вершина, р.х – соответствующий ключ,
р.l – левый сын, р.r – правый сын вершины р.
Если λ . ≠ lp (есть левый сын), то р.l.x < p.x .
Если λ . ≠ rp (есть правый сын), то p.r.x > p.x.