爲什麼avl樹比紅黑樹搜索更快？

我已經在幾個地方看過它，avl樹搜索速度更快，但無法理解。據我所知：紅黑樹的最大高度= 2 * log（N + 1） AVL樹的高度= 1.44 *徽標（N + 1）爲什麼avl樹比紅黑樹搜索更快？

是否因爲AVL較短？

2011-05-20 paseena

閱讀關於數據結構的一本書。但是如果我正確地記得（從頭頂開始），AVL樹近似於比RB樹更加接近完美平衡，以插入AVL的代價比RB更昂貴。 – 2011-05-20 21:18:48

是的，因爲它更短，因此從上到下節點更少。也許一張照片會有所幫助：http://en.wikipedia.org/wiki/File:AVL_Tree_Rebalancing.svg – 0x4f3759df 2011-05-20 21:19:47

是的。

查找項目所需的步驟數取決於項目與根之間的距離。

由於AVL樹包裝得更緊密（即它具有較低的最大高度），這意味着比紅黑色案件更接近根部的項目更多。

特別緊密的包裝也意味着AVL樹在插入元素時需要更多的工作。任何應用程序的最佳選擇取決於它是插入密集型還是搜索密集型...

來源

2011-05-20 21:21:35 Andrei

+1好解釋 – cnicutar 2011-05-20 21:26:33

一個很好的解釋。我只能添加一些數字：AVL樹中節點深度的最大差異是1，在R-B樹中，一個節點可以比另一個節點深兩倍（深度是節點和根之間的距離）。但是R-B樹中的插入和刪除最多需要3次旋轉，而AVL樹可能需要與樹深相等的旋轉次數。（旋轉是平衡樹木中的基本操作，在這裏我不會描述它） – 2013-06-11 07:31:16

如果輸入鍵幾乎是上升/下降，AVL樹比紅黑樹好，因爲那樣我們就必須做單旋轉（左 - 左或右 - 右情況）以添加此元素。而且，由於樹會緊密平衡，搜索也會更快。

但是對於隨機選擇的輸入鍵，RBTree更好，因爲與AVL相比，它們需要更少的旋轉插入。

總體而言，它取決於輸入序列，這將決定如何傾斜，我們的樹，和performed.For刀片式密集使用紅黑樹和搜索集約利用AVL操作。

來源

2012-12-02 10:23:47 Decipher

AVL樹和RBTree確實有各自的優點和缺點。如果你已經學會了他們的工作方式，你會更好地理解這一點。

AVL在插入操作略高於RBTree更快，因爲會涉及插入最多一個旋轉，雖然可能有兩個用於RBTree。

RBTree只需要刪除最多三個旋轉，但這不是在AVL保證。所以它可以比AVL更快地刪除節點。

然而，首先，他們都有嚴格的對數樹高。

拿起任何樹，這使得AVL「平衡」保證高度的兩個子子樹之間的差爲一個，這就是說，直觀的財產，整個樹是剛性的平衡。

但是，當涉及到一個RBTree時，由於RBTree的屬性只能保證樹的深度不會大於節點總數的對數的兩倍，所以規則可能變得「鬆散」。

我這裏還有一些事實，可以更精確：

AVL樹的高度嚴格小於：1.44log（N + 2）-0.328 （約）

爲紅色黑樹的高度最大爲2log（N + 1）

有關詳細信息，請參閱https://en.wikipedia.org/wiki/AVL_tree#Comparison_to_other_structures。

來源

2013-06-11 06:01:11 Determinant

爲什麼avl樹比紅黑樹搜索更快？

回答

相關問題