BST树形运行时间

Question

我有一个伪代码：

function func(BST t): 
    x = MIN(t) 
    for i=1..n do: 
     print x.key 
     x = SUCCESSOR(x) 

现在，我需要证明它的运行过程中出现的时间是THETA（N）。 但是，我知道SUCCESSOR的运行时间是O（logn），因此运行时间是O（nlogn）。 我的错在哪里？

预先感谢...

Answer 1

有两种可能性：

• 这不是真的，运行时间为O(nlogn)
• 你知道确切实施的继任者，它有上界对数的复杂性（如指出，O(logn)）但是你可以推断，当它一个接一个地执行时，它实际上退化为theta(1)。事实上，在BST中SUCCESSOR的良好实施应该具有分解theta(1)的复杂性，因为在执行整个func期间将访问每个节点最多两次两次。

Answer 2

这真的取决于您BST的实施，但如果你的BST持有“父”节点，并用它来寻找继任者，它需要穿越每个边缘最多两次 - 一旦你去“下”，第一次到达节点，和一个当你“上”，从它回来。

由于树有n-1边缘，你得到最2*(n-1)边沿数量看，这是O(n)。

注意，的确是SUCCESSOR()功能的最坏情况是O(logn)，但平均情况O(1)，如果实现了我所描述的方式。