證明/解釋算法的時間複雜度爲O（h + k）

Question

證明/解釋給定算法的時間複雜度爲O（h + k）。其中h是樹的高度，k是x和y（含）之間的節點數。

我知道，如果k = 0（範圍內沒有項目），那麼它的算法只是遍歷樹的高度，因此O（h）。我也知道一個節點是否在它的兩個孩子的範圍內，而不是其中的一個。但是這似乎有倍增效果，所以我很困惑如何證明/解釋這個。

INRANGE-TREE-WALK (v, x, y) 
    if v != NIL 
    if v.key < x 
     INRANGE-TREE-WALK(v.right, x, y) 
    else if v.key 〈= y 
     print v.key 
     INRANGE-TREE-WALK (v.left, x, y) 
     INRANGE-TREE-WALK (v.right, x, y) 
    else 
     INRANGE-TREE-WALK(v.left, x, y) 

Answer 1

我假定樹是二叉搜索樹。

你可以看看與該功能被稱爲當前節點的深度，然後請注意，對於任何給定的深度永遠不會發生在多個節點v與深度訪問了哪些v.key < x。

雖然這種情況可能會在不同的深度發生多次，但聲稱這絕不會在樹的深度處發生多次。

假設了一下這種說法是假的，那在一個特定的深度d樹算法訪問兩個節點一個和b，並發現這兩個a.key < x和b.key < x。讓我們也選擇一個和b這樣a.key <= b.key，即一個是在b左側。

首先，請注意，只有這樣，才能訪問這兩個一個和b是第一次訪問一個共同的祖先，這些節點，我們有x <= p.key <= y的p。否則，無法沿着樹上的兩個不同分支行走。

但由於這是一個二叉搜索樹，所有的節點v下面p有v.key >= P.key價值觀和後果v.key >= x右子樹。節點b也是如此。但這與b.key < x的前提矛盾。

所以，我們已經證明，函數不會被調用同一級別的兩個節點，並且它們都有v.key < x。因此，在該算法的全部執行中只能發現這種情況是真實的h次。

對於案例v.key > y可以得出相同的結論。

x <= p.key <= y將多少次爲真？由於該算法永遠不會訪問同一節點兩次（因爲它只訪問任何訪問節點的子節點），因此該條件成立的次數等於k。

保持v == NIL的次數。這永遠不會超過訪問節點的數量加上一個。

將所有這些加在一起，並且我們得到不多於2（2h + k）+1的單個函數調用，並且假定執行一個函數調用 - 不包括遞歸調用 - 是恆定的，我們得到的時間複雜度爲O（h + k）。