Ортогональный поиск — различия между версиями
Proshev (обсуждение | вклад) |
(→Сбалансированное дерево поиска) |
||
Строка 24: | Строка 24: | ||
Переходим к двумерному случаю. Пусть дано некоторое множество точек на плоскости. Нам необходимо ответить, какие именно из них лежат в некотором заданном прямоугольнике. | Переходим к двумерному случаю. Пусть дано некоторое множество точек на плоскости. Нам необходимо ответить, какие именно из них лежат в некотором заданном прямоугольнике. | ||
− | Для этого возьмем любое сбалансированное дерево поиска и | + | Для этого возьмем любое сбалансированное дерево поиска и наполним его точками <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>range{\_}search(y_{min}, y_{max})</tex>. Все полученные таким образом точки и будут составлять ответ. |
Теперь для ответа нам нужно спуститься отрезком по дереву и, если все поддерево лежит в отрезке, сразу выдавать его, если нет - спускаться дальше. | Теперь для ответа нам нужно спуститься отрезком по дереву и, если все поддерево лежит в отрезке, сразу выдавать его, если нет - спускаться дальше. |
Версия 16:35, 19 мая 2012
Содержание
Простейший случай
Пусть дана прямая с точками на ней и отрезок. Точки даны в отсортированном порядке. Необходимо указать, какие из изначальных точек лежат на этом отрезке.
Данная задача решается с помощью функций из STL - upper_bound и lower_bound.
upper_bound возвращает наименьшее значение больше данного, lower_bound - наибольшее значение меньше данного.
Рассмотрим на примере:
Код реализации:
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); }
Сбалансированное дерево поиска
Переходим к двумерному случаю. Пусть дано некоторое множество точек на плоскости. Нам необходимо ответить, какие именно из них лежат в некотором заданном прямоугольнике.
Для этого возьмем любое сбалансированное дерево поиска и наполним его точками
из множества. В качестве ключа будет использоваться -координата точки. Теперь слегка модернизируем дерево: в каждой вершине дерева будем хранить отсортированный по -координате массив точек, которые содержатся в соответствующем поддереве. В такой структуре данных поиск точек в заданном прямоугольнике будет выглядеть следующим образом:- Выберем из дерева поиска те точки, запрос сверху в дереве отрезков. Из аналогии с деревом отрезков следует, что мы ответ мы получим в виде поддеревьев дерева поиска. -координата которых лежит в интервале . Сделаем это точно так же, как делается
- Для каждого из полученных поддеревьев обратимся к массиву содержащихся в нем точек и запустим от него приведенную выше функцию . Все полученные таким образом точки и будут составлять ответ.
Теперь для ответа нам нужно спуститься отрезком по дереву и, если все поддерево лежит в отрезке, сразу выдавать его, если нет - спускаться дальше.