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!