刪除紅黑樹的整個子樹會保留其屬性？

Question

我目前正在實現一個紅黑樹數據結構來爲應用程序執行一些優化。

在我的應用程序中，在給定點上，我需要從樹中刪除小於或等於給定值的所有元素（您可以假定元素是整數）。

我可以逐個刪除元素，但我想要更快一些。因此，我的問題是：如果我刪除了紅黑樹的整個子樹，我該如何修復樹來恢復高度和顏色不變量？

Answer 1

當您從紅黑樹中刪除一個元素時，它需要O（log n）時間，其中n是樹中當前元素的數量。

如果你只刪除了一些元素，那麼最好只是逐個刪除它們，最後以O（k log n）操作（k =刪除的元素，n =移除之前樹中的元素）結束。但是如果你知道你要移除大量的節點（例如50％或更多的樹），那麼最好迭代你想要保留的元素（O（k'））操作，其中k'=將保留的元素），然後根據內存管理方案廢棄樹（O（1）或O（n））並重建樹（O（k'log k'））操作。當k'< k（保持小於50）時，總複雜度爲O（k'）+ O（k'log k'）= O（k'log k'），顯然小於O樹的％）。

好吧，無論如何，當您要刪除大部分元素時，最好在實踐中枚舉要保留的元素，然後重新構建樹。

Answer 2

從紅黑樹上批量刪除很難，因爲黑高不變變得非常糟糕。假設你沒有實時（軟），我要麼一個接一個地刪除（因爲你必須逐個插入它們，我們在這裏討論一個較小的常量因子），或者切換到一個splay樹。

Answer 3

編輯：下面是一個通用的子樹刪除。您需要的僅僅是一個Split操作（根據您的實際問題內容）。

在最壞情況下O(log n)時間內，可以刪除紅黑樹的整個子樹。

已知Split和Join在紅黑樹上的操作可以在O(log n)時間完成。

拆分：給定的值k和紅黑樹T，t分裂成兩個紅黑樹T1和T2，使得在T1 < K的T2的所有數值和所有數值> = K。

加入：組合兩個紅黑樹T1和T2到單個紅黑樹T. T1和T2滿足Max在T1在T2（或T1 <在短= T2）< =分鐘。

你需要的是兩個Splits和一個Join。

對於您的情況，您需要刪除的子樹將對應於值範圍L <= v <= U。

所以你首先在L上輸入Split，得到T1和T2，T1爲< = T2。 Split T2在U上得到T3和T4與T3 < = T4。現在Join樹T1和T4。

僞代碼，你的代碼將是這個樣子：https://cstheory.stackexchange.com/questions/1045/subrange-of-a-red-and-black-tree

：

Tree DeleteSubTree(Tree tree, Tree subTree) { 

    Key L = subTree.Min(); 
    Key U = subTree.Max(); 

    Pair <Tree> splitOnL = tree.Split(L); 
    Pair <Tree> splitOnU = splitOnL.Right.Split(U); 

    Tree newTree = splitOnL.Left.Join(splitOnU.Right); 

    return newTree; 
} 

有關更多信息，請參見本