Subrange of a Red and Black Tree

Question

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.

Answer 1

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(|r_L−r_R|+1), where r_L and r_R 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.

Answer 2

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

Answer 3

(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.

Answer 4

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.