用於從紅黑樹中刪除多個元素的算法

Question

是否存在允許刪除RB中的多個節點的算法或從RB刪除節點的唯一算法是以某種方式刪除節點：
1.刪除一個
2.如果需要修復樹

Answer 1

如果沒有約束，說當你在做多節點缺失的樹必須保持平衡，它似乎是合理的，我認爲你可以做多的刪除後修復樹。

每次刪除後均衡樹的目的是爲了確保刪除操作的計算成本是一致的。如果您不需要刪除以這種方式保持一致，則可以用不同的方式編寫刪除算法。雖然，修復操作將比僅僅一次刪除後的計算更爲冗長。它也可能是一個更復雜的一個。

Answer 2

我解決這個問題的方法是創建一個要刪除的節點的鏈表並連續使用它們的標準刪除方法。我很想知道是否有更好的大規模刪除算法。

Answer 3

如果超過一半的節點被刪除，您可以扔掉現有的樹並在更短的時間內建立一個新樹，因爲插入和刪除的成本相同。

Answer 4

我會建議使用Treap而不是紅黑樹，因爲在Treap v/s紅黑樹中平衡樹在各種情況下似乎更容易。我和你有同樣的問題，但與Treaps。 https://cstheory.stackexchange.com/questions/20495/algorithm-to-bulk-delete-nodes-from-a-treap

我不能確定預期的高度限制在批量刪除後是否仍然有效（問題中提到的算法）。

Answer 5

您可能會感興趣的數據結構TeardownTree。它支持delete_range操作，在O(k + log n)時間內工作，其中n是樹中項目的初始數量，k是刪除項目（並返回給調用者）的數量。充分披露：我是作者。

我必須強調的是，數據結構不支持insert操作，但針對clone和delete_range進行了優化。我寫了一個非正式的description of the algorithm。通過所有優化，代碼現在與該文檔顯着不同，但它應該足以抓住這個想法。