WAVL（弱AVL）和紅黑樹之間有什麼區別？

WAVL（弱AVL）和紅黑樹有什麼區別？是否有一個特定的原因使用WAVL而不是RB？WAVL（弱AVL）和紅黑樹之間有什麼區別？

2017-03-27 nadavs

嗨，歡迎來到堆棧溢出。請注意，對這個問題的回答可能會導致不完全基於事實的答案，或者由於個人偏好而產生偏見的答案。可能存在不同的使用情況，其中每個選項將更好地服務於給定的目的。爲了獲得關於這個問題的答案，考慮在問題中增加一些更多的細節，說明你想如何使用這個問題，以及爲什麼你覺得每個選項要麼滿足你的需要，要麼不滿足。我希望你能夠找出哪個選項適合你:) –

WAVL樹試圖結合AVL樹和紅黑樹的最佳特徵。只要插入WAVL樹就會構建與AVL樹相同的樹 - 這種樹比紅黑樹更加平衡，因此WAVL樹可以在紅黑樹變得更不平衡的情況下更好地執行。 WAVL中的刪除比刪除AVL樹要簡單一些，因爲WAVL刪除只執行1或2次旋轉，而不是可能一直停留在根目錄。

來源

2017-10-20 20:49:02

這很簡單，但沒有什麼可以解釋WAVL在網絡上可以幫助我們驗證他們算法的真相。 –

我想我們可以在網上找到關於WAVL樹的所有信息。你想驗證什麼道理？關於它們的原始論文涵蓋了所有細節，其性能與Ben Pfaff 2004年論文（AVL比紅黑色快20％）涵蓋的AVL樹相似。 –

謝謝。我希望閱讀詳細解釋所有規則的原始文件。你也提到AVL比紅黑樹快20％。它對我來說很奇怪，因爲有很多變量會影響性能，比如使用遞歸或迭代，生成新節點的方式（從銀行或不），你做什麼：讀取vs插入vs刪除以及何時。這兩個實現共享相同的優化。如果您有任何問題，我會很高興在您的答案中包含參考（鏈接）。似乎無法訪問？ –

WAVL（弱AVL）和紅黑樹之間有什麼區別？

回答

相關問題