170
правок
Изменения
Нет описания правки
'''Статус конспекта:'''НаписаноВ списке билетов была опечатка, что такое квадродерево, есть кое-какие оценки на глубину, размер, время построенияпоэтому возникла путаница во многих местах. Про перечисление точек в прямоугольнике написано, но я В этой статье оставляю просто всё полезное (и не увереночень) про квадродеревья, потому что хорошо (проблемы там описаны)нужно для скип-квадродерева.''
== Определение и построение ==
'''Квадродерево''' {{---}} дерево, каждая внутренняя вершина которого содержит 4 ребёнка. Любому узлу квадродерева соответствует некоторый квадрат. Если внутренней вершине <tex>v</tex> соответствует какой-то квадрат <tex>a</tex>, то её детям соответствуют четверти квадрата <tex>a</tex> (см. картинку).
[[Файл:Quadtree.png | 500px | thumb | По картинке должно быть понятно]]
Вообще говоря, квадродеревья могут быть использованы для разных целей и хранить разные данные, но нам они нужны для перечисления точек в произвольном прямоугольнике, соответственно, мы хранить в них будем какой-то набор точекна плоскости.
Пусть дано множество точек <tex>P</tex>, для которого нужно построить квадродерево. Начнём с некоторого квадрата <tex>\sigma</tex>, содержащего все точки из <tex>P</tex>. Если он не дан явно, его можно легко найти за линейное время от числа вершин. Пусть <tex>\sigma = [x_0, x_1] \times [y_0, y_1]</tex>. Обозначим <tex>x_m = (x_0 + x_1) / 2; y_m = (y_0 + y_1) / 2</tex>. Тогда:
== Перечисление точек в произвольном прямоугольнике ==
''В этом разделе написаны сомнительные вещи и вообще он не нужен, можно не читать.''
Пусть на вход подаётся некоторый прямоугольник <tex>M</tex>, для которого надо вернуть все точки из множества <tex>P</tex>, которые принадлежат этому прямоугольнику.
Короче, я не знаю, как это доказать, и мне кажется, что это не так. Если нам подали прямоугольник, содержащий все точки, то мы пройдём по всем вершинам, которых <tex>O(d \cdot n)</tex> (так написано в книжке, и лучшей оценки, видимо, нет). Возможно, я неправильно понимаю, что от нас хотят. Может быть, можно придумать какие-то оптимизации, ибо так совсем печальная оценка на запрос получается. Также могу предположить, что оценку времени можно улучшить, использовав функцию от размера ответа, но опять же не могу придумать/найти, как это сделать.
== Сбалансированное квадродерево ==
Квадродерево называется '''сбалансированным''', если для соответствующего ему разбиения плоскости на квадраты верно, что для любых двух соседних квадратов их стороны отличаются не более чем в два раза.
== Сжатое квадродерево ==
