Ортогональный поиск — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (Сбалансированное дерево поиска)
Строка 27: Строка 27:
  
 
Для этого возьмем любое сбалансированное дерево поиска и наполним его точками <tex>(x, y)</tex> из множества. В качестве ключа будет использоваться <tex>x</tex>-координата точки. Теперь модернизируем дерево: в каждой вершине дерева будем хранить отсортированный по <tex>y</tex>-координате массив точек, которые содержатся в соответствующем поддереве. В такой структуре данных поиск точек в заданном прямоугольнике <tex>(x_{min}, x_{max}) \times (y_{min}, y_{max})</tex> будет выглядеть следующим образом:
 
Для этого возьмем любое сбалансированное дерево поиска и наполним его точками <tex>(x, y)</tex> из множества. В качестве ключа будет использоваться <tex>x</tex>-координата точки. Теперь модернизируем дерево: в каждой вершине дерева будем хранить отсортированный по <tex>y</tex>-координате массив точек, которые содержатся в соответствующем поддереве. В такой структуре данных поиск точек в заданном прямоугольнике <tex>(x_{min}, x_{max}) \times (y_{min}, y_{max})</tex> будет выглядеть следующим образом:
# Выберем из дерева поиска те точки, <tex>x</tex>-координата которых лежит в интервале <tex>(x_{min}, x_{max})</tex>. Сделаем это точно так же, как делается [[Реализация запроса в дереве отрезков сверху|запрос сверху в дереве отрезков]]. Из аналогии с деревом отрезков следует, что мы ответ мы получим в виде <tex>O(\log n)</tex> поддеревьев дерева поиска.
+
# Выберем из дерева поиска те точки, <tex>x</tex>-координата которых лежит в интервале <tex>(x_{min}, x_{max})</tex>. Сделаем это точно так же, как делается [[Реализация запроса в дереве отрезков сверху|запрос сверху в дереве отрезков]]. Из аналогии с деревом отрезков следует, что ответ мы получим в виде <tex>O(\log n)</tex> поддеревьев дерева поиска.
 
# Для каждого из полученных поддеревьев обратимся к массиву содержащихся в нем точек и запустим от него приведенную выше функцию <tex>range{\_}search(y_{min}, y_{max})</tex>. Все полученные таким образом точки и будут составлять ответ.
 
# Для каждого из полученных поддеревьев обратимся к массиву содержащихся в нем точек и запустим от него приведенную выше функцию <tex>range{\_}search(y_{min}, y_{max})</tex>. Все полученные таким образом точки и будут составлять ответ.
 
{{TODO| t=запилить красивую и понятную картинку}}
 
{{TODO| t=запилить красивую и понятную картинку}}
  
Каждая из функций <tex>range{\_}search(y_{min}, y_{max})</tex> будет работать в худшем случае за <tex>O(\log n)</tex>, отсюда получаем итоговое время выполнения запроса <tex>O(\log^2 n)</tex>. Что касается памяти, то в сбалансированном дереве поиска <tex>O(\log n)</tex> слоев, а каждый слой содержит массивы, содержащие в сумме ровно <tex>n</tex> точек, соответственно вся структура в целом занимает <tex>O(n\log n)</tex> памяти.
+
Каждая из функций <tex>range{\_}search(y_{min}, y_{max})</tex> будет работать в худшем случае за <tex>O(\log n)</tex>, отсюда получаем итоговое время выполнения запроса <tex>O(\log^2 n)</tex>. Что касается памяти, то в сбалансированном дереве поиска <tex>O(\log n)</tex> слоев, а каждый слой хранит массивы, содержащие в сумме ровно <tex>n</tex> точек, соответственно вся структура в целом занимает <tex>O(n\log n)</tex> памяти.
  
 
Такую структуру данных можно при необходимости обобщить на случай большей размерности. Пусть у нас есть множество точек из <tex>p</tex>-мерного пространства, каждая из которых представляется как <tex>n</tex> координатных чисел: <tex>(\xi_1, \xi_2, ... , \xi_p)</tex>. Тогда, строя дерево поиска по координате <tex>\xi_i</tex>, в каждой вершине будем хранить другое дерево поиска с ключом <tex>\xi_{i+1}</tex>, составленное из точек, лежащих в соответствующем поддереве. В дереве поиска, составленном по предпоследней координате <tex>\xi_{p-1}</tex>, уже не будет необходимости хранить в каждой вершине целое дерево, поскольку при переходе на последнюю координату <tex>\xi_{p}</tex> дальнейший поиск производиться не будет, поэтому в вершинах будем хранить массивы, так же, как и в двумерном случае. Оценим занимаемую память и время запроса: при добавлении следующей координаты асимптотика обеих величин умножается на  <tex>\log n</tex>. Отсюда, получаем оценку <tex>O(\log^{p} n)</tex> на время запроса и <tex>O(n\log^{p-1} n)</tex> на занимаемую память.
 
