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