紅黑樹 - K插入和K刪除所需的最大旋轉次數？

Question

紅黑樹中K插入和K刪除後需要的最大旋轉次數是多少？

我在考慮它的3K，因爲在插入的最壞情況下，我們對每個插入執行2次旋轉，對於每次刪除執行1次旋轉。 我在正確的軌道上嗎？

Answer 1

與AVL樹不同，在AVL樹中，缺失的旋轉可以傳播到根部（儘管插入最多隻有一個（雙）旋轉），但RB樹需要一個常量（插入時最多2個，最多3個刪除）旋轉次數。在RB樹中，在刪除過程中可以取對數多少時間的是可以傳播到根的重新着色，這意味着插入和刪除對於AVL和RB樹都具有相同的漸近性。

（如果有興趣，你可以找到這些東西的分析in this script）

關於你的問題，頂多3K是正確的（但顯然旋轉從鏈接的腳本計算略有不同）。