优先搜索树 | Codeboy's Blog

形式陈述

两条不变量

给定有限平面点记录集 $P$ ，每点有唯一 ID 处理坐标重复。空集用空树表示，查询以 $O(1)$ 时间返回空；以下复杂度针对 $n\ge1$ 。本页静态 Priority Search Tree 是一棵二叉树，同时维护：

y-heap：按 y 的最小堆序，每个节点存当前子集 y 最小的点，故子树任一点的 y 不小于根点 y。
x-search decomposition：借鉴二叉搜索树的有序分解，但不要求节点点值满足普通 BST 中序不变量；移除根点后，按键 $\kappa=(x,\mathrm{id})$ 的中位顺序统计量划分剩余记录，存分割键 split，左侧 $\kappa\le split$ ，右侧 $\kappa>split$ ，并递归构造。两侧规模相差至多一；没有剩余记录时为叶。

这里的堆序只限制 y，不要求二叉堆的完全树形，也不执行其 sift 操作。节点本身的 x 不必位于左右点之间；搜索依据的是 split 和子树 x 范围，而不是把所有存储点按中序排成普通 BST。树高 $O(\log(n+1))$ ，每点只存一次，空间 $O(n)$ 。

三边查询

本页查询

Q=[x_1,x_2]\times(-\infty,y_0].

把闭 x 区间转为键区间 $[(x_1,-\infty),(x_2,+\infty)]$ ，其中无穷标签只作比较哨兵，不是数据 ID。沿 split 分割寻找两端的分叉节点时，共同路径上的每个节点自身点也要按原 x、y 条件检查并报告；到达分叉后，再分别检查两条边界路径上的节点点。每当一棵兄弟子树的完整 x 范围落入 $[x_1,x_2]$ ，调用 heap-report。

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

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

最坏时间报告 $k$ 个点。对这里的直接静态构造，先按 $(x,\mathrm{id})$ 排序，每个递归子集扫描最小 y、移除该点并按剩余秩分半，每层总工作 $O(n)$ ，总构建时间 $O(n\log(n+1))$ 。不能从“已经排序”就省略各层最小值与分割工作。

直觉

x 中位分解把查询横向区间切成少量规范子树，y 最小堆序则让根点一旦高过上界，整棵子树都可剪掉。两种秩序分别负责定位与输出敏感剪枝，因此节点存储点的 x 不必像普通 BST 那样满足中序关系。

优先搜索树同时按 x 中位数切分并保持 y 最小堆序 — 优先搜索树的双重不变量

例子与边界

五点真例

设

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

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

[2,5]\times(-\infty,3]

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

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

共同搜索路径不能漏掉节点点

取 $P=\{(0,0),(-4,5),(-3,6),(1,7),(2,8)\}$ 。根存 $(0,0)$ ，剩余四点可在 $x=-3$ 处分成两半。查询 $[0,0]\times(-\infty,0]$ 的两个端点都会沿 split 走向右子树，但唯一答案恰在根。如果寻找分叉时像普通 BST 一样只走指针、跳过共同路径的点检查，就会错误返回空集；后面的 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按搜索键形成 BST，并以独立随机优先级保持期望平衡；优先级不属于输入几何坐标。PST 的 y 是数据本身，堆序用于范围剪枝，而平衡来自 x 中位分解，不是随机性。

Range Tree用 $O(n\log n)$ 空间支持一般二维矩形报告；PST 用 $O(n)$ 空间换取三边查询。正交范围查询中的 reporting、counting 与 emptiness 也应分开， $O(\log(n+1)+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.

形式陈述 ​

两条不变量 ​

三边查询 ​

五点真例 ​

共同搜索路径不能漏掉节点点 ​

重复坐标与边界 ​

与 Treap、Range Tree 的区分 ​