Deleting a whole subtree of a red-black tree would keep its properties?

Question

I'm currently implementing a red-black tree data structure to perform some optimizations for an application.

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

I could delete the elements one by one, but I would like to have something faster. Therefore, my question is: if I delete a whole subtree of a red-black tree, how could I fix the tree to recover the height and color invariants?

Answer 1

When you delete one element from a red-black tree it takes O(log n) time, where n is the number of elements currently in the tree.

If you remove only few of the elements, then it's best just to remove them one by one, ending up with O(k log n) operations (k = removed elements, n = elements in the tree before removals).

But if you know that you are going to remove a large number of nodes (e.g. 50% or more of the tree), then it's better to iterate through the elements you want to keep (O(k') operation where k' = elements what will be kept), then scrap the tree (O(1) or O(n) depending on your memory management scheme) and rebuild the tree (O(k' log k')) operation. The total complexity is O(k')+O(k' log k') = O(k' log k'), which obviously is less than O(k log n) when k' < k (you keep less than 50% of the tree).

Well, the point being anyway that when you are going to remove MOST of the elements, it's better in practice to enumerate the ones you want to keep and then rebuild the tree.

Answer 2

EDIT: The below is for a generic sub-tree delete. What you need is just a single Split operation (based on your actual question contents).

It is possible to delete a whole subtree of a Red-Black tree in worst case O(log n) time.

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

Split : Given a value k and a red-black Tree T, Split T into two red-black trees T1 and T2 such that all values in T1 < k and all values in T2 >= k.

Join : Combine two red-black trees T1 and T2 into a single red-black tree T. T1 and T2 satisfy max in T1 <= min in T2 (or T1 <= T2 in short).

What you need is two Splits and one Join.

In your case, the subtree you need to delete will correspond to a range of values L <= v <= U.

So you first Split on L, to get T1 and T2 with T1 <= T2. Split T2 on U to get T3 and T4 with T3 <= T4. Now Join the 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