Изменения
→Удаление
== Описание ==
[[Файл:Skip_quadtree.png | 500px | thumb | По картинке должно быть понятно]]Skip quadtree {{---}} как skip list, только вместо list'а quadtree. Поэтому желательно знатьструктура данных, что такое напоминающая [[Список с пропусками | skip -list]], которая позволяет эффективно локализоваться и необходимо знать, что такое [[Квадродеревья#Сжатое квадродерево | сжатое квадродерево]]. В данной статье будет рассматриваться только рандомизированая версия этой структуры, потому что больше и не нужно, кажетсяпроизводить операции над множеством точек.
В данной статье будет рассматриваться только рандомизированая версия этой структуры. The randomized skip quadtree {{---}} последовательность сжатых квадродеревьев над последовательностью подмножеств некоторого исходного множества точек <tex>S</tex>. <tex>S_0 = S</tex>, в <tex>S_1S_i</tex> каждый элемент из <tex>S_0S_{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> '''break''' level = i break--
'''while''' (true)
'''if''' (q is not critical)
'''node ''' qc = ребенок q, содержащий ту же область E, что и q
'''if''' (qc is not leaf '''or''' level == 0)
q = qc
'''else'''
'''break'''
que.push(q)
'''else'''
que.add_all(n.children)