Такую структуру данных можно при необходимости обобщить на случай большей размерности. Пусть у нас есть множество точек из <tex>p</tex>-мерного пространства, каждая из которых представляется как <tex>n</tex> координатных чисел: <tex>(\xi_1, \xi_2, ... , \xi_p)</tex>. Тогда, строя дерево поиска по координате <tex>\xi_i</tex>, в каждой вершине будем хранить другое дерево поиска с ключом <tex>\xi_{i+1}</tex>, составленное из точек, лежащих в соответствующем поддереве. В дереве поиска, составленном по предпоследней координате <tex>\xi_{p-1}</tex>, уже не будет необходимости хранить в каждой вершине целое дерево, поскольку при переходе на последнюю координату <tex>\xi_{p}</tex> дальнейший поиск производиться не будет, поэтому в вершинах будем хранить массивы, так же, как и в двумерном случае. Оценим занимаемую память и время запроса: при добавлении следующей координаты асимптотика обеих величин умножается на  <tex>\log n</tex>. Отсюда, получаем оценку <tex>O(\log^{p} n)</tex> на время запроса и <tex>O(n\log^{p-1} n)</tex> на занимаемую память.

Версия 16:56, 23 мая 2012

Эта статья находится в разработке!

Простейший случай

Пусть дана прямая с точками на ней и отрезок. Точки даны в отсортированном порядке. Необходимо указать, какие из изначальных точек лежат на этом отрезке.

Line with dots and segment.png

Данная задача решается с помощью функций из STL - upper_bound и lower_bound.

lower_bound возвращает итератор на первый элемент, больший либо равный данного.
upper_bound возвращает итератор на первый элемент множества со значением, большим данного.

Рассмотрим на примере:

Upper bound and lower bound1.png

Код реализации:

template<class RauIter, class OutIter, class Scalar> OutIter range_search(RauIter p, RauIter q, OutIter out)
{
   return std::copy(lower_bound(p, q, l), upper_bound(p, q, r), out);
}

Сбалансированное дерево поиска

Переходим к двумерному случаю. Пусть дано некоторое множество точек на плоскости. Нам необходимо ответить, какие именно из них лежат в некотором заданном прямоугольнике.

Для этого возьмем любое сбалансированное дерево поиска и наполним его точками [math](x, y)[/math] из множества. В качестве ключа будет использоваться [math]x[/math]-координата точки. Теперь модернизируем дерево: в каждой вершине дерева будем хранить отсортированный по [math]y[/math]-координате массив точек, которые содержатся в соответствующем поддереве. В такой структуре данных поиск точек в заданном прямоугольнике [math](x_{min}, x_{max}) \times (y_{min}, y_{max})[/math] будет выглядеть следующим образом:

  1. Выберем из дерева поиска те точки, [math]x[/math]-координата которых лежит в интервале [math](x_{min}, x_{max})[/math]. Сделаем это точно так же, как делается запрос сверху в дереве отрезков. Из аналогии с деревом отрезков следует, что ответ мы получим в виде [math]O(\log n)[/math] поддеревьев дерева поиска.
  2. Для каждого из полученных поддеревьев обратимся к массиву содержащихся в нем точек и запустим от него приведенную выше функцию [math]range{\_}search(y_{min}, y_{max})[/math]. Все полученные таким образом точки и будут составлять ответ.

TODO: запилить красивую и понятную картинку

Каждая из функций [math]range{\_}search(y_{min}, y_{max})[/math] будет работать в худшем случае за [math]O(\log n)[/math], отсюда получаем итоговое время выполнения запроса [math]O(\log^2 n)[/math]. Что касается памяти, то в сбалансированном дереве поиска [math]O(\log n)[/math] слоев, а каждый слой хранит массивы, содержащие в сумме ровно [math]n[/math] точек, соответственно вся структура в целом занимает [math]O(n\log n)[/math] памяти.

Такую структуру данных можно при необходимости обобщить на случай большей размерности. Пусть у нас есть множество точек из [math]p[/math]-мерного пространства, каждая из которых представляется как [math]n[/math] координатных чисел: [math](\xi_1, \xi_2, ... , \xi_p)[/math]. Тогда, строя дерево поиска по координате [math]\xi_i[/math], в каждой вершине будем хранить другое дерево поиска с ключом [math]\xi_{i+1}[/math], составленное из точек, лежащих в соответствующем поддереве. В дереве поиска, составленном по предпоследней координате [math]\xi_{p-1}[/math], уже не будет необходимости хранить в каждой вершине целое дерево, поскольку при переходе на последнюю координату [math]\xi_{p}[/math] дальнейший поиск производиться не будет, поэтому в вершинах будем хранить массивы, так же, как и в двумерном случае. Оценим занимаемую память и время запроса: при добавлении следующей координаты асимптотика обеих величин умножается на [math]\log n[/math]. Отсюда, получаем оценку [math]O(\log^{p} n)[/math] на время запроса и [math]O(n\log^{p-1} n)[/math] на занимаемую память.

Такой же результат можно получить с помощью сжатого многомерного дерева отрезков.

Прошитые отсортированные массивы

Для ускорения запроса можно "прошить" дерево поиска, а именно: каждый элемент массива, сохраненного в какой-либо вершине, соединить с элементами массивов, сохраненных в вершинах-детях. Соединять будем по следующему принципу: элемент [math](x, y)[/math] массива-предка соединим с элементами [math]upper\_bound(y)[/math] и [math]lower\_bound(y)[/math] каждого массива-ребенка. Тогда для выполнения завершающей фазы поиска нам достаточно будет посчитать [math]upper\_bound()[/math] и [math]lower\_bound()[/math] только на массиве, привязанному к корню дерева. Для получения границ на других массивах можно будет просто спуститься по ссылкам от массива-предка за [math]O(1)[/math]. Таким образом, поиск теперь будет выполняться за [math]O(\log^{p-1} n)[/math], где [math]p[/math] — размерность пространства.

TODO: здесь тоже надо что-нибудь нарисовать

Квадро дерево

Инкрементальное квадро дерево