如果结果不匹配，请 
更多“从根算起，树可以分为多个层次，树的_____称为树的深度。”相关的问题
为提高空间利用率，可将内部节点的分支数下限从[m/2]提高至[2m/3]。于是，一旦节点v发生上溢且无法通过旋转完成修复，即可将v与其(已经饱和的某一)兄弟合并，再将合并节点等分为三个节点，采用这一策略之后，即得到了B-树的一个变种，称作B'-树(B'-tree)。
当然，实际上不必真地先合二为一，再一分为三。可通过更为快捷的方式，达到同样的效果：从来自原先两个节点及其父节点的共计m+(m-1)+1=2m个关键码中，取出两个上交给父节点，其余2m-2个则尽可能均衡地分摊给三个新节点。
a)按照上述思路，实现B'-树的关键码插入算法;
b)与B-树相比，B'-树的关键码删除算法又有何不同？
A、根结点至多有m棵子树
B、所有叶结点都在最低的两个层次上
C、非失败结点至少有m/2(m为偶数)或m/2+1(m为奇数)棵子树
D、根结点中的数据是有序的
A.树可以看作图的特例
B.树中有一个特殊的元素(根)，而图中每个元素的“地位”是一样的
C.图和树中的边沿任意轴旋转后，各元素间的逻辑关系保持不变
D.树中任意两个元素间有唯一的简单路径，而图中任意两个元素间可能有零或多条简单路径
范围查询的另一解法需要借助范围树(range tree)。
为此，首先仿照如图8.37(教材240页)和图8.38(教材241页)所示的策略，按x坐标将平面上所有输入点组织为一棵平衡二叉搜索树，称作主树(main tree)。
于是如图x8.10(a)和(b)所示，该树中每个节点各自对应于一个竖直的条带区域;左、右孩子所对应的条带互不重叠，均由父节点所对应的条带垂直平分而得;同一深度上所有节点所对应的条带也互不重叠，而且它们合并后恰好覆盖整个平面。
接下来，分别对于主树中每一节点，将落在其所对应条带区域中的输入点视作一个输入子集，并同样采用以上方法，按照y坐标将各个子集组织为一棵平衡二叉搜索树，它们称作关联树(associative tree)。于是如图x8.10(a)和(c)所示，每棵关联树所对应的竖直条带，都会进而逐层细分为多个矩形区域，且这些矩形区域也同样具有以上所列主树中各节点所对应条带区域的性质，至此，主树与这o(n)棵关联树构成了一个两层的嵌套结构，即所谓的范围树。
利用范围树，可按如下思路实现高效的范围查询，对于任一查询范围R=[x1，x2]×[y1，y2]，首先按照[x1，x2]对主树做一次×方向的范围查询。根据8.4.1节的分析结论，如此可以得到o(logn)个节点，而且如x8.10(b)所示，它们所对应的竖直条带互不重叠，它们合并后恰好覆盖了x坐标落在[x1，x2]范围内的所有输入点。
接下来，深入这些节点各自对应的关联树，分别按照[y1，y2]做一次y方向的范围查询。如此从每棵关联树中取出的一系列节点，也具有与以上取自主树的节点的类似性质，具体地如图x8.10(c)所示，这些节点所对应的矩形区域互不重叠，且它们合并之后恰好覆盖了当前竖直条带内y坐标落在[y1，y2]范围内的所有输入点。换而言之，这些点合并之后将给出落在R中的所有点，既无重也不漏。
a)试证明，如此实现的范围树，空间复杂度为o(nlogn);
b)按照以上描述，试利用你的范围树实现新的范围查询算法;
c)试证明，以上范围查询算法的时间复杂度为O(r+log2n)，其中r为实际命中并被报告的点数;
d)继续改进以上范围树，在不增加空间复杂度的前提下，将查询时间减至O(r+logn)。
解决问题的一种方法是使用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。
