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)，如果實現了我所描述的方式。