Сложность поиска по квадрату дерева

Question

Я уже искал эту информацию. Найдено это:

https://groups.google.com/forum/#!topic/uw.cs.cs240/MGfrsvKAiMA

и это:

How can worst case complexity of quad tree O(N)?

, но я не считаю, что это отвечает мою проблему. Возможно, первое, но я не понимаю объяснения. До такой степени.

У меня есть квадратное дерево над дискретным пространством (2d квадратная таблица сущностей). Это дерево регионов, как описано на странице английской Википедии (https://en.wikipedia.org/wiki/Quadtree#Types). В каждом регионе может находиться только одна сущность. Каждая сущность имеет свои дискретные координаты.

Я реализовал метод поиска всех объектов в определенном (дискретном) AABB, работающем точно так же, как функция queryRange() на вышеупомянутой странице Wiki.

Мой вопрос: какова временная сложность для этого queryRange() функция?

Я попытался выяснить это сам, но, похоже, он зависит от многих различных факторов, таких как: глубина дерева, количество элементов в дереве, размер данных AABB. Я думаю, что в его основе это связано с количеством поддеревьев, посещенных рекурсией queryRange().

Также я был бы благодарен за любые достоверные источники. Я пишу магистерскую диссертацию, и мне нужны цитаты. Я действительно не могу показаться, что Google ничего хорошего на эту тему.

Answer 1

Временная сложность запросов зависит от многих аспектов:

1. Распределение данных
2. Порядок введения (если вы не сбалансировать дерево)
3. ли вы хранить точки или прямоугольники (точки намного более распространенным, насколько я могу сказать)
4. Тип запросов вы выполняете

Я не ехр ert при вычислении сложности, так что может быть каким-то образом, как средний сложность может быть рассчитана, но может быть неэффективна для данного реального сценария.

Максимальная сложность немного проще. Скажем, n - количество записей и h высоты дерева.

Большой запрос, очевидно, возвращает все элементы, поэтому сложность O (n). Очень узкий запрос должен проходить от корня до ровно одного листа, следовательно, O (h). Это дает объединенный O (n + h).

Есть некоторые пограничные случаи: если данные, например, имеют такую ​​форму, что все точки находятся на одной линии (0,1), (0,2), (0,3), (0,4) , ... и они вставляются в порядке, то дерево может выродиться в список, такой, что h = n, если вы не выполните некоторое перебалансирование.

Если вас интересуют варианты quadtree, вы можете ознакомиться с недавними PH-Tree. PDF содержит некоторые вычисления сложности.PH-Tree - это квадрант области (разложение на квадранты) на основе декомпозиции бит-уровня-три. Таким образом, максимальная глубина равна количеству бит в значениях, обычно 32 или 64. Структура не зависит от порядка вставки, поэтому нет перебалансировки (и не требуется, поскольку глубина ограничена). Некоторые технические обновления можно найти here. (Отказ от ответственности: это основано на моих собственных исследованиях, когда я был в университете).