關於平衡樹分析

我正在讀一本關於樹的書。這裏是文本片段。關於平衡樹分析

有很多通用算法來實現平衡樹。大部分比標準二分查找樹更復雜一些，平均需要更長的時間。然而，他們確實提供了針對令人尷尬的簡單情況的保護。

一種較新的方法是放棄平衡條件並允許樹任意深，但是在每次操作之後，應用重構規則，其趨於使未來的操作有效。這些類型的數據結構通常被歸類爲自我調整。在二叉搜索樹的情況下，我們不能保證在任何單個操作上綁定O（log n），但可以顯示m個操作的任何序列在最差情況下需要總時間O（m log n）案件。

上面的文字片段問題

如何筆者來到在第一段的結論是什麼意思筆者尷尬簡單的情況下如何平衡樹的一般算法提供防範呢？
是什麼作者的意思是「在最後一段米操作的任何順序採取我們如何得出這一結論的總時間O（mlogn），請求與例子來解釋。

謝謝！

來源

2011-08-31 venkysmarty

對於一個典型的，簡單的實現二叉搜索樹的，僅僅將序列1, 2, 3, ..., n會產生有n個級別的樹。（插入每個元素都會沿着樹的右邊遍歷樹，然後在這邊添加一個新元素，導致最大程度的不平衡樹。）我相信這就是他們所說的「令人尷尬的簡單」。
他們在談論splay trees（與AVL或紅/黑樹相對）。 AVL和紅/黑樹保證O（log n）每個插入/刪除/查找操作的最壞情況，但代價是複雜的代碼和較大的常數因子。對於任何長操作順序，Splay樹不保證每個操作都可以保證O（log n），但它們確保每個操作的O（log n）平均爲。所以從長遠來看，它們的表現與更復雜的樹木一樣好，但具有更簡單的實現和更小的常數因子。

來源

2011-08-31 05:55:32 Nemo

我認爲在第二段中，它是O（mlogn）而不是O（logn） – venkysmarty

我更新它以讀取「O（log n）每個操作」。 – Nemo

1）我相信作者意味着像一串節點基本上看起來像一個懸掛列表的情況下，樹自動調整和旋轉（看着AVL Trees），你可以打擊「找到」或「刪除」像這樣的高度爲O（n）的樹。

2.）如果樹是自我調整的，它的高度將是O（logn）。由於我們在樹上執行了m個操作，因此我們可以假設，由於big-O是最差情況下的運行時間，因此操作的對象可能位於底部，因此在高度爲O（logn）的樹上進行m次操作（攤銷運行因爲再次旋轉可能會發生）將是O（mlogn）。

來源

2011-08-31 05:40:52 Vinay

什麼樣的操作，可以用elobarate，爲什麼我們用log n來多重m？ – venkysmarty

操作意義標準的東西，如「查找」，「刪除」和「插入」（所有在詞典ADT中概述）。 m簡單地表示我們執行了m個操作，每個操作都花費O（logn）時間。因此，這些m個操作序列將共同花費O（mlogn）時間。這就像做了三次需要12秒鐘的事情。然後整個過程需要36秒。 – Vinay

您的「編輯」不正確。紅色/黑色樹中的旋轉（例如）都經過精心設計，每一次操作都是O（log n），無論您按照什麼順序執行哪些操作。 – Nemo

簡單二叉搜索樹的最壞情況是當它變得如此不平衡以致每個節點只有一個孩子時。在這種情況下，具有N節點的樹將具有高度N，並且樹上的操作可能具有O(N)複雜性。平衡二叉搜索樹通過在樹操作之後以某種方式重新平衡樹來防止發生這種情況。由於這些重新平衡操作，我認爲可以說所有平衡樹算法比簡單的不平衡樹更復雜。
他們正在談論分期償還的複雜性。實質上他們說，雖然單個操作的複雜性並不總是如此，但是如果我們執行一系列操作，每個操作將平均達到O（log（N））複雜度，因此M操作的總數是O(Mlog(N)).

希望這會有所幫助。

來源

2011-08-31 05:43:32

如果你從一個排序列表開始，並且你沒有做任何重新平衡，你會得到一個完全不平衡的n級深度樹的最壞情況。但是輸入已經排序了，你應該能夠在O（n）時間內把它放在一個合理的順序中（選擇中間的元素作爲根，遞歸到根的孩子的左半部分和右半部分）。

來源

2011-08-31 05:53:37

關於平衡樹分析

回答

相關問題