1632
правки
Изменения
м
Дальше идут related вещи просто.
Короче, всё написано, только в одном месте сомнения.
''Видимо, в этом месте заканчивается всё то, что относится к данному билету, далее идут просто полезные факты (сбалансированное упомянуто просто так, а сжатое нужно для первого билета)''
Тут можно ещё чтоОни нужны для каких-то написатьтам задач, но вроде это нам не нужнонужны, поэтому оставлю только определениеничего писать не буду.
rollbackEdits.php mass rollback
'''Статус конспекта:'''НаписаноВ списке билетов была опечатка, что такое квадродерево, есть кое-какие оценки на глубину, размер, время построенияпоэтому возникла путаница во многих местах. Про перечисление точек в прямоугольнике написано, но я В этой статье оставляю просто всё полезное (и не увереночень) про квадродеревья, потому что хорошо (проблемы там описаны)нужно для скип-квадродерева.''
== Определение и построение ==
'''Квадродерево''' {{---}} дерево, каждая внутренняя вершина которого содержит 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>. Тогда:
{{Лемма
|statement=
Глубина квадродерева для множества точек <tex>P</tex> не превосходит <tex>\log_2(s / c) + 31/2</tex>, где <tex>c</tex> {{---}} наименьшее расстояние между двумя точками из <tex>P</tex>, а <tex>s</tex> {{---}} сторона квадрата, с которого начинается построение квадродерева.
|proof=
Сторона квадрата на глубине <tex>i</tex>, очевидно, равна <tex>s / 2^i</tex>. Максимальное расстояние между двумя точками внутри квадрата достигается, когда они являются вершинами диагонали, то есть на глубине <tex>i</tex> расстояние между любыми двумя точками в одном квадрате не превосходит <tex>s \sqrt 2 / 2^i</tex>. Поскольку внутренняя вершина квадродерева содержит хотя бы 2 точки в соответствующем ей квадрате, то <tex>s \sqrt 2 / 2^i \geq c</tex>, так как <tex>c</tex> {{---}} минимальное расстояние между точками в <tex>P</tex>. Отсюда следует, что <tex>i \leq \log_2(s \sqrt 2 / c) = \log_2 (s / c) + 1/2</tex>. Значит, глубина любой внутренней вершины не превосходит <tex>\log_2 (s / c) + 1/2</tex>, из чего следует утверждение леммы (так как самый глубокий лист лежит на 1 глубже самой глубокой внутренней вершины).
== Перечисление точек в произвольном прямоугольнике ==
''В этом разделе написаны сомнительные вещи и вообще он не нужен, можно не читать.''
Пусть на вход подаётся некоторый прямоугольник <tex>M</tex>, для которого надо вернуть все точки из множества <tex>P</tex>, которые принадлежат этому прямоугольнику.
Короче, я не знаю, как это доказать, и мне кажется, что это не так. Если нам подали прямоугольник, содержащий все точки, то мы пройдём по всем вершинам, которых <tex>O(d \cdot n)</tex> (так написано в книжке, и лучшей оценки, видимо, нет). Возможно, я неправильно понимаю, что от нас хотят. Может быть, можно придумать какие-то оптимизации, ибо так совсем печальная оценка на запрос получается. Также могу предположить, что оценку времени можно улучшить, использовав функцию от размера ответа, но опять же не могу придумать/найти, как это сделать.
== Сбалансированное квадродерево ==
Квадродерево называется '''сбалансированным''', если для соответствующего ему разбиения плоскости на квадраты верно, что для любых двух соседних квадратов их стороны отличаются не более чем в два раза.
== Сжатое квадродерево ==
Сжатое квадродерево для <tex>n</tex> точек имеет <tex>O(n)</tex> вершин и глубину <tex>O(n)</tex>.
|proof=
Как отмечалось в представленной выше теореме, достаточно доказать оценку <tex>O(n)</tex> для числа внутренних вершин, каждая из которых является интересным квадратом (Кэп: то есть для числа интересных квадратов это надо доказать). Докажем по индукции, что в квадродереве для <tex>n</tex> точек количество интересных квадратов меньше либо равно <tex>n</tex>:
* для <tex>n = 1</tex> это очевидно;
* пусть в квадродереве доказано для квадродерева для <tex>n > - 1</tex> точек. Рассмотрим кореньДобавим новую точку <tex>x</tex>: сначала найдём наименьший интересный квадрат <tex>p(x)</tex>, у него обязательно должно быть хотя бы 2 непустых ребёнкакоторый её содержит. Если хотя бы один из детей является точкой<tex>x</tex> находится в его пустой четверти, то остальные непустые дети являются деревьямипросто добавляем <tex>x</tex> как лист, в которых суммарно не больше изменив число интересных квадратов. Если же четверть <tex>n - 1p(x)</tex> точек (и в каждом их меньше которую необходимо вставить <tex>nx</tex>). Значит, в них суммарно не больше уже содержит точку <tex>n - 1y</tex> интересных квадратов (по индукционному предположению). Следовательно, во всём квадродереве не больше или интересный квадрат <tex>nr</tex> интересных квадратов. Если же все непустые дети корня являются интересными квадратами), то мы всё равно можем применить индукционное предположение ко всем детям и получить то же самоедобавить в дерево интересный квадрат, поскольку во всех поддеревьях который будет меньше содержать <tex>nx</tex> точек (ибо их суммарно и <tex>ny</tex> и везде есть хотя бы одна, так как дети непустые)в разных четвертях. На самом делеТаким образом, как оказалосьпри добавлении точки мы увеличиваем количество интересных квадратов не более, у корня необязательно хотя бы 2 непустых ребёнка, но для детей корня это уже верно (что у поддеревьев корень имеет хотя бы 2 непустых ребёнка), так что доказательство не портитсячем на один.
Таким образом, квадродерево для <tex>n</tex> точек имеет <tex>O(n)</tex> вершин. Глубина, очевидно, тоже <tex>O(n)</tex>, поскольку на каждом уровне есть хотя бы одна вершина (здесь под вершинами имеются в виду узлы в дереве). При этом оценки получше нет (то есть глубина <tex>\Theta(n)</tex>). На картинке в правом дереве можно на место левого нижнего красного кружка поставить опять такое дерево и так делать сколь угодно долго, получим глубину <tex>\Theta(n)</tex>.
