如何插入和刪除紅黑樹比AVL樹更快？

我想更好地理解差異，但還沒有找到可以將其分解到我的水平的來源。如何插入和刪除紅黑樹比AVL樹更快？

我知道兩棵樹每插入最多需要2次旋轉。那麼如何在紅黑樹上插入更快？

插入需要O（log n）在avl樹中旋轉，而O（1）在紅黑色中？

2014-09-01 user2626445

我不知道誰是白癡投了這個問題！ – 2014-09-01 14:18:27

嗯，我不知道你的等級是什麼，但簡單地說，紅黑樹的平衡性比AVL樹低。對於紅黑樹，從根到最遠葉的路徑不超過從根到最近葉的路徑的兩倍，而對於AVL樹，兩個相鄰子樹之間永遠不會有多於一個的層差。這使得AVL樹中的插入和刪除操作成本稍高，但查找速度更快。兩種數據結構的漸近和最壞情況行爲是相同的（在兩種情況下，運行時間（非旋轉數）爲O（log n）），您提到的O（1）是所謂的amortized runtime）。

查看this paragraph瞭解兩種數據結構的簡短比較。

來源

2014-09-01 14:28:20 Christian

謝謝你的男人！我只看最大的旋轉，而不是整體的平均值。在用幾個例子工作之後，我可以清楚地看到你所說的。我不知道什麼攤銷運行時會檢查出來。 – user2626445 2014-09-01 17:35:44

紅黑樹中的插入和刪除速度並不快。這是一個常見假設，假設基於這樣的事實：紅黑樹平均每插入一次的旋轉次數比AVL（.6與.7）少。
你可以在Java中比較TreeMap（紅黑色）和TreeMapAVL的這個實現來檢查你自己，你可以得到確切的數字而不是常見但不正確的假設。 https://github.com/dmcmanam/bbst-showdown

來源

2017-10-13 14:02:31

如何插入和刪除紅黑樹比AVL樹更快？

回答

相關問題