Merging two red-black trees

[dotnwat]

I'm interested in being able to efficiently merge two red-black trees, specifically optimizing for the case in which trees share most structure. For example:

// first tree
tree = red_black_tree();
tree = tree.insert(1);
tree = tree.insert(2);

// second tree, forked from the first
other = tree.insert(3);
other = tree.insert(4);

// fold them back together
tree = tree.merge(other);

I'm wondering if you have any takes on this and/or suggestions about how to approach the problem. Thanks!

[orium]

Of the top of my head I don't see a way to merge them in better than O(N⋅lg(M)) where N is the size of the first tree and M of the second one. A red black tree imposes a conditions on the tree that makes it so you can't simply stitch them together. If there's a better way, I'm sure there's a paper about that.

[dotnwat]

O(N⋅lg(M)) where N is the size of the first tree and M of the second one

I would have guessed that the complexity would not be a function of N and M, but rather a function of the size of the delta of each tree from their common shared sub-trees.

For example:

tree = rb_tree() // arbitrary starting state

delta1 = tree.insert(1)
delta2 = tree.insert(2)

tree2 = delta1.merge(delta2)

If we say that |delta| is the number of nodes produced by the path-copying algorithm, I'd have guessed that merge could be proportional to the size of the two deltas, rather than the size of the original tree(s).

[orium]

Adding or removing elements to a RLB can change it's structure along the path from root to leaf, because of the re-balancing it does, so it's not a simple stitch job. Again: maybe there's a better way than N⋅lg(M), and if there is, there's a research paper about it if you are willing look for it.

[dotnwat]

Thanks. I'll give it some thought. Seems like an interesting problem to noodle on.