如果以這種方式實現BST inorder遍歷的時間複雜度

Question

那麼通常如果使用深度優先遍歷，我們得到O(n)時間。但是，如果我們先找到最小元素，那麼調用successor()方法n次，它會是什麼時間複雜度？

我認爲這可能是O(n log n)，因爲繼任者是O(log n)但這看起來不正確。任何人都可以在這裏提供任何深入分析（可能涉及一些限制分析）？

Answer 1

如果每個節點都存在父指針，則調用n次後繼方法需要O（n）個時間。通過組合所有後續調用，可以看到樹中的每個邊緣最多訪問過兩次（從父到子，從子到母）。因此，所有後繼呼叫訪問的邊緣總數最多爲2n。所以運行時間是O（n）。

現在，如果父指針不存在，那麼在每次調用中，我們都必須從根開始，並通過遍歷O（log n）個節點（如果樹是平衡的）搜索後繼元素。所以複雜度變爲O（n log n）。

Answer 2

不太正式的說法，但相當有說服力的一個O（N）：

後繼功能始終從起始節點到其繼任者的最短路徑。它要麼下降要麼是升高，但一旦它開始做一個，它就不能改變到另一個。因此它必須走最短的路徑。

後繼函數必須產生與深度優先方法相同的輸出，因此它必須以相同的順序訪問相同的節點（即輸出的節點，它不必經過相同的節點，雖然它）。

深度優先方法也總是採用每個輸出節點之間的最短路徑（在每個步驟中，它向下或向上，而不是兩者）。

因此，每種方法都採用完全相同的路徑，實際上等價。