Перечисление точек в произвольном прямоугольнике за n * log ^(d - 1) n (range tree) — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «{{notready}} Рассмотрим задачу хранения множества точек N-мерного пространства с возможность...»)
 
Строка 14: Строка 14:
  
 
Задача состоит в построении динамической структуры данных, хранящей точки пространства X и способной эффективно отвечать на запросы по перечислению множества точек, лежащих внутри прямоугольника запроса.
 
Задача состоит в построении динамической структуры данных, хранящей точки пространства X и способной эффективно отвечать на запросы по перечислению множества точек, лежащих внутри прямоугольника запроса.
 +
 +
== Одномерный случай ==
 +
 +
Для начала рассмотрим задачу в случае <math>N = 1</math>.
 +
 +
Заметим, что в этом случае точками пространства являются просто элементы некого линейного порядка.
 +
 +
Будем использовать сбалансированное бинарное дерево поиска, в листьях которого будем хранить точки искомого множества, а в нелистовых вершинах - разделющие значения, по которым будет вестись поиск в дереве.
 +
 +
Запрос задачи в одномерном случае превращается в перечисление множества значений, лежащих в отрезке запроса <math>[a, b]</math>.
 +
 +
Алгоритм, перечисляющий элементы дерева, входящие в отрезок запроса:
 +
 +
* Запустить обычный поиск в двоичном дереве элементов <math>a</math> и <math>b</math>, остановившись в последней общей вершине пути из корня; назовем эту вершину <math>v</math>.
 +
* Продолжить поиск элемента <math>a</math> из вершины <math>v</math>. При этом при каждом переходе к левому ребенку добавлять правое поддерево текущей вершины к ответу. Проверить последнюю вершину (лист) на вхождение в отрезок запроса и в случае необходимости добавить лист в ответ.
 +
* Аналогично, продолжить поиск элемента <math>b</math> из вершины <math>v</math>. При каждом переходе к правому ребенку добавлять левое поддерево к ответу. Аналогично проверить последнюю вершину в пути.
 +
 +
Здесь "добавить поддерево к ответу" означает пройти по поддереву целиком и каждый лист добавить к ответу.
 +
 +
Несложно понять, что описанный алгоритм действительно решает поставленную задачу за время <math>O(\log n + k)</math>, где <math>n</math> - количество элементов в дереве, <math>k</math> - размер ответа.

Версия 04:30, 16 января 2014

Конспект не готов.

Рассмотрим задачу хранения множества точек N-мерного пространства с возможностью перечисления точек, содержащихся в N-мерном прямоугольнике запроса. Эту задачу решает range-tree.

Постановка задачи

Пусть дано пространство [math]X[/math], являющееся произведением [math]N[/math] линейных порядков: [math]X = X_1 \times X_2 \times \hdots \times X_N[/math].

Отрезком в линейно упорядоченном множестве называется множество [math][a, b] = \{x | a \leq x \leq b\}[/math].

Прямоугольником в пространстве [math]X[/math] назовем произведение отрезков из [math]X_1 \hdots X_N[/math]: [math]I = [a_1, b_1] \times [a_2, b_2] \times \hdots \times [a_N, b_N][/math], где [math]a_i, b_i \in X_i[/math].

Задача состоит в построении динамической структуры данных, хранящей точки пространства X и способной эффективно отвечать на запросы по перечислению множества точек, лежащих внутри прямоугольника запроса.

Одномерный случай

Для начала рассмотрим задачу в случае [math]N = 1[/math].

Заметим, что в этом случае точками пространства являются просто элементы некого линейного порядка.

Будем использовать сбалансированное бинарное дерево поиска, в листьях которого будем хранить точки искомого множества, а в нелистовых вершинах - разделющие значения, по которым будет вестись поиск в дереве.

Запрос задачи в одномерном случае превращается в перечисление множества значений, лежащих в отрезке запроса [math][a, b][/math].

Алгоритм, перечисляющий элементы дерева, входящие в отрезок запроса:

  • Запустить обычный поиск в двоичном дереве элементов [math]a[/math] и [math]b[/math], остановившись в последней общей вершине пути из корня; назовем эту вершину [math]v[/math].
  • Продолжить поиск элемента [math]a[/math] из вершины [math]v[/math]. При этом при каждом переходе к левому ребенку добавлять правое поддерево текущей вершины к ответу. Проверить последнюю вершину (лист) на вхождение в отрезок запроса и в случае необходимости добавить лист в ответ.
  • Аналогично, продолжить поиск элемента [math]b[/math] из вершины [math]v[/math]. При каждом переходе к правому ребенку добавлять левое поддерево к ответу. Аналогично проверить последнюю вершину в пути.

Здесь "добавить поддерево к ответу" означает пройти по поддереву целиком и каждый лист добавить к ответу.

Несложно понять, что описанный алгоритм действительно решает поставленную задачу за время [math]O(\log n + k)[/math], где [math]n[/math] - количество элементов в дереве, [math]k[/math] - размер ответа.