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

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

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