Subrange of a Red and Black Tree While trying to fix a bug in a library, I searched for papers on finding subranges on red and black trees without success. I'm considering a solution using zippers and something similar to the usual append  operation used on deletion algorithms for immutable data structures, but I'm still wondering if there's a better approach I wasn't able to find, or even some minimum complexity boundary on such an operation?

Just to be clear, I'm talking about an algorithm that, given a red&amp;black tree and two boundaries, will produce a new red&amp;black tree with all the elements of the first tree that belong within those boundaries.

Of course, an upper bound for the complexity would be the complexity of traversing one tree and constructing the other by adding elements.
This answer combines some of my comments to the question and expand them.

The subrange operation on red-black trees can be performed in worst-case O(log n) time, where n is the number of elements in the original tree.  Since the resulting tree will share some nodes with the original tree, this approach is suitable only if trees are immutable (or trees are mutable but the original tree is no longer needed).

First notice that the subrange operation can be implemented by two split operations.  Here the split operation takes a red-black tree T and a key x and produces two trees L and R such that L consists of all the elements of T less than x and R the elements of T greater than x.  Therefore, our goal now is to implement the split operation on red-black trees in worst-case O(log n) time.

How do we perform the split operation on red-black trees in O(log n) time?  Well, it turned out that there was a well-known method.  (I did not know it, but I am no expert of data structures.)  Consider the join operation, which takes two trees L and R such that every value in L is less than every value in R and produces a tree consisting of all the values in L and R.  The join operation can be implemented in worst-case time O(|rL−rR|+1), where rL and rR are the ranks of L and R, respectively (that is, the number of black nodes on the path from the root to each leaf).  The split operation can be implemented by using the join operation O(log n) times, and the total worst-case time is still O(log n) by considering a telescoping sum.

Sections 4.1 and 4.2 of a book [Tar83] by Tarjan describe how to implement the join and the split operations on red-black trees in worst-case time O(log n).  These implementations destroy original trees, but it is easy to convert them to immutable, functional implementations by copying nodes instead of modifying them.

As a side note, the Set and the Map modules of Objective Caml provide the split operation as well as other standard operations on (immutable) balanced binary search trees.  Although they do not use red-black trees (they use balanced binary search trees with the constraint that the left height and the right height differ by at most 2), looking at their implementations might be useful, too.  Here is the implementation of the Set module.

References

[Tar83] Robert Endre Tarjan.  Data Structures and Network Algorithms.  Volume 44 of CBMS-NSF Regional Conference Series in Applied Mathematics, SIAM, 1983.