Skip quadtree: определение, время работы

Эта статья находится в разработке!

Описание

По картинке должно быть понятно

Skip quadtree — как skip list, только вместо list'а quadtree. Поэтому желательно знать, что такое skip list, и необходимо знать, что такое сжатое квадродерево. В данной статье будет рассматриваться только рандомизированая версия этой структуры, потому что больше и не нужно, кажется.

The randomized skip quadtree — последовательность сжатых квадродеревьев над последовательностью подмножеств некоего исходного множества [math]S[/math]. [math]S_0 = S[/math], в [math]S_1[/math] каждый элемент из [math]S_0[/math] входит с вероятностью [math]p[/math] и так далее. The randomized skip quadtree состоит из последовательности [math]\{Q_i\}[/math], где [math]Q_i[/math] — сжатое квадродерево над множеством [math]S_i[/math]. Будем называть эти квадродеревья уровнями, при этом нулевой уровень содержит в точности точки из [math]S[/math]. Заметим, что если какой-то квадрат интересный в [math]Q_i[/math], то он интересный и в [math]Q_{i-1}[/math].

Операции над skip quadtree

Будем для каждого интересного квадрата на каждом уровне хранить указатели на тот же квадрат уровнем ниже и уровнем выше (если есть).

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

Для добавления сначала надо локализоваться. При этом мы локализуемся сразу на всех уровнях (так уж устроен процесс). Дальше добавляемся в нулевой уровень, затем с вероятностью [math]p[/math] добавляемся на уровень выше и так далее до первого недобавления. При этом количество уровней должно увеличиться максимум на 1, то есть, если появился новый уровень, то процесс точно заканчивается.

Удаление совсем просто: локализуемся, удаляем со всех уровней, на которых есть.

Время работы

Лемма (О количестве шагов на одном уровне):

На каждом уровне совершается [math]O(1)[/math] шагов поиска для любой точки [math]x[/math].

Доказательство:

[math]\triangleright[/math]

Пусть в [math]Q_i[/math] (то есть на [math]i[/math]-ом уровне) поиск точки [math]x[/math], начинающийся с корня, проходит по квадратам [math]p_0, p_1, \dots, p_m[/math]. Пусть случайная величина [math]j[/math] — количество шагов поиска в [math]Q_i[/math], тогда [math]p_{m - j}[/math] — последний квадрат из [math]p_0, p_1, \dots, p_m[/math], являющийся интересным в [math]Q_{i + 1}[/math]. Оценим вероятность того, что делается [math]j[/math] шагов. Забьём на случай [math]j = 0[/math], так как он не важен при расчёте мат. ожидания. На пути [math]p_{m - j + 1} \dots, p_m[/math] будет хотя бы [math]j + 1[/math] непустых четвертинок. У первого квадрата на этом пути есть хотя бы 2 непустых четвертинки, одна из них — следующий квадрат на пути, в котором тоже хотя бы 2 непустых четвертинки, и так далее. В последнем квадрате просто хотя бы 2 непустых четвертинки. Чтобы [math]p_{m - j}[/math] был последним из [math]p_0, p_1, \dots, p_m[/math] интересным квадратом в [math]Q_{i + 1}[/math] небходимо, чтобы среди этих [math]j + 1[/math] непустых четвертинок только одна (вероятность этого назовём [math]Pr_1[/math]) или ноль (вероятность этого назовём [math]Pr_0[/math]) были непустыми в [math]Q_{i + 1}[/math]. Иначе, если будет хотя бы 2 непустые четвертинки, то их наименьший общий предок в дереве будет интересным квадратом и будет находиться глубже [math]p_{m - j}[/math]. Таким образом, искомая вероятность не превосходит [math]Pr_0 + Pr_1[/math]. Лично мне утверждение из предыдущего абзаца далось с трудом, если у вас тоже всё очень плохо, попробуйте напрячь мозг и залипнуть в картинку, вдруг поможет [math]Pr_0 \leq p^{(j + 1)}[/math], потому что это в сущности вероятность того, что ни одна точка из как минимум [math]j + 1[/math] непустых четвертинок не попала на уровень выше. [math]Pr_1 \leq (j + 1) \cdot p^{(j + 1)}[/math], потому что это в сущности вероятность того, что ровно одна точка из как минимум [math]j + 1[/math] непустых четвертинок не попала на уровень выше. В общем, если чуть подумать, оценки на [math]Pr_0[/math] и [math]Pr_1[/math] довольно ясны. [math]E(j) = \sum\limits_{j = 1}^{m} j \cdot Pr(j) \leq \sum\limits_{j = 1}^{m} j \cdot (p^{(j + 1)} + (j + 1) \cdot p^{(j + 1)}) \leq \sum\limits_{j = 1}^{\infty} j \cdot (p^{(j + 1)} + (j + 1) \cdot p^{(j + 1)})[/math] В общем, если так подумать, это [math]O(1)[/math]. Мне пока лень совсем строго написать, но вообще и так понятно. Разумеется, при условии [math]p \in (0, 1)[/math].

[math]\triangleleft[/math]

Источник

http://arxiv.org/pdf/cs.cg/0507049.pdf