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

Question

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

Сначала я строю дерево бинарного поиска на основе значения 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++, если это имеет значение.}

* _{Выполнение запроса диапазона для x в диапазоне [-inf, 1] и y в диапазоне [0, 5].}

Answer 1

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

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

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