如何證明從最小節點在BST中找到後繼n-1次是O（n）？

Question

如何證明從最小節點在BST中找到n-1次後繼是O（n）？

的問題是，我們可以通過

1創建排序順序）讓BST的節點=最低點。

2）從該節點，我們遞歸調用找到後繼者。

我被告知結果是O（n），但我不明白，不知道如何證明它。

它不應該是O（n * log n）嗎？因爲對於步驟1，它是O（log n），對於步驟2，它也是O（log n），但它被稱爲n-1次。因此，它將是O（n * log n）

請澄清我的疑問。謝謝！ :)

Answer 1

你是正確的，任何個人操作可能需要O（log n）時間，所以如果你執行這些操作n次，你應該得到O（n log n）的運行時間。這個界限是正確的，但它不是緊。實際運行時間爲Θ（n）。

看到這個的一種方法是查看樹中的任何單獨的邊。如果您從最左端的節點開始並重復執行後續查詢，您將訪問每個邊緣多少次？如果仔細觀察這些操作是如何運作的，你會發現每一條邊都被訪問過兩次：一次向下，一次向上。由於所做的所有工作都是遍歷上下邊緣，所以這意味着完成的工作總量與邊數的兩倍成比例。在任何樹中，邊的數量是節點數減1，所以完成的工作總數爲Θ（n）。

爲了將其作爲一個證明來形式化，試着展示你永遠不會在相同的邊緣下降兩次，並且當你爬上一條邊時，你再也不會下降到這條邊。一旦你完成了這個工作，運行時間爲Θ（n）的結論可以從上面的邏輯中得出。

希望這會有所幫助！

Answer 2

我想發表此評論templatetypedef的答案，但它太長。

他的答案是正確的，因爲看到這是線性的最簡單的方法是因爲每個邊緣只訪問兩次，並且樹的邊數總是比節點數少1個（因爲每個節點都有一個父母，除了根！）。

問題是，他用短語形式化證明的方式使用了似乎意味着矛盾的詞作爲出路。一般來說，數學家不喜歡使用矛盾，因爲它經常會產生帶有多餘內容的證明。例如：

Proof that 2 + 2 != 5: 
Assume for contradiction that 2 + 2 = 5 (<- Remove this line) 
Well 2 + 2 = 4 
And 4 != 5 
Contradiction! (<- Remove this line) 

矛盾往往是冗長的，有時它甚至會混淆證據背後的想法！有時候矛盾似乎是非常必要的，但這種情況相對較少，這是一個單獨的討論。

在這種情況下，我沒有看到矛盾的證據比直接證明更容易。另一方面，無論採用何種證明技術，這種證明在形式上都相當醜陋。這裏的企圖：

1）succ(n)算法遍歷的兩個路徑

• 在第一種情況每邊被訪問的簡單的路徑上從一個節點到它的右子樹的最左邊的節點的一個

• 在其他情況下，節點n無權孩子在這種情況下，我們上去祖先p_1, p_2, p_3, ..., p_k這樣p_(k-1)是始祖這是左孩子它的父。所有這些邊緣的被訪問的簡單路徑

我們希望顯示的任意邊緣的剛好兩個succ()通話遍歷，一次的succ()第一種情況下，一次針對的succ()第二種情況。那麼，除了最右邊的分支以外的每個邊緣都是如此，但是您可以分別處理這些邊緣情況。另外，我們可以證明我們參觀的最後一個元素

後返回根簡單的說法。這是因爲兩折的給定邊e我們必須找到n1和n2這樣succ(n1)穿越e和succ(n2)也穿越e，以及證明每隔一個succ()生成的路徑不包括e。

2）首先，我們實際上證明了爲每種類型的路徑的那個succ()訪問，沒有兩個路徑重疊（即，如果succ(n)和succ(n')相同類型的兩個移動路徑，這些路徑共用無毛邊）

• 在第一種情況下，簡單路徑的定義如下。從節點n開始，然後向右一邊移至r。然後遍歷以r爲根的子樹的左分支。現在考慮從其他節點n'（注意，我們不假設n != n'）開始的任何其他此類路徑。它必須右移一個節點到r'。然後它遍歷以r'爲根的子樹的最左邊的分支。如果路徑重疊，則選擇其中一個重疊的邊。如果它是(n,r) = (n',r')那麼我們有n = n'，所以它是相同的路徑。如果最左邊的分支中有一些e = e'，那麼您可以再次顯示n = n'（您可以跟蹤最左邊的分支並顯示每條邊相同，然後最終得出r = r' => n = n'的結論，因爲對於父樹是獨特的樹。下面會看到這個跟蹤參數）。因此我們知道，對於任何n和n'，如果它們的路徑重疊，它們實際上是相同的節點！對立說：如果它們是不同的節點，那麼它們的路徑不會重疊。這正是我們想要的（對於原始陳述而言，對立總是同樣真實的）。

• 在第二種情況下，我們定義了簡單的路徑開始節點n去了祖先p_1, p_2, ..., p_k = g直到我們到達的第一個節點p_k這樣p_(k-1)是的p_k左側。考慮從節點n'開始的相同類型的其他路徑，其中n != n'。同樣，它訪問p_1', p_2', ..., p_k' = g'。因爲它是一棵樹，所以這些祖先沒有一個與第一組相同。因爲沒有兩個路徑上的節點都是一樣的，沒有邊緣的可以是相同的，因此succ(n)和succ(n')不經過任何同邊的

3）現在我們只需要證明對於給定的邊緣至少存在一種類型的路徑。 （注意這裏我忽略了最右邊分支上的特殊邊緣，這些邊緣在技術上只訪問過一次，而且我也忽略了最左邊分支上的特殊邊緣，這些邊緣在技術上被find_min()訪問一次，然後一次被succ()調用）

• 如果從左子c其父p當時succ(c)將覆蓋第二類型的路徑。要找到其他路徑，請繼續向上p的祖先p_1, p_2, ..., p_k，使p_(k-1)位於p_k的右側。 succ(p_k)將按照定義遍歷包含e的路徑（因爲e位於p_(k-1)的子樹的最左邊的分支上，即p_k的右邊子節點）。

• 類似的論點適用於對稱的情況下，當c是p

右子總之，我們已經表明，succ()產生兩種路徑的證明。對於每種類型的路徑，這些類型的所有路徑不重疊。此外，對於任何邊緣，我們至少有一種類型的路徑。由於我們在上調用succ()每個節點我們可以最終得出結論每個邊都被遍歷了兩次（因此算法是Theta(n)）。

儘管證明有多長，但實際上並不完整（即使我明確表示我正在跳過細節，甚至忽略了這些要點！）。有些情況下，我說沒有證明存在的東西存在。如果你願意的話，你可以弄清楚這些細節，並且它確實令人滿意（至少在我看來，也許當你是一個天才時，你會發現它很乏味，嘿）

希望這有幫助。讓我知道你是否想讓我澄清一些步驟