170
правок
Изменения
м
Нет описания правки
Все операции похожи на аналогичные в обычных деревьях поиска. Только они делаются за <tex>O(n)</tex>. Того же самого можно добиться, храня точки просто в списке или векторе. Хотя на практике, наверно, так побыстрее. Но всё же сама по себе структура не особо полезна, зато пополезнее будет [[Skip quadtree: определение, время работы | Skip Quadtree]].
=== Поиск ===
Нам дают точку, хотим найти наименьший интересный квадрат, который её содержит(содержит геометрически, в самом дереве её может не быть, тут, возможно, правильнее сказать «пересекает»). Довольно очевидно, как это делать: просто идём вниз по дереву в нужную четверть, начиная с корня. В какой-то момент закончим, найдя наименьший интересный квадрат, который содержит искомую точку. Дальше легко проверить, есть ли такая точка в квадродереве. Работает, очевидно, за высоту, которая линейно зависит от числа точек (см. выше).
=== Вставка ===
Сначала запускаем поиск, находим наименьший квадрат, в который надо вставиться, понимаем, в какую четверть вставляться. Если она пустая, то всё совсем просто, меняем 1 указатель. Если там есть точка, то добавим новый интересный квадрат, поправим <tex>O(1)</tex> указателей, и всё хорошо. Таким образом, нужно сделать поиск за <tex>O(n)</tex> и ещё <tex>O(1)</tex> действий.
