419
правок
Изменения
м
→Сбалансированное дерево поиска
Для этого возьмем любое сбалансированное дерево поиска и наполним его точками <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>. Все полученные таким образом точки и будут составлять ответ.
{{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>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> на занимаемую память.
