请输入或粘贴题目内容
搜题
拍照、语音搜题，请扫码下载APP
题目内容
（请给出正确答案）
可将算法的时间复杂度降低到O(nlog2n)，算法的思想是对于关键码序列(keylow，keylow+1，…，keyhigh)，轮流以keyk为根，k=low，low+1，…，h，求使得|W[low-1][k-1]-W[k][high]|达到最小的k，用keyk作为由该序列构成的拟最优二叉搜索树的根。然后对以keyu为界的左子序列和右子序列，分别施行同样的操作，建立根keyk的左子树和右子树，试编写一个函数，实现上述试探算法。要求该函数的时间复杂度应为O(nlog2n)。
答案
更多“求最优二叉搜索树算法的时间复杂度为O(n2)，下面给出一个求拟最优二叉搜索树的试探算法，”相关的问题
第2题
第3题
所谓半无穷范围查询(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为实际命中并被报告的点数。
第4题
二叉搜索树中，然后对树进行中序遍历，并将元素按序放人数组a中，为简单起见，假设a中的数据互不相同。试编写一个函数，从一棵二叉搜索树中删除最大元素。要求函数的时间复杂性必须是O(h)，其中h是二叉搜索树的高度。
第5题
范围查询的另一解法需要借助范围树(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)。
第8题
第9题
A.i≤r≤j
B.i
C.i≤r
D.i
第11题
