我怎么能证明这工作在二叉搜索树？

问题描述：

我要你给我一个提示，以证明这项工作从Cormen的书：证明，无论什么节点，我们开始在一个高度小时二叉搜索树，K 连续调用树后继需要O（K + H）的时间。

I'd want you to give me a hint to prove this exercise from the book of Cormen: "Prove that no matter what node we start at in a height-h binary search tree, k successive calls to TREE-SUCCESSOR take O(k+h) time."

答

让 X 是起始节点和以Z 是后结束节点 K 连续调用树的继任者。
让 P 介于的简单路径X 和以Z 的包容性。
让是是的共同祖先X 和以Z 的 P 探访。
P 的长度最多为 2小时，这是 0（H） 。
让输出是元素，它们的值之间的 x.key 和ž .KEY 的包容性。
输出的大小是 O（K）。
在 K 连续调用树的继任者执行，这是 P 的节点访问，另外该节点 X ，是和以Z ，如果一个节点的 P 被访问它所有的元素都在输出。
所以运行时间 0（H + K）。

Let x be the starting node and z be the ending node after k successive calls to TREE-SUCCESSOR.
Let p be the simple path between x and z inclusive.
Let y be the common ancestor of x and z that p visits.
The length of p is at most 2h, which is O(h).
Let output be the elements that their values are between x.key and z.key inclusive.
The size of output is O(k).
In the execution of k successive calls to TREE-SUCCESSOR, the nodes that are in p are visited, and besides the nodes x, y and z, if a sub tree of a node in p is visited then all its elements are in output.
So the running time is O(h+k).

我怎么能证明这工作在二叉搜索树？

相关推荐