优先搜索树

两条不变量 ​

给定平面点集 $P$，先假设每点有唯一 id 处理坐标重复。Priority Search Tree 同时维护：

1. y-heap：每个节点存当前子集 y 最小的点，故子树任一点的 y 不小于根点 y。
2. x-search decomposition：移除根点后，以剩余点的 x 中位数 split 划分左右子集，左侧 $x\le split$，右侧 $x>split$，并递归构造。

节点本身的 x 不必位于左右点之间；搜索依据的是 split 和子树 x 范围，而不是把所有存储点按中序排成普通 BST。树高 $O(\log n)$，每点只存一次，空间 $O(n)$。

三边查询 ​

本页查询

$$Q=[x_1,x_2]\times (-\mathrm{\infty },y_0].$$

先沿 x 分割找到 $x_1,x_2$ 的 split node。对两条边界路径，检查路径节点自身点；每当一棵兄弟子树的完整 x 范围落入 $[x_1,x_2]$，调用 heap-report。

Heap-report 查看子树根：若根 y 已大于 $y_0$，由最小堆序可剪掉整棵子树；否则报告根点，并递归两个孩子。除边界的 $O(\log n)$ 路径外，每个展开节点都会输出一个点，因此

$$O(\log n+k)$$

最坏时间报告 $k$ 个点。静态树可在预排序后线性或 $O(n\log n)$ 构建，取决于输入和中位数实现；成本需另报。

五点真例 ​

设

$$P=\{(1,5),(2,1),(3,4),(4,2),(5,6)\}.$$

根保存全局最小 y 点 $(2,1)$，其余点按 x 中位数分给左右子树。查询

$$[2,5]\times (-\mathrm{\infty },3]$$

报告 $(2,1)$ 与 $(4,2)$。含 $(3,4)$ 的子树若根最小 y 已大于 $3$，会整体剪掉；算法不需逐点比较全部五项。

若查询上界改为 $y_0=5$，答案会新增 $(3,4)$；点 $(1,5)$ 虽满足 y 上界，却因 x 不在 $[2,5]$ 而不会被报告。只有 x 规范子树与边界路径中的合法点才可进入 heap-report。

重复坐标与边界 ​

相同 x 用 (x,id) 全序分到唯一侧，查询边界再按原 x 判断；相同 y 不影响非严格堆序。若省略 tie-breaking，中位分割可能把同一逻辑点重复放入两侧。

结构专为一侧 y 无界的 3-sided reporting。一般四边矩形 $[x_1,x_2]\times [y_1,y_2]$ 同时有 y 下界，单纯最小堆无法剪掉“太小”的点；需 range tree、分层 PST 或其他额外结构。

与 Treap、Range Tree 的区分 ​

Treap公理库Treap 与随机优先级搜索树treap · randomized search tree同时满足键的搜索树序和独立随机优先级堆序的随机平衡树。按搜索键形成 BST，并以独立随机优先级保持期望平衡；优先级不属于输入几何坐标。PST 的 y 是数据本身，堆序用于范围剪枝，而平衡来自 x 中位分解，不是随机性。

Range Tree公理库范围树range tree以主坐标搜索树和节点关联目录支持固定维正交范围查询。用 $O(n\log n)$ 空间支持一般二维矩形报告；PST 用 $O(n)$ 空间换取三边查询。正交范围查询公理库正交范围查询Orthogonal range searching在固定维点集中对轴对齐盒执行报告、计数、判空或聚合查询。中的 reporting、counting 与 emptiness 也应分开，$O(\log n+k)$ 不等于常数时间计数。

参考资料

• Edward M. McCreight, “Priority Search Trees,” SIAM Journal on Computing 14(2), 1985.
• Mark de Berg et al., Computational Geometry: Algorithms and Applications, 3rd ed., Springer, 2008.
• Pankaj K. Agarwal and Jeff Erickson, “Geometric Range Searching and Its Relatives,” 1999.