algorithm - 在 O(n) 时间内用排序的 y 坐标制作优先搜索树

Question

这是“Mark de Berg, Otfried Cheong, Marc van Kreveld, Mark Overmars”的《计算几何》一书中的习题

第 10 章练习 10.2:

Let P be a set of n points in the plane, sorted on y-coordinate. Show that, because P is sorted, a priority search tree of the points in P can be constructed in O(n) time. Range queries are of the form (−∞ : 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) 分也是如此。

我对此的解决方案。在构建堆时。如果他们不符合要求的属性(property)，我将交换左右 child 。我不确定这是否有效。

我需要的解决方案是基于伪代码的。

如果我想实现，基于数组样式的堆交换左右指针将很困难。

我的方向是否正确？如果不是，我错过了什么。

Answer 1

答案是创建一个平衡的二叉搜索树，如下所示。中点是根。递归生成左右两边的树。喜欢这个未经测试的代码。

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

此函数将在每个元素作为中间时被调用一次，并且每次都执行O(1)。所以它是O(n)。