# 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&black tree and two boundaries, will produce a new red&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.

-
@Radu: There is a bug in the comment edit feature. If you use latex in a comment and edit the comment, you see strange behaviour, like duplication etc. – Aryabhata Sep 7 '10 at 16:31
@Radu I added a couple of paragraphs to better explain my question. – Daniel C. Sobral Sep 7 '10 at 17:38
Are trees immutable? – Tsuyoshi Ito Sep 7 '10 at 21:35
Also, did you mean upper bound instead of lower bound in the last paragraph? – Tsuyoshi Ito Sep 7 '10 at 21:45
It seems that the split operation on red-black trees can be implemented in worst-case time O(log n), where n is the number of elements in a tree. This claim can be found in the introduction of the paper “Purely functional worst case constant time catenable sorted lists” by Gerth Stølting Brodal, Christos Makris and Kostas Tsichlas, ESA 2006: cs.au.dk/~gerth/pub/esa06trees.html. As I mentioned in my previous comment, this allows a worst-case O(log n)-time implementation of the subrange operation. – Tsuyoshi Ito Sep 9 '10 at 14:20

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.

-
@Radu GRIGore: Yes, unless I am missing something. – Tsuyoshi Ito Sep 12 '10 at 13:39
@Radu GRIGore: Or maybe not, now I am not sure. This implementation of the split operation allocates O(log n) new nodes for the output tree, but I think that the whole operation can probably be implemented in the tail-recursive way, requiring only O(1) working space. If this is correct, the answer to your question will depend on what you mean by “extra space.” – Tsuyoshi Ito Sep 12 '10 at 14:06
That seems perfect, thanks! – Daniel C. Sobral Sep 12 '10 at 15:02
@Radu GRIGore: In that case, I think that extra space is O(1), though I have not checked it carefully. – Tsuyoshi Ito Sep 12 '10 at 16:02
@Radu GRIGore: I cannot see the reason why one cares about the amount of workspace without caring about the amount of the space needed to store the result itself. In complexity theory, the problem usually specifies what the result is and therefore the space needed to store the result does not depend on algorithms. However, in the current problem, there are many ways to implement the required operation and some implementations need more space to store the result than others. If you ignore the difference of this amount of space, I do not see why you care how much workspace we need. – Tsuyoshi Ito Sep 12 '10 at 17:42

The solution is not to use red-black trees. In splay trees and AVL trees the code for splitting and joining is very simple. I refer you to the following URLs with java code for splay trees and AVL trees that support this. Go to the following URL and check out Set.java (avl trees) and SplayTree.java (splay trees).

ftp://ftp.cs.cmu.edu/usr/ftp/usr/sleator/splaying/

---Danny Sleator

-
Welcome to the site, Danny ! – Suresh Venkat Feb 3 '11 at 4:15
How will this help modify the Scala Red Black implementation to support subranging in less than O(n)? I have not asked what kind of trees have simple subrange implementations because that is not a problem I have. This answer, though well intended, is off-topic and useless to the problem at hand. – Daniel C. Sobral Feb 3 '11 at 13:32

(This is meant to be a comment but I am too new to leave comment.)

I merely want to note that you may also be interested in the "excision" operation, which returns the subrange as a new tree and the input tree without the subrange as another. You need to have control on the underlying representation of the tree though since the known method relies on level links. Excision runs in time logarithmic to the size of the smaller tree, albeit in the amortized sense ("amortized" is iirc, because I don't have access to the paper any more) See:

K. Hoffman, K. Mehlhorn, P. Rosenstiehl, and R. E. Tarjan, Sorting Jordan sequences in linear time using level linked search trees, Information and Control, 68 (1986), 170–-184

P.S. The above citation came from Seidel's treap writeup. Treaps also support excision.

-
This method assumes that one already has pointers (or "fingers") to the two boundaries. – jbapple Oct 14 '10 at 14:26

Say that you have $n$ (comparable) elements in a red-black tree and you want to extract the $m$ elements that belong to $[a,b]$ into another red-black tree.

1. Descend from the root in time $O(\lg n)$ to the smallest element that is $\ge a$ (aka, $a$'s successor).
2. Start from there an in-order traversal that build an array with the desired elements in $O(m)$ time.
3. Build a binary search tree: The middle of the array gives the root and you recurse left and right. The distances from leaves to the root differ by at most one: Color the 'far' leaves red. (You do the coloring in the recursive procedure for constructing the tree.) This takes $O(m)$.

This works in $O(m+\lg n)$. Compare with "traverse the tree and insert in the result", which takes $O(n+m\lg m)$.

Update, in response to the request for $o(m)$ auxiliary space: I believe you need $\Omega(\lg m)$ auxiliary space to build an almost complete binary tree given that you are told the size in advance and then you receive the elements in-order one-by-one. Draw the complete final tree and imagine you received the first $k$ elements. These elements are separated from the others by a vertical line that cuts some edges. Since the left extremities of those edges need to be connected later, you need to remember them. In the worst case the vertical line cuts a zig-zag with $\lg m$ edges.

I didn't work out the details, so I'm not sure how the extra bookkeeping affects the running time.

Second update: JeffE's comment below says how to do it with $O(1)$ auxiliary space and within the same time bounds. (For mutable trees, at least.) That means that my waving hands argument above about $\Omega(\lg m)$ space is wrong.

-
Thinking about this, I think I could get a rough count in O(logn), with which I could avoid the temporary array. – Daniel C. Sobral Sep 7 '10 at 22:16
You can get the count in O(lg n) by storing subtree sizes in their roots. – Radu GRIGore Sep 8 '10 at 8:21
... but storing sizes in nodes goes against the requirement to not use auxiliary space, so my observation doesn't address your concern about memory. – Radu GRIGore Sep 10 '10 at 12:01
Binary trees can be perfectly rebalanced using only CONSTANT extra space (in addition to the tree itself): eecs.umich.edu/~qstout/abs/CACM86.html – JɛﬀE Sep 11 '10 at 20:32
@JeffE: I actually glanced at that paper but I (foolishly) assumed 'vine' is my array. So, in summary, if you replace my array with a 'vine' and my step 3 with vine_to_tree in the linked paper you get $O(m+\lg n)$ time and $O(1)$ auxiliary space. Thanks! – Radu GRIGore Sep 12 '10 at 12:00