Создание приоритетного дерева поиска с отсортированными координатами y за O (n) время - PullRequest
Новая
       9

Создание приоритетного дерева поиска с отсортированными координатами y за O (n) время

1 голос
/ 19 сентября 2019

Это проблема упражнения в книге «Вычислительная геометрия» «Марк де Берг, Отфрид Чеонг, Марк ван Кревельд, Марк Овермарс»

Глава 10 Упражнение 10.2:

Пусть P - набор из n точек на плоскости, отсортированных по y-координате.Покажите, что, поскольку P отсортирован, дерево поиска приоритетов точек в P может быть построено за O (n) времени.Диапазон запросов имеет вид (−∞: q x ] × [q y : q` y ].

Вот что я подумал об этом:

  1. Создайте полное двоичное дерево поиска (не сбалансированное двоичное дерево поиска) из этой точки. Это будет сделано в O (n) с точкиотсортировано по значениям y.

  2. Построение максимальной кучи с использованием подхода снизу вверх с использованием значений x. Опять при этом сделать значение y_mid узла равным y-значение его левого потомка.

Этот алгоритм имеет некоторые проблемы. Рассмотрим этот пример: после создания двоичного дерева мы имеем (игнорируем значение y_mid): 

                             (50/8)
               (58/4)                      (33/12)
        (70/2)       (81/6)         (39/10)       (31/14)
    (28/1) (22/3) (71/5) (90/7) (57/9) (27/11) (48/13) (86/15)

Это вывод после процесса сборки кучи: 

                             (22/3)
               (28/1)                      (27/11)
        (50/8)       (71/5)         (33/12)       (31/14)
    (58/4) (70/2) (81/6) (90/7) (57/9) (39/10) (48/13) (86/15)

Можно заметить, что узлы (50/8) и (71/5) нарушают приоритет распределения точек.медиана у родителя, слева значение y не может быть больше значения y справа. Аналогично для точек (58/4) и (70/2).

Мое решение по этому поводу.Пока строит кучу.Я сделаю обмен левого и правого ребенка, если они не в состоянии требуемой собственности.Я не уверен, работает ли это или нет.

Решение, которое мне нужно, основано на псевдокоде.

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

Я иду в правильном направлении?Если не то, что мне не хватает.

1 Ответ

0 голосов
/ 19 сентября 2019

Ответ заключается в создании сбалансированного бинарного дерева поиска следующим образом.Середина - это корень.Рекурсивно сгенерировать дерево слева и справа.Как этот непроверенный код. 

def make_tree (elements, left=None, right=None):
    if left is None:
        left = 0
    if right is None:
        right = len(elements) - 1

    middle = (left + right) // 2
    answer = Node(middle)
    if left < middle:
        answer.left = make_tree(elements, left, middle - 1)
    if middle < right:
        answer.right = make_tree(elements, middle + 1, right)
    return answer

Эта функция будет вызываться один раз для каждого элемента как middle, и каждый раз будет работать O(1).Так что это O(n).

...