Removing a whole red-black tree subtree will preserve its properties?

Question

I am currently implementing a red-black tree data structure to perform some optimizations for the application.

In my application at this point, I need to remove all elements that are less than or equal to a given value (you can assume that the elements are integer) from the tree.

I could delete the items one by one, but I would like something faster. So my question is: if I remove the whole subtree of the red-black tree, how can I fix the tree to restore the height values ​​and color invariants?

Answer 1

When removing one element from a red-black tree, O (log n) time is required, where n is the number of elements that are currently in the tree.

If you delete only a few items, it is best to delete them one by one, resulting in O (k log n) operations (k = deleted items, n = items in the tree before deletion).

But if you know that you are going to remove a large number of nodes (for example, 50% or more from the tree), then it is better to iterate the elements you want to save (O (k '), where k' = the elements to be saved), then drop the tree (O (1) or O (n) depending on your memory management scheme) and rebuild the tree (O (k 'log k')). The total complexity is O (k ') + O (k' log k ') = O (k' log k '), which is obviously less than O (k log n) when k' k (you hold less than 50% of the tree )

Well, anyway, when you are going to remove the MOST from the elements, it is better to list in practice those that you want to save, and then restore the tree.

Answer 2

EDIT: The following is a general tree removal. You only need one Split operation (based on your actual question content).

In the worst case, O(log n) can remove the whole subtree of the Red-Black tree.

It is known that Split and Join operations on a red-black tree can be performed in O(log n) time.

Split Given the value of k and the red-black tree T, divide T into two red-black trees T1 and T2, so that all values ​​in T1 <k and all values ​​in T2> = k.

Attach : combine two red-black trees T1 and T2 into one red-black tree T. T1 and T2 satisfy max at T1 <= min in T2 (or T1 <= T2 shorter).

You need two Splits and one Join .

In your case, the subtree to be deleted will correspond to the range of values L <= v <= U

So, you first Split on L to get T1 and T2 with T1 <= T2. Split T2 to U to get T3 and T4 with T3 <= T4. Now Join trees T1 and T4.

In pseudoCode, your code will look something like this:

 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; } 

See this for more information: https://cstheory.stackexchange.com/questions/1045/subrange-of-a-red-and-black-tree

Answer 3

Mass removal from red-black wood is difficult, because the invariant of black height is badly messed up. Assuming you are not executing (soft) in real time, I would either delete one after the other (since you had to insert them one by one, we are talking about a lower constant coefficient here) or switch to the playback tree.