Изменения

[[Файл: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> по определению структуры.

Будем для каждого интересного квадрата Для реализации операций нам нужно уметь получать по вершине с уровня <tex>i</tex> соответствующую ей вершину с уровня <tex>i - 1</tex>. Сделать это можно двумя способами:* Хранить в вершине ссылку на каждом уровне хранить указатели на тот же квадрат вершину уровнем ниже и уровнем выше (если есть).* Так как каждая вершина однозначно задается своими координатами, можем сопоставить ей маску. Используем ассоциативный массив, чтобы по маске получать ссылку на вершину. Такие массивы будем хранить для каждого уровня skip quadtree.

===Локализация===Локализация выполняется аналогично сжатому квадродеревулокализации в сжатом квадродереве. Под локализацией подразумевается, что мы хотим найти минимальный интересный квадрат, геометрически содержащий данную точку (содержит геометрически, в самом дереве её может не быть, тут, возможно, правильнее сказать «пересекает»). Сначала локализуемся в квадродереве наибольшего уровня, начиная с его корня. Затем локализуемся в квадродереве уровня уровнем ниже, начиная уже не с корня, а с того квадрата, который нашли на прошлом уровне. И так далееНо на каждом уровне, кроме нулевого, локализумся не до листа, а до глубочайшего интересного. Продолжаем, пока не дойдём до днанулевого уровня.

Для добавления ===Вставка===При вставке сначала надо локализоваться. При этом мы локализуемся сразу на всех уровнях (так уж устроен процесс). Дальше добавляемся в , запоминая ссылки, дальше добавляем вершину на нулевой уровень, затем с вероятностью <tex>p</tex> добавляемся на уровень выше и так далее до первого недобавления. При этом количество уровней должно может увеличиться максимум на <tex>1</tex>, то есть, если появился новый уровень, то процесс точно заканчивается. Хотя не, давайте без последнего условия, вроде с ним только лучше, но без него проще доказывать.

===Удаление совсем просто: ===При удалении локализуемся, и удаляем вершину со всех уровней, на которых она есть, не забывая обновлять ссылки или ассоциативный массив. При этом какой-то уровень мог стать пустым, в таком случае выкинем его.

'''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--

'''node ''' qc = ребенок q, содержащий ту же область E, что и q