Range Trees: почему бы не сэкономить место по умолчанию?

Question

Предположим, у вас есть набор S уникальных точек на 2-мерной плоскости. Теперь вы ожидаете кучу вопросов в виде "это точка p присутствует в S"Вы решили построить Range Range для хранения вашего S и ответь на этот вопрос. Основная идея Range Range заключается в том, что вы сначала строите сбалансированное двоичное дерево поиска. Tree0 на 0-th координаты, а затем в каждом узле этого Tree0 построить еще одно сбалансированное дерево поиска Tree1 но на этот раз, используя 1-st координировать как ваш ключ. Статья в Википедии для Range Tree.

Теперь я ожидал, что Tree1 который построен для каждого узла n0 из Tree0 будет держать именно те точки, чьи 0-th координата равна ключу от n0, Однако, если вы прочитаете больше о Range Trees, вы увидите, что это не так. В частности:

1. Корень r0 из Tree0 содержит Tree1 который содержит все точки.
2. Левое дитя r0 содержит Tree1 который содержит все точки, чьи 0-th координата меньше, чем 0-th координировать в r0,
3. Правильный ребенок r0 содержит Tree1 который содержит все точки, чьи 0-th координата больше, чем от r0,

Если вы продолжите эту логику, вы увидите, что на каждом уровне дерева диапазонов все точки сохраняются ровно один раз. Итак, каждый уровень требует n память и с глубины сбалансированного Tree0 является logn, это дает O(nlogn) как требование к памяти.

Тем не менее, если бы вы просто хранить точки, чьи 0-th координата точно соответствует ключу в узле, вы будете хранить каждую точку один раз для всего дерева (а не для уровня дерева), что дает O(n) требование к памяти.

Какова причина сохранения точек один раз за уровень в дереве рангов? Это разрешает какие-то крутые запросы диапазона или что-то? Пока это выглядит как любой запрос, который вы могли бы выполнить на O(nlogn) версия также доступна для O(n) версия. Что мне не хватает?

Answer 1

(Расширение комментария @user3386109 до полного ответа.)

Существует несколько различных структур данных для хранения двумерных наборов точек, каждая из которых оптимизирована для разных типов запросов. Как следует из названия, деревья диапазонов оптимизированы для поиска по диапазонам, запросов вида "вот прямоугольник, каковы все точки в этом прямоугольнике?" Структура дерева диапазонов - хранение каждой точки в нескольких различных поддеревьях - спроектирована таким образом, чтобы вы могли найти диапазон узлов в 1D, содержащий одну ось прямоугольника, а затем обнаружить все узлы в следующем измерении, которые находятся в другом измерении. прямоугольника. Если вы не планируете делать какие-либо запросы в этой форме, тогда нет необходимости хранить вещи таким образом. По сути, вы платите за то, что не собираетесь использовать.

Существуют и другие структуры данных, которые можно использовать для хранения набора точек и проверки наличия конкретной точки. Если это единственный вопрос, на который вам нужно ответить, простая хеш-таблица может быть всем, что вам нужно. Вы также можете использовать обычный BST, в котором точки сравниваются сначала по их первым компонентам, а затем по вторым компонентам. (Вы также можете использовать здесь kd-дерево, если хотите.)

Надеюсь это поможет!