Диапазон поиска сложности R дерева и R* дерева

Question

Какова сложность поиска диапазона для дерева R и дерева R*? Я понимаю процесс поиска диапазона: аналогично DFS-поиску, он посещает каждый узел, и если ограничивающий прямоугольник узла пересекает целевой диапазон, то включите узел в набор результатов. Точнее, нам также нужно рассмотреть стратегию ветвления и ограничения, которую он использует: если родительский узел не пересекается с целью, то мы не посещаем его дочерние узлы. Тогда сложность должна быть меньше, чем O(n), где n - количество узлов. Я действительно не знаю, как рассчитать количество узлов с учетом количества листьев (или точек данных). Кто-нибудь может дать мне объяснение здесь? Спасибо.

Answer 1

Очевидно, что наихудший случай должен быть не менее O(n), если ваш диапазон равен [-∞;∞] во всех измерениях. Это может быть так же плохо, как O(n log n) тогда из-за дерева.

Если предположить, что ответом является одна запись, средний случай, вероятно, равен O(log n) - нужно следовать только нескольким путям через дерево (если у вас мало перекрытий).

Это журнал для базы вашего размера страницы. Так что обычно оно не превышает 5, потому что вы никогда не хотите деревьев с более чем 1000^5=10^15 объектов.

Для практических целей предположим, что сложность среды выполнения - это просто размер набора ответов O(s). Выберите 2% ваших данных, это займет вдвое больше, чем 1%.