Перечисление точек в произвольном прямоугольнике за n * log ^(d - 1) n (range tree)
Конспект не готов. |
Рассмотрим задачу хранения множества точек N-мерного пространства с возможностью перечисления точек, содержащихся в N-мерном прямоугольнике запроса. Эту задачу решает range-tree.
Постановка задачи
Пусть дано пространство
, являющееся произведением линейных порядков: .Отрезком в линейно упорядоченном множестве называется множество
.Прямоугольником в пространстве
назовем произведение отрезков из : , где .Задача состоит в построении динамической структуры данных, хранящей точки пространства X и способной эффективно отвечать на запросы по перечислению множества точек, лежащих внутри прямоугольника запроса.
Одномерный случай
Для начала рассмотрим задачу в случае
.Заметим, что в этом случае точками пространства являются просто элементы некого линейного порядка.
Будем использовать сбалансированное бинарное дерево поиска, в листьях которого будем хранить точки искомого множества, а в нелистовых вершинах - разделющие значения, по которым будет вестись поиск в дереве.
Запрос задачи в одномерном случае превращается в перечисление множества значений, лежащих в отрезке запроса
.Алгоритм, перечисляющий элементы дерева, входящие в отрезок запроса:
- Запустить обычный поиск в двоичном дереве элементов и , остановившись в последней общей вершине пути из корня; назовем эту вершину .
- Продолжить поиск элемента из вершины . При этом при каждом переходе к левому ребенку добавлять правое поддерево текущей вершины к ответу. Проверить последнюю вершину (лист) на вхождение в отрезок запроса и в случае необходимости добавить лист в ответ.
- Аналогично, продолжить поиск элемента из вершины . При каждом переходе к правому ребенку добавлять левое поддерево к ответу. Аналогично проверить последнюю вершину в пути.
Здесь "добавить поддерево к ответу" означает пройти по поддереву целиком и каждый лист добавить к ответу.
Несложно понять, что описанный алгоритм действительно решает поставленную задачу за время
, где - количество элементов в дереве, - размер ответа.