Путаница в дереве приоритетного поиска

Ваша последняя логика на самом деле все еще верна. Значение (-5,6) уже должно было быть получено, когда вы нажмете на узел, который вы пометили (6,-3). Так вот, я не специалист по математике. Но общая идея такова. В дереве приоритетного поиска, как вы реализовали, вы фактически выполняете поиск по двум отдельным критериям. Для x это простой бинарный поиск диапазона. Для y вы фактически ищете его как дерево приоритетов (хорошо для поиска y:inf или -inf:y, в зависимости от того, используете ли вы max или min.)

Обратите внимание, что внизу страницы 15 говорится, что дерево подходит для полубесконечного диапазона (один бесконечен). Продолжайте читать, и вы увидите, как дерево оптимизируется для полубесконечного диапазона значений y.

Короче говоря, поскольку ваше дерево построено с x в качестве бинарного поиска и y в качестве приоритета (с использованием максимального остаточного значения), оптимальный поиск [x1:x2],[y1:inf].

Каждый узел в дереве по существу хранит 2 вещи. 1. Середина x (или max-x в левом дереве, и решение пройти влево или вправо основано на проверке >x). 2. ТОЧКА с наибольшим значением y в поддереве, которое не было добавлено к предыдущему.

Алгоритм поиска по сути выглядит так. Начиная с корня с использованием критериев [x1:x2], [y1:inf] 1. Проверьте значение y ТОЧКИ, назначенной узлу. Если y > y1, перейдите к 2, в противном случае ОСТАНОВИТЕ перемещение вниз (поскольку ТОЧКА, назначенная узлу, имеет самое высокое значение y, и если проверка не удалась, под ним нет другого узла, который мог бы выполнить [y1:inf]. 2. Проверить если значение x точки находится в диапазоне [x1:x2]. Если это так, включите эту точку в выходные данные. Перейдите к шагу 3, независимо от того, включили ли вы эту точку. 3. Проверьте значение "средней точки" узла (назовем это mx). Если mx находится в диапазоне [x1:x2], пройдите по обоим пути. Если mx равно ‹ [x1:x2], пройдите влево. В противном случае пройдите вправо. Вернитесь к шагу 1 для каждого пути, который вы траверс.

РЕДАКТИРОВАТЬ для очень, ОЧЕНЬ длинного текста: давайте рассмотрим ваш пример. Я сделал дополнительную аннотацию, обозначив каждую точку буквой («имя» точки). Каждый узел теперь имеет формат имени точки с его значением y в скобках и «средним диапазоном» x под ним. Для листовых узлов те, что отмечены '*', означают, что они уже назначены где-то выше по дереву, и их следует рассматривать как NIL, если вы когда-либо до них доберетесь.

                              7(E)
                       ------ 0 ---------------------
                       |                            |
                      A(6)                         G(6)
                 ----- -3 -----                  ---- 4 -------- 
                 |            |                  |             |
                 C(4)        D(2)               F(1)          I(3)
           ---- -4 -         -2              --- 3 ---         5
           |       |         / \             |       |        / \
           B(0)  C*(-3,4)D*(-2,2)E*(0,7)     NIL   H(4,-4) I*(5,3)J(6,-1)
          -5                                 2   
          / \                               / \
    A*(-5,6)B*(-4,0)                   F*(2,1) G*(3,6)

Давайте запустим пример запроса [-2:4] [1:inf] (или любой y >= 1)

• Начиная с корня, мы видим точку Е.
• Является ли y точки E (7) >= 1? Да.
• Находится ли x точки E (0) в [-2:4]? Да
• Добавьте E к выходу.
• Средняя точка (тоже 0) находится в диапазоне? Да
• От узла с буквой E нужно пройти в обе стороны.
• Сначала идем налево, видим точку А.
• Является ли y точки A (6) >= 1? Да.
• Находится ли x точки A(-5) в [-2:4]? Нет.
• Пропустить A, но продолжить движение (только проверка y останавливает перемещение).
• Находится ли средняя точка в точке A в диапазоне [-2:4]? Нет, это слева.
• Поскольку -3 ‹ [-2:4], нам нужно пройти только вправо. Теперь мы видим точку D.
• Является ли y точки D (2) >= 1? Нет! Пропустите точку и прекратите перемещение вниз, так как нет другой точки под D, которую мы НЕ вывели (обратите внимание, даже если E ниже D, E уже выведено, когда мы посетили корень в начале).
• Я иду вверх к А, так как нам не нужно идти по левому пути, продолжайте идти вверх.
• Теперь я снова в корне, который нужно пройти обоим. Поскольку мы только что пошли налево, мы идем направо. Там мы видим точку G
• Является ли y точки G (6) >= 1? Да
• Находится ли x точки G (3) в [-2:4]? Да
• Добавьте G к выходу, теперь у нас есть (E,G).
• Находится ли середина в точке G в пределах досягаемости? Да, нам придется пересечь обе стороны.
• Пойдем сначала налево. Мы видим Ф.
• Является ли y точки F (1) >= 1? Да
• Находится ли x точки F (2) в [-2:4]? Да
• Добавьте F к выходу, теперь у нас есть (E,F,G)
• Находится ли середина в F в [-2:4]? Да, нам придется пересечь обе стороны.
• Идём опять налево, видим... НИЛ. Ниже больше не нужно добавлять точки (поскольку мы уже проверили/добавили F,G раньше).
• Вернёмся к F и пройдём по правой стороне, увидим H.
• Y точки H (-4) >= 1? Нет. Не добавлять точку и останавливать перемещение.
• Возвращаемся к F, где уже пройдены оба пути.
• Мы возвращаемся к G, которому все еще нужно пройти правый путь.
• Мы идем по правой дорожке и видим I.
• Является ли y точки I (3) >= 1? Да
• Находится ли x точки I (5) в [-2:4]? Нет.
• Пропустить Ф.
• Находится ли средняя точка I в диапазоне [-2,4]? Нет, это больше.
• Поскольку он больше, нам нужно пройти только по левой стороне, так что давайте сделаем это.
• Трассируем вниз по левой стороне видим... опять я. Так как мы уже видели I, а это конечный узел, мы прекращаем обход и возвращаемся к I.
• Готово (не нужно проходить вправо). Вернитесь к Г.
• G сделано (обе стороны пройдены). ВЕРНИТЕСЬ обратно к Е.
• E сделано (обе стороны пройдены). Поскольку E является корневым узлом, мы закончили.

В результате "E,F,G" находятся в диапазоне.