打印給定範圍內的BST鍵

Question

我想了解打印BST鍵在給定範圍內的運行時間。 我試圖從this example瞭解它，但我不能。

我想我明白O(log n)是從哪裏來的。這是從通過BST去遞歸，這將需要O(log n)每邊，但我不知道：

1. 凡K的來源。它只是持續打印時間嗎？如果是的話爲什麼運行時不是O(log n) + O(k)，而且你會忽略K

2. O(n)從哪裏開始遍歷呢？因爲它不在這個運行時。

3. 如果我們在樹的每一邊都有多個值，運行時將如何改變。例如，如果範圍是從4開始呢？

Answer 1

更簡單的方法來了解該解決方案是要考慮下面的算法：

1. 搜索在BST樹的最小值比關鍵k1更大 - O（LGN）
2. 在執行從k1開始遍歷BST樹節點，直到我們到達小於或等於k2的節點，並打印它們的鍵。因爲完整BST的有序遍歷需要O（n）次，所以如果k1和k2之間有k個密鑰，按順序遍歷需要O（k）次。

給定的算法是做同樣的事情;搜索k1和k2之間的關鍵字需要O（lgn）時間，而僅對k（k）範圍內的k個關鍵點進行打印，該範圍是O（k）。如果所有BST鍵位於k1和k2內，運行時間將爲O（lgn）+ O（n）= O（n），因爲所有n個鍵都需要打印出來。