是否证明了在二叉树中重复调用successor（）的效率？ [英] Prove the efficiency of repeated calls to successor() in binary trees?

问题描述

我需要《 CLRS算法》一书中的这个练习的提示：

I need a hint for this exercise from the CLRS Algorithms book:

证明无论我们从高处开始于哪个节点-h二进制搜索树，对Tree-Successor的 k 连续调用需要 O（k + h）时间。

推荐答案

• 让 x 为起始节点，而 z 是 k 连续调用TREE-SUCCESSOR之后的结束节点。


• 让 p 是 x 和 z 之间的简单路径。


• 让 y 为 x 和的共同祖先z 访问 p 。


• p 最多为 2h ，即 O（h）。


• 让 output 成为它们的值在 x.key 和 z之间的元素。键。


• 输出的大小为 O（k）。


• 在执行 k 个连续调用TREE-SUCCESSOR的过程中，
  个位于 p ，
以及节点 x ， y 和 z ，
如果访问了 p 中某个节点的子树，则其所有元素都在输出中。


• 因此运行时间为 O（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).

这篇关于是否证明了在二叉树中重复调用successor（）的效率？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！