1632
правки
Изменения
м
Для добавления ===Вставка===При вставке сначала надо локализоваться. При этом мы локализуемся сразу на всех уровнях (так уж устроен процесс). Дальше добавляемся в , запоминая ссылки, дальше добавляем вершину на нулевой уровень, затем с вероятностью <tex>p</tex> добавляемся на уровень выше и так далее до первого недобавления. При этом количество уровней должно может увеличиться максимум на <tex>1</tex>, то есть, если появился новый уровень, то процесс точно заканчивается. Хотя не, давайте без последнего условия, вроде с ним только лучше, но без него проще доказывать.
rollbackEdits.php mass rollback
== Описание ==
[[Файл: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> по определению структуры.
* Так как каждая вершина однозначно задается своими координатами, можем сопоставить ей маску. Используем ассоциативный массив, чтобы по маске получать ссылку на вершину. Такие массивы будем хранить для каждого уровня skip quadtree.
===Локализация===Локализация выполняется аналогично сжатому квадродеревулокализации в сжатом квадродереве. Под локализацией подразумевается, что мы хотим найти минимальный интересный квадрат, геометрически содержащий данную точку (содержит геометрически, в самом дереве её может не быть, тут, возможно, правильнее сказать «пересекает»). Сначала локализуемся в квадродереве наибольшего уровня, начиная с его корня. Затем локализуемся в квадродереве уровня уровнем ниже, начиная уже не с корня, а с того квадрата, который нашли на прошлом уровне. И так далееНо на каждом уровне, кроме нулевого, локализумся не до листа, а до глубочайшего интересного. Продолжаем, пока не дойдём до днанулевого уровня.
===Удаление совсем просто: ===При удалении локализуемся, и удаляем вершину со всех уровней, на которых она есть, не забывая обновлять ссылки или ассоциативный массив. При этом какой-то уровень мог стать пустым, в таком случае выкинем его.
== Время работы и память ==
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)
