打印AVL字符串樹的最有效方法是什麼？

Question

我在想，一個遍歷將在O（n）時間運行。比這更好的唯一的事情是在登錄時間內運行某些內容。但我不明白這是怎麼回事，因爲我們必須至少運行n次。

O（n）是我們可以在這裏做的最新的嗎？

Answer 1

轉換和擴大@ CB的評論一個答案：

如果你有一個AVL樹在其N個字符串，你想打印所有的人，那麼你必須做至少Θ（N ）總的工作只是因爲你必須打印出n個字符串中的每一個。您通常可以降低生成列表所需的工作量，或者簡單地通過計算列表中將要包含的項目數來輸出一系列值。

這裏我們可以更加精確。假設樹中所有字符串的組合長度爲L.打印出樹中所有字符串所需的時間必須至少爲Θ（L），因爲輸出每個單獨字符會花費一些計算工作量。因此，我們可以說我們必須至少執行Θ（n + L）的工作來打印出樹中的所有字符串。

這裏給出的界限只是說任何正確的算法至少要做這麼多工作，並不是說實際上有一個算法能夠完成這麼多工作。但是如果你仔細觀察任何主要的樹遍歷 - 順序，前序，後序，水平順序 - 你會發現它們都符合這個時間限制。

現在，您可以尋找節省的一個領域是空間複雜性。如果樹是完全平衡的（因爲它在內存中保存了整個樹的一層，最底層可以有Θ（n）個節點），樹的級別遍歷可能需要總空間爲Ω（n），而順序，前序或後序遍歷只需要O（log n）內存，因爲只需要將當前訪問路徑存儲在AVL樹中具有對數高度的地方。