题目内容
（请给出正确答案）
[主观题]
在一棵表示有序集S的二又搜索树中，任意一条从根到叶结点的路径将S分为3部分：在该路径左边结点
中的元素组成的集合S1在该路径上的结点中的元素组成的集合S2;在该路径右边结点中的元素组成的集合S3。S1∪S2∪S3。若对于任意的S2，c∈E3，是否总有a≤h≤c？为什么？
查看答案
如果结果不匹配，请 联系老师 获取答案
题目内容
（请给出正确答案）
如果结果不匹配，请 联系老师 获取答案
题目内容
（请给出正确答案）
如果结果不匹配，请 联系老师 获取答案
更多“在一棵表示有序集S的二又搜索树中，任意一条从根到叶结点的路径…”相关的问题
所谓半无穷范围查询(semi-infinite range query)，是教材8.4节中所介绍一般性范围查询的特例，具体地，这里的查询区域是某一侧无界的广义矩形区域，比如R=[-1，+1]x[0，﹢∞)，即是对称地包含正半y坐标轴、宽度为2的一个广义矩形区域，当然，对查询的语义功能要求依然不变——从某一相对固定的点集中，找出落在任意指定区域R内部的所有点。
范围树(176页习题[8-20])稍作调整之后，固然也可交持半无穷范围查询，但若能针对这一特定问题所固有的性质，改用优先级搜索树(priority search tree，PST)之类的数据结构，则不仅可以保持O(r+logn)的最优时间效率，而且更重要的是，可以将空间复杂度从范围树的O(nlogn)优化至O(n)。
如图x10.3所示，优先级搜索树除了首先在拓扑上应是一棵二叉树，还同时遵守以下三条规则。
①首先，各节点的y坐标均不小于其左右孩子(如果存在)——因此，整体上可以视作为以y坐标为优先级的二叉堆。
②此外，相对于任一父节点，左子树中节点的x坐标均不得大于右子树中的节点。
③最后，互为兄弟的每一对左、右子树，在规模上相差不得超过一。
a)试按照以上描述，用C/C++定义并实现优先级搜索树结构;
b)试设计一个算法，在O(nlogn)时间内将平面上的n个点组织为一棵优先级搜索树;
c)试设计一个算法，利用已创建的优先级搜索树，在O(r+logn)时间内完成每次半无穷范围查询，其中r为实际命中并被报告的点数。
图7中所示的无向图G中，实线边所表示的子图为G的一棵生成树T。
(1)求G对应T的所有基本回路。
(2)求G对应T的所有基本割集。
A、h-1
B、h
C、h+1
D、h+2
解决问题的一种方法是使用2-d树。2-d树类似于二叉搜索树，不同之处在于：
◇偶数层用keyl来比较：在该层上每一结点的keyl都大于共左子树中任一结点的key1，都不大于其右子树中任一结点的keyl。
◇奇数层用key2来比较：在该层上每一结点的key2都大于其左子树中任一结点的key2，都不大于其右子树中任一结点的key2.
◇树的根结点处于第0层。每次插入或搜索都从根结点出发，逐层比较。新结点应作为叶结点插入，
臂如，可以将不同人的姓和名(假设没有同名同姓者)分别为keyl和key2，建立一棵2-d树.作为例子，图7-27就是将清华大学的历任校长，按共任职年代的先后次序(周白齐、唐国安、周春、金邦正、曹云祥、严鹤龄、罗家伦、梅贻琦、叶企孙、蒋南翔、高景德、张孝文、王大中、顾秉林)，顺序插人而形成的一棵2-d树。
(1)若命名树结点的类名为kdTNode，树的类名为kdTrce，关键码keyl的数据类型为T1，关键码key2的数据类型为T2，试写出2-d树的模板类结构定义，包括构造函数、复制构造函数、求树高、按给定值搜索、查找左子女、查找右子女、查找父结点、插人、删除等函数。此外，还要定义对树结点私有数据成员的存取函数(只要求写出函数的原型，不必给出代码实现)。
(2)基于上述定义，写出其中一个成员函数的实现代码：从根开始搜索关键码keyl和
key2与给定值vall和val2匹配的结点。函数的形式为：
若搜索成功，则函数返回true值，同时引用参数pt指向搜索到的结点，另引用参数pr指向结点*pt的父结点。此时，若树中只有一个结点，pr为NULL。
若搜索不成功或树为空，则函数返回false值，同时参数pt为NULL，在树非空时，pr则指向搜索失败前指针pt最后到达的结点;当树为空时，pr为NULL。
A、h+1
B、2h+1
C、3h+1
D、4h+2
