这是"Mark de Berg， Otfried Cheong， Marc van Kreveld， Mark Overmars"的"计算几何"书中的一个练习题
第 10章 练习 10.2：
设 P 是平面中的一组 n 个点，按 y 坐标排序。显示 因为 P 是排序的，所以 P 中点的优先级搜索树可以是 在O(n(时间内构建。范围查询的形式为 (−∞ ： qx] × [q y ：q'y]。
以下是我对此的看法：
从这些点创建一个完整的二叉搜索树(不是平衡的二叉搜索树(。这将在 O(n( 中完成，因为点基于 y 值排序。
通过使用 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( 点。
我的解决方案。 在构建堆时。如果他们未能获得所需的属性，我将交换左右孩子。我不确定这是否有效。
我需要的解决方案是基于伪代码的。
如果我想实现这一点，使用基于数组的样式交换这个左右指针的堆将是困难的。
我走对了方向吗？如果不是，我错过了什么。
答案是创建一个平衡的二叉搜索树，如下所示。 中点是根。 递归生成左侧和右侧的树。 就像这个未经测试的代码一样。
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).