Concatenating red-black trees

Question

The OCaml standard library has a wonderful Set implementation that uses a very efficient divide-and-conquer algorithm to compute the union of two sets. I believe it takes whole subtrees (not just single elements) from one set and inserts them into the other set, rebalancing when necessary.

I'm wondering if this requires the height information that is kept in the AVL tree that OCaml uses or if this is also possible with red-black trees. For example, is it possible to concatenate a pair of red-black trees more efficiently than simply iterating over the second tree appending its elements to the end of the first tree?

Answer 1

You can copy the elements in linear time using a R-B tree. I guess in theory you could get sublinear complexity by transplanting an entire subtree at once -- a R-B tree stores relatively subtree height information that's kind of similar to an AVL tree, so you should be able to find the deepest part of the new subtree by traversing only the deeper of the sub-trees, in ~log(N) time. That would tell you how much you need to adjust your existing (target) tree so you can splice that entire sub-tree on and have the result balanced.

After that, you'd often have to re-balance though, especially if the target tree was smaller than the source. For an extreme case, consider a target with a single node and a source that's (say) 10 levels deep. You can't do anything to a single node so that you can splice something 10 levels deep onto it and have it immediately come out balanced. You'd probably want to avoid this (at least in general) by using the smaller tree as the source, and the larger as the target. You might still need a post-splice re-balance, but it'd be a lot less common this way.

Answer 2

You may win something when you'll combine tree with low overlap, but in general you'll have to reorgainze nodes. With balancing you have worse situation as there probably rules for rotating after touching only one node.

Answer 3

Since you seem be talking about Concatenate + adding onto the end, it seems like you have the following problem:

Given two red-black trees T1 and T2, such that keys of T1 <= keys of T2,
find union of the two.

This is called the join operation on the trees and in this case, it is possible to do the join of the trees in O(log n) time, check out: http://www.cs.tau.ac.il/~wein/publications/pdfs/rb_tree.pdf

Also check out: http://net.pku.edu.cn/~course/cs101/resource/Intro2Algorithm/book6/chap14.htm, Problem 14.2.