设二叉搜索树中的关键码互不相同，则其中的最小元素必无左子女，最大元素必无右子女，此命题是否正确？最小元素和最大元素一定是叶结点？一个新元素总是作为叶结点插入二叉搜索树吗？

查看答案

如果结果不匹配，请联系老师获取答案

您可能会需要：

重置密码查看订单联系客服

安装优题宝APP，拍照搜题省时又省心！

更多“设二叉搜索树中的关键码互不相同，则其中的最小元素必无左子女，…”相关的问题

第1题

范围查询的另一解法需要借助范围树（range tree)。为此，首先仿照如图8.37（教材240页)和图8.38（教

范围查询的另一解法需要借助范围树(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=[x₁，x₂]×[y₁，y₂]，首先按照[x₁，x₂]对主树做一次×方向的范围查询。根据8.4.1节的分析结论，如此可以得到o(logn)个节点，而且如x8.10(b)所示，它们所对应的竖直条带互不重叠，它们合并后恰好覆盖了x坐标落在[x₁，x₂]范围内的所有输入点。

接下来，深入这些节点各自对应的关联树，分别按照[y₁，y₂]做一次y方向的范围查询。如此从每棵关联树中取出的一系列节点，也具有与以上取自主树的节点的类似性质，具体地如图x8.10(c)所示，这些节点所对应的矩形区域互不重叠，且它们合并之后恰好覆盖了当前竖直条带内y坐标落在[y₁，y₂]范围内的所有输入点。换而言之，这些点合并之后将给出落在R中的所有点，既无重也不漏。

a)试证明，如此实现的范围树，空间复杂度为o(nlogn);

b)按照以上描述，试利用你的范围树实现新的范围查询算法;

c)试证明，以上范围查询算法的时间复杂度为O(r+log²n)，其中r为实际命中并被报告的点数;

d)继续改进以上范围树，在不增加空间复杂度的前提下，将查询时间减至O(r+logn)。

点击查看答案

第2题

在最优二叉搜索树问题中，定义e[i,j]为ki,kj的最优二叉查找树的期望搜索成本，而我们需要通过寻优来确定最优二叉查找树的根结点的下标r,则r的取值范围为（)。

A.i≤r≤j

B.i

C.i≤r

D.i

点击查看答案

第3题

试证明：a)按照二叉搜索树的基本算法在AVL树中引入一个节点后，失衡的节点可能多达Ω（logn)个;b)按照二叉搜索树的基本算法从AVL树中摘除一个节点后，失衡的节点至多1个。

点击查看答案

第4题

试证明，采用BST::remove（)算法（教材198页代码7.6)从二叉搜索树中删除节点，若实际被删除的节点为x，则此后：a)除x的历代祖先以外，其余节点的高度无需更新;b)祖先高度不会增加，但至多减一;c)一旦某个祖先高度不变，更高的祖先也必然高度不变。d)利用以上事实，进一步改进updateHeightAbove（)方法，提高效率。

点击查看答案

第5题

若输入的有序序列S₁和S₂以平衡二叉搜索树（而非序列)的方式给出，则：a)如教材344页代码12.8和346页代码12.9所示的两个median（)算法，分别应做哪些调整？b)调整之后的计算效率如何？

点击查看答案

第6题

最优二叉搜索树是指___________为最小的二叉搜索树。

点击查看答案

第7题

试用判定树的方法给出在中序线索二叉树上：(1)如何搜索指定结点的在中序下的后继。(2)如何搜索指定结点的在前序下的后继。(3)如何搜索指定结点的在后序下的后继。

试用判定树的方法给出在中序线索二叉树上：（1)如何搜索指定结点的在中序下的后继。（2)如何搜索指定结点的在前序下的后继。（3)如何搜索指定结点的在后序下的后继。

点击查看答案

第8题