爲什麼按順序遍歷一個線程樹是O（N）？

Question

我似乎無法弄清楚一個線程化二叉樹的順序遍歷是如何O（N）。 因爲你必須下降鏈接來找到最左邊的孩子，然後回到線程時您想要將父項添加到遍歷路徑中。那不是O（N^2）嗎？

謝謝！

Answer 1

樹（線程與否）的遍歷是O（N），因爲從父元素開始訪問任何節點都是O（1）。一個節點的訪問由三個固定的操作組成：從父節點下降到節點，訪問適當的（花費在節點上的時間），然後返回到父節點。 O（1 * N）是O（N）。

查看它的最終方法是該樹是一個圖形，並且遍歷圖形中的每條邊只有兩次。由於沒有周期或冗餘邊緣（每個節點可以通過一條獨特路徑到達），因此邊的數量與節點數成正比。具有N個節點的樹恰好具有N-1條邊：除樹的根節點之外，每個節點具有從其父節點通向其的邊。

有時，看起來好像訪問一個節點需要多個下降。例如，在訪問子樹中最右邊的節點之後，我們必須彈出多個級別，然後才能向右行進到下一個子樹。但我們並沒有一路下降，只是訪問那節點。每個一級下降可以被視爲僅需要訪問緊接在下面的節點所需要的，並且相反的上升的成本與此相關。通過訪問節點V，我們也可以訪問它下面的所有節點，但所有這些節點都從V的父節點到V節點受益並共享邊緣遍歷，然後再次備份。

這與攤銷分析有關，該分攤分析適用於根據對問題結構的一些總體觀察我們可以全局瞭解總成本的情況，但在個別操作的詳細級別，成本分配在看起來很混亂的不平衡的方式。

攤銷分析有助於我們理解，例如，將N個插入哈希表中，通過按指數規律增長來調整自己的大小爲O（N）。大多數插入操作都很快速，但是我們會不時增加表格並處理其內容。這類似於在樹遍歷期間，我們必須執行許多連續的攀登才能爬出深層子樹。

關於散列表的全局觀察是，在三次調整大小操作中，插入表中的每個項目將平均移動到一個較大的表中，因此每個插入可以被視爲「預付」插入，這是一個固定成本。當然，「老」的項目會被移動更多次，但這會被移動次數更少的「年輕」項目所抵消，從而降低成本。關於樹的全局觀察已經在上面提到過了：它有N-1條邊，在遍歷過程中每條邊都被精確地遍歷兩次，所以每個節點的訪問「支付」雙邊遍歷它的邊。因爲這很容易看到，所以我們實際上不必正式將分期分析應用於樹遍歷。

現在假設我們對每個節點進行了單獨搜索（並且樹是一個平衡搜索樹）。那麼遍歷仍然不是O（N * N），而是O（N log N）。假設我們有一個有序的搜索樹，它保存連續的整數。如果我們遞增整數併爲每個值執行單獨搜索，那麼每個搜索都是O（log N），並且我們最終完成N個這樣的搜索。在這種情況下，邊緣遍歷不再共享，所以攤銷不適用。爲了達到我們正在深度D處發現的某個給定節點，爲了該節點和該節點，我們必須跨越D個邊緣兩次。循環中下一次搜索另一個整數將完全獨立於前一個整數。

它也可以幫助你思考一個鏈表，它可以被認爲是一個非常不平衡的樹。要訪問長度爲N的鏈表中的所有項並返回到頭節點顯然是O（N）。單獨搜索每個項目是O（N * N），但是在遍歷中，我們並不是單獨搜索每個節點，而是使用每個前導作爲尋找下一個節點的跳板。

Answer 2

找不到父母的循環。否則說，你正在經歷兩個節點之間的每個弧兩次。這將是O（N）的2 *弧數= 2 *（節點數-1）。