优先级搜索树：PST构建与应用解析

"优先级搜索树是一种数据结构，用于在二维平面上进行范围查询，特别是针对半无限范围查询的问题。这种数据结构由E. M. McCreight在1985年发明，它结合了二叉堆和二叉搜索树的特性，因此也被称为树堆。在优先级搜索树中，每个节点的y坐标都大于其左右子节点（如果存在），并且对于任何父节点，其左子树中的节点x坐标小于右子树中的节点。此外，相邻的左、右子树在规模上最多相差1。这样的设计使得在O(r + logn)的时间内可以完成范围查询，并且空间复杂度仅为O(n)。 在C/C++中实现优先级搜索树，需要定义一个结构体来表示节点，包括x和y坐标以及指向左右子节点的指针。同时，还需要实现插入节点、删除节点、查找范围内的节点等基本操作。为了构建一棵优先级搜索树，首先可以按照x坐标对所有点进行排序，然后采用递归的方式，选择y坐标最大的点作为根节点，接着将剩余的点根据x坐标划分到左右子树，分别对子树进行递归构造。这样整个构造过程的时间复杂度是O(nlogn)。 邓俊辉教授的《数据结构不算法·习题解》提供了相关的习题和解答，指导读者如何理解和实现优先级搜索树。这本书是由清华大学出版社出版，2015年9月发行，作为985名优教材立项资助的一部分，对于学习数据结构和算法的读者具有很高的参考价值。书中详细解答了各种习题，包括优先级搜索树的构造和操作，帮助读者深入理解这种高效的数据结构及其应用。"