Путаница в дереве поиска приоритетов
Единственный разумный набор слайдов, который я нашел, это то, что на странице 15 говорит, для построения:
- Сортируйте все точки по их значениям координаты x и сохраните их в конечных узлах сбалансированного двоичного дерева (т. Е. Дерева диапазонов)
- Начиная с корня, каждый узел содержит точку в своем поддереве с максимальным значением для его координаты y, которое не было сохранено
на меньшей глубине в дереве; если такого узла не существует, то узел
пустой
Я реализовал Range Range непосредственно перед этим, поэтому на основе примера, который я там использовал, теперь у меня есть (для дерева поиска приоритетов):
7
------ 0 ---------------------
| |
6 6
---- -3 ---- ---- 4 ------
| | | |
4 2 1 3
---- -4 - -2 --- 3 --- 5
| | / \ | | / \
0 (-3,4) (-2,2)(0,7) NIL (4,-4) (5,3)(6,-1)
-5 2
/ \ / \
(-5,6) (-4,0) (2,1) (3,6)
Здесь каждый внутренний узел имеет форму:
mid_x
max y
и запрос диапазона, который я задаю, равен (-inf, 1) x (-0,5, 5), т. е. (x_low, x_high) x (y_low, y_high).
- Итак, давайте начнем с корня, я проверяю, находится ли x (=0) в (-inf, 1) и если 7 > (-0,5, 5). Это так, поэтому я поступаю с обоими детьми, но для простоты позвольте мне следовать за левым (во всех случаях с этого момента).
- Я проверяю, равен ли -3 диапазон x, и равен ли 6 больше или равно верхней границе диапазона y запроса (т. Е. 5). Это так, я продолжаю.
- То же самое для следующего уровня, поэтому мы переходим на следующий уровень и теперь, пожалуйста, сосредоточимся на этом внутреннем узле. Он имеет значение max y a 0, что указывает на то, что max y поддерева равно 0, что неверно (левый дочерний элемент равен (-5, 6))*.
Чего мне не хватает в процессе сборки / поиска?
Другими словами:
Проверьте крайнюю левую ветвь дерева; это как max_y значения (2-й пункт в цитате), 7, 6, 4, 0.
Но не является ли это значение тем, которое указывало максимальное значение y, хранящееся в поддереве под внутренним узлом? Если это так, это не относится к 0 и указать (-5, 6) (6 не используется, так как используется на 2-м уровне).
*Определенный запрос, который я задаю, может быть не поврежден этим, но другой может.
1 ответ
Ваша последняя логика на самом деле все еще верна. Значение (-5,6) должно быть уже подобрано, когда вы нажмете на узел, который вы пометили (6,-3). Теперь я не математик. Но общая идея такова. В дереве Приоритетного поиска, который вы внедрили, вы выполняете поиск по двум отдельным критериям. Для х это простой двоичный поиск диапазона. Для 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 < РЕДАКТИРОВАТЬ для очень, очень длинного текста: давайте разберем ваш пример. Я сделал дополнительную аннотацию, помечая каждую точку буквой ("имя" точки). Теперь у каждого узла есть формат имени точки, с его значением y в круглых скобках и "средним диапазоном" x ниже него. Для конечных узлов те, у которых есть "*", означают, что они уже назначены где-то вверх по дереву и должны рассматриваться как NIL, если вы когда-либо достигнете их. Давайте запустим пример запроса [-2:4] [1:inf](или любого y >= 1) Результат "E,F,G" находятся в диапазоне. 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)