170
правок
Изменения
м
Нет описания правки
Skip quadtree {{---}} как skip list, только вместо list'а quadtree. Поэтому желательно знать, что такое [[Список с пропусками | skip list]], и необходимо знать, что такое [[Квадродеревья и перечисление точек в произвольном прямоугольнике (статика)#Сжатое квадродерево | сжатое квадродерево]]. В данной статье будет рассматриваться только рандомизированая версия этой структуры, потому что больше и не нужно, кажется.
The randomized skip quadtree {{---}} последовательность сжатых квадродеревьев над последовательностью подмножеств некоего некого исходного множества <tex>S</tex>. <tex>S_0 = S</tex>, в <tex>S_1</tex> каждый элемент из <tex>S_0</tex> входит с вероятностью <tex>p</tex> и так далее. The randomized skip quadtree состоит из последовательности <tex>\{Q_i\}</tex>, где <tex>Q_i</tex> {{---}} сжатое квадродерево над множеством <tex>S_i</tex>. Будем называть эти квадродеревья уровнями, при этом нулевой уровень содержит в точности точки из <tex>S</tex>.
Заметим, что если какой-то квадрат [[Квадродеревья и перечисление точек в произвольном прямоугольнике (статика)#interesting | интересный]] в <tex>Q_i</tex>, то он интересный и в <tex>Q_{i-1}</tex>.
Для добавления сначала надо локализоваться. При этом мы локализуемся сразу на всех уровнях (так уж устроен процесс). Дальше добавляемся в нулевой уровень, затем с вероятностью <tex>p</tex> добавляемся на уровень выше и так далее до первого недобавления. При этом количество уровней должно увеличиться максимум на 1, то есть, если появился новый уровень, то процесс точно заканчивается. Хотя не, давайте без последнего условия, вроде с ним только лучше, но без него проще доказывать.
Удаление совсем просто: локализуемся, удаляем со всех уровней, на которых есть. При этом какой-то уровень мог стать пустым, в таком случае выкинем его.
== Время работы и память ==
Пусть в <tex>Q_i</tex> (то есть на <tex>i</tex>-ом уровне) поиск точки <tex>x</tex>, начинающийся с корня, проходит по квадратам <tex>p_0, p_1, \dots, p_m</tex>. Пусть случайная величина <tex>j</tex> {{---}} количество шагов поиска в <tex>Q_i</tex>, тогда <tex>p_{m - j}</tex> {{---}} последний квадрат из <tex>p_0, p_1, \dots, p_m</tex>, являющийся интересным в <tex>Q_{i + 1}</tex>.
Оценим вероятность того, что делается <tex>j</tex> шагов. Забьём на случай <tex>j = 0</tex>, так как он не важен при расчёте мат. ожидания. На пути <tex>p_{m - j + 1} \dots, p_m</tex> будет хотя бы <tex>j + 1</tex> непустых четвертинок. У первого квадрата на этом пути есть хотя бы 2 непустых непустые четвертинки, одна из них {{---}} следующий квадрат на пути, в котором тоже хотя бы 2 непустых непустые четвертинки, и так далее. В последнем квадрате просто хотя бы 2 непустых непустые четвертинки. Чтобы <tex>p_{m - j}</tex> был последним из <tex>p_0, p_1, \dots, p_m</tex> интересным квадратом в <tex>Q_{i + 1}</tex> небходимо, чтобы среди этих <tex>j + 1</tex> непустых четвертинок только одна (вероятность этого назовём <tex>Pr_1</tex>) или ноль (вероятность этого назовём <tex>Pr_0</tex>) были непустыми в <tex>Q_{i + 1}</tex>. Иначе, если будет хотя бы 2 непустые четвертинкипара непустых четвертинок, то их наименьший общий предок в дереве будет интересным квадратом и будет находиться глубже <tex>p_{m - j}</tex>. Таким образом, искомая вероятность не превосходит <tex>Pr_0 + Pr_1</tex>.
''Лично мне утверждение из предыдущего абзаца далось с трудом, если у вас тоже всё очень плохо, попробуйте напрячь мозг и залипнуть в картинку, вдруг поможет. Хотя я постарался расписать поподробней, чем в статье.''
<tex>Pr_0 \leq p^{(j + 1)}</tex>, потому что это в сущности вероятность того, что ни одна точка из как минимум <tex>j + 1</tex> непустых четвертинок не попала на уровень выше.
Для оценки мат. ожидания посчитаем вероятность того, что количество уровней <tex>h</tex> равно <tex>k</tex>. <tex>p(h = k) = p(h \leq k) \cdot p(h \geq k)</tex>.
<tex>p(h \leq k) = (1 - p^{k+1})^n</tex>, потому что вероятность того, что точка дойдёт до уровня <tex>k + 1</tex> , равна <tex>p^{k + 1}</tex>.
<tex>p(h \geq k) = (1 - (1 - p^k)^n)</tex>, потому что вероятность того, что точка не дойдёт до уровня <tex>k</tex> , равна <tex>1 - p^k</tex>.
<tex>E(h) = \sum\limits_{k = 1}^{\infty} k \cdot p(h = k) = p(1) \cdot 1 + \dots + p(\log_{1/p} n) \cdot \log_{1/p} n + \sum\limits_{k = \log_{1/p} n + 1}^{\infty} k \cdot p(k)</tex>
