如何在二叉搜索樹上證明這一操作？

Question

我想讓你給我一個提示，以證明Cormen一書中的這個練習： 「證明無論我們在一個高度爲h的二叉搜索樹中開始什麼節點，都要連續調用TREE-SUCCESSOR採取O（K + H）時間。「

Answer 1

• 讓x是起始節點和z是後k連續調用樹繼任結束節點。
• 讓p是x和z（含）之間的簡單路徑。
• 讓y成爲x和z的共同祖先即p訪問。
• 的p的長度至多爲2h，這是O(h)。
• 讓output是元素的值是x.key和z.key（含）之間。
• output的大小是O(k)。
• 在k連續調用樹的繼任者， 是在p節點的執行被訪問， 再說節點x，y和z， 如果p節點的子樹被訪問，那麼所有其元素在output。
• 所以運行時間是O(h+k)。

Answer 2

提示：制定一個小例子，觀察結果，嘗試推斷原因。

要開始，這裏有一些事情要考慮。

從某個節點開始，k成功接收Tree-Succcesor構造的一棵樹。此步行訪問有多少（至少和最多）節點？ （提示：考慮關鍵（x））。請記住，最多訪問兩次邊緣（爲什麼？）。

最後提示：結果爲O(2h+k)。