Как искать в дереве диапазонов?

Я прочитал несколько слайдов, например, одну последнюю страницу , где описывают алгоритм поиска. Однако у меня есть основной вопрос. Данные лежат в двумерном пространстве.

Сначала я создаю двоичное дерево поиска на основе значения x точек. Каждый внутренний узел содержит BST на основе значения y точек, лежащих в поддереве этого внутреннего узла.

Затем я думаю, что мне следует искать точки, которые лежат в запросе диапазона [x1, x2], а затем проверять, удовлетворяется ли для этих точек запрошенный запрос диапазона [y1, y2]. Однако алгоритм предполагает, что вы должны искать в BST на основе y внутреннего узла, если диапазон внутреннего узла находится внутри [x1, x2], но я этого не понимаю.

Если мы это сделаем, то в примере, который у меня есть, мы будем искать (без причины) базирующийся на y BST корня. Проверьте пример:

                      ------ 0 ---------------------
                      |                            |
                ---- -3 ----                  ---- 4 ------ 
                |          |                  |           |
          ---- -4 -    -2              --- 3 ---          5
          |       |    / \             |       |         / \
         -5   (-3,4) (-2,2)(0,7)       2    (4,-4)   (5,3)(6,-1)
         / \                          / \
    (-5,6) (-4,0)                  (2,1) (3,6)

И запрос диапазона, который я хочу выполнить, это (-oo, 1) x (0, 5)*.

Если я смотрю на корень, он имеет значение 0, поэтому он заключен в (-oo, 1), поэтому, если я буду следовать алгоритму, я буду искать все дерево корня на основе y?

Это должно быть дерево, содержащее все точки, поэтому нет смысла продолжать поиск в дереве на основе x. Более того, это приведет к большему количеству посещаемых узлов, чем необходимо.

Я реализую это в

c++ search algorithm computational-geometry range-tree
person gsamaras    schedule 14.05.2016    source источник
comment
Является ли (-inf, 1) координатой (x, y) или (x_lo, x_hi)? Я предполагаю, что это последнее.   -  person James Adkison    schedule 14.05.2016
comment
@JamesAdkison последний, я должен отредактировать свой вопрос? Как мне это сделать, если да?   -  person gsamaras    schedule 14.05.2016
comment
Мне было бы ясно, если бы были утверждения, подобные: Выполнение запроса диапазона для x в диапазоне [-inf, 1] и y в диапазоне [0, 5] (или что-то подобное).   -  person James Adkison    schedule 14.05.2016

Ответы (1)


arrow_upward
2
arrow_downward

Алгоритм, который вы предлагаете, не совсем правильный - вы должны сравнивать диапазон, который вы запрашиваете, с диапазоном узла, на который вы смотрите, а не со значением узла.

Например, сначала вы должны сравнить (-inf, 1) с (-5, 6), который является диапазоном данных дерева (вы также можете использовать (-inf, inf) в качестве диапазона данных дерева или любого интервала, который включает (-5, 6), если на то пошло) вместо значения 0. Рекурсивно вы должны сравнить диапазон запроса с диапазоном поддерева, укоренившегося в узле, в котором вы делаете запрос.

Кроме того, обновление диапазона может быть выполнено во время поиска - при разделении на узле верхняя/нижняя граница левого/правого интервала рекурсивного вызова является значением узла.

person zw324    schedule 14.05.2016
comment
Да, я знаю, что я что-то упустил, но я не знал, что. Тем не менее, я пытаюсь запустить пример, который у меня есть в моем вопросе, но я не уверен, как это сделать. Я имею в виду, как корень может проверить наличие (-5, 6)? Он его хранит? - person gsamaras; 14.05.2016
comment
Вы можете сохранить его (я думаю, что это может обеспечить некоторое ускорение в крайнем случае, например, когда все дерево находится в диапазоне запроса), но вы можете использовать (-inf, inf) и обновлять интервал во время запроса - мой последний обновление должно было решить эту проблему :-) - person zw324; 14.05.2016
comment
Спасибо, мистер Вэй, я задал новый относительный вопрос. Если у вас есть время, посмотрите! - person gsamaras; 14.05.2016