Изменения
→Удаление
== Описание ==
[[Файл:Skip_quadtree.png | 500px | thumb]]
Skip quadtree {{---}} структура данных, позволяющая напоминающая [[Список с пропусками | skip-list]], которая позволяет эффективно локализоваться и производить операции над множеством точек.
В данной статье будет рассматриваться только рандомизированая версия этой структуры.
The randomized skip quadtree {{---}} последовательность сжатых квадродеревьев над последовательностью подмножеств некоторого исходного множества точек <tex>S</tex>. <tex>S_0 = S</tex>, в <tex>S_i</tex> каждый элемент из <tex>S_{i-1}</tex> входит с вероятностью <tex>p \in (0, 1)</tex>, то есть <tex>S_i \subset S_{i-1}</tex>. The randomized skip quadtree состоит из последовательности <tex>\{Q_i\}</tex>, где <tex>Q_i</tex> {{---}} [[Квадродеревья#Сжатое квадродерево | сжатое квадродерево]] над множеством <tex>S_i</tex>. Будем называть эти квадродеревья уровнями, при этом нулевой уровень содержит в точности точки из <tex>S</tex>.
На рисунке представлено дерево, состоящее из трех слоев: <tex>Q_0</tex>, <tex>Q_1</tex>, <tex>Q_2</tex>. Одинаковые вершины, находящиеся на разных уровнях, соединены линиями. Стрелками обозначены переходы в процессе локализации при поиске точки <tex>y</tex>. Любая вершина однозначно определяется своими координатами на каждом уровне. Поэтому по вершине с уровня <tex>i</tex> мы можем получить ее на уровне <tex>i - 1</tex>, если она [[Квадродеревья и перечисление точек в произвольном прямоугольнике (статика)#interesting | интересная]]на уровне <tex>i</tex>, так как в противном случае она могла быть сжата.
Заметим, что если какой-то квадрат интересный в <tex>Q_i</tex>, то он интересный и в <tex>Q_{i-1}</tex>, так как <tex>S_i \subset S_{i-1}</tex> по определению структуры.
===Удаление===
При удалении локализуемся и удаляем вершину со всех уровней, на которых она есть, не забывая обновлять ссылки или ассоциаивный ассоциативный массив. При этом какой-то уровень мог стать пустым, в таком случае выкинем его.
== Время работы и память ==
n.add_subtree(points) // добавляем все точки поддерева ''внутренней'' вершины
'''else if''' (n is not critical)
'''node''' q // некритическая вершина на максимальном уровне i, соответствующая n level = 0 k - 1 // текущий максимальный уровень, на котором вершина q некритическая '''for''' i = k - 1 .. 0 // k - количество уровней в skip quadtree '''while''' (level > 0) node <tex>n_in_{level}</tex> = n from <tex>Q_iQ_{level}</tex> // вершина, соответствующая n в дереве <tex>Q_iQ_{level}</tex> '''if''' (<tex>n_in_{level}</tex> != null '''and''' <tex>n_in_{level}</tex> is not critical) q = <tex>n_in_{level}</tex> level = i
'''break'''
level--
'''while''' (true)
'''if''' (q is not critical)
