7

我需要 CLRS Algorithms 书中关于这个练习的提示：

证明无论我们从高度为 h 的二叉搜索树中的哪个节点开始，对 Tree-Successor 的k次连续调用都需要O(k+h)时间。

4

2 回答 2

8
  • 在对 TREE-SUCCESSOR 的连续调用之后，让x成为开始节点并z成为结束节点。k
  • 让成为和包容p之间的简单路径。xz
  • 让我们y成为x和z那次p访问的共同祖先。
  • 的长度p最多为2h，即O(h)。
  • 让output是它们的值介于x.key和z.key包含之间的元素。
  • 的大小output为O(k)。
  • 在k对 TREE-SUCCESSOR 的连续调用的执行中，访问了 in的节点，p并且除了节点和，如果访问了节点 in 的子树，则其所有元素都在 in 。xyzpoutput
  • 所以运行时间为O(h+k)。
于 2012-09-15T18:38:39.520 回答
3

提示：做一个小例子，观察结果，尝试推断原因。

要开始，这里有一些事情需要考虑。

从某个节点开始，对 Tree-Succcesor 的 k 次连续调用构成了部分树遍历。这次步行访问了多少（至少和最多）节点？（提示：想想key(x)）。请记住，一条边最多被访问两次（为什么？）。

最后提示：结果是O(2h+k).

于 2011-12-10T06:04:02.160 回答