170
правок
Изменения
Нет описания правки
== Операции над skip quadtree ==
Будем для каждого интересного квадрата на каждом уровне хранить указатели на тот же квадрат уровнем ниже и уровнем выше (если есть).
Локализация выполняется аналогично сжатому квадродереву. Сначала локализуемся в квадродереве наибольшего уровня, начиная с его корня. Затем локализуемся в квадродереве уровня ниже, начиная уже не с корня, а с того квадрата, который нашли на прошлом уровне. И так далее, пока не дойдём до дна.
Для добавления сначала надо локализоваться. При этом мы локализуемся сразу на всех уровнях. Дальше добавляемся в нулевой уровень, затем с вероятностью <tex>p</tex> добавляемся на уровень выше и так далее до первого недобавления. При этом количество уровней должно увеличиться максимум на 1.
Удаление совсем просто: локализуемся, удаляем со всех уровней, на которых есть.
== Время работы ==
== Источник ==
http://arxiv.org/pdf/cs.cg/0507049.pdf
