rebalance red-black tree with many violations

Question

Every red-black tree implementation I've come across use a strategy that considers re-balancing the tree after each mutation (e.g. insert, delete, ...).

I have a situation where I graft several sub-trees from one red-black tree onto another. After these grafts I would like to consider re-balancing the resulting tree.

Are there any approaches to doing this, either applying existing techniques in a brute force manner, or strategies that would make it efficient. It isn't entirely clear that existing algorithms can be naively applied.

Answer 1

In general, I would say that the algorithm you want is a tree union (also called a merge), which takes two trees and combines them so that the new tree contains the union of the keys of both inputs. You can read a brief description on Wikipedia, or a more in-depth description (which generalizes to other balancing schemes such as AVL, BB[α], Treap) in a recent paper.

However, it seems that your use-case is slightly more specific than a tree union. In particular, I'm guessing that the subtrees you are grafting onto the existing tree don't violate the ordering property of the BST. In this case the algorithm you want is even simpler than a tree union, and is much closer to a simple insertion:

// graft B onto T
function graft(T, B):
  let (L, R) = split T at B.root.key
  return join(L, join(B, R))

This algorithm is inspired by the union algorithm but does not need to recurse, because of the nice properties of the input. It uses two functions which I've summarized below; you can find them described in more detail in the links I provided above.

1. split cuts a tree at a specific key k, producing two trees L and R where all keys in L are less than k, and all keys in R are greater than k.
2. join takes two trees (L, R) where all keys in L are smaller than all keys in R and combines them into a single tree.

Both split and join have logarithmic time complexity. Because of this, graft only takes logarithmic time. If you have a small number of branches to graft, then simply iteratively applying graft should be fastest. However if you have a large number of branches to graft, it may be faster to first combine them into a single tree and then merge this tree with the original.