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