<p>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).</p>

<p><a href="ftp://ftp.cs.cmu.edu/usr/ftp/usr/sleator/splaying/">ftp://ftp.cs.cmu.edu/usr/ftp/usr/sleator/splaying/</a></p>

<p>---Danny Sleator</p>

CC BY-SA 2.5
2011-02-03T04:15:08.217Z
Welcome to the site, Danny !
Suresh Venkat
CC BY-SA 2.5
2011-02-03T13:32:01.130Z
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
CC BY-SA 2.5
2011-02-03T02:41:45.863Z
2011-02-03T02:41:45.863Z
Danny Sleator
<p>(This is meant to be a comment but I am too new to leave comment.)</p>

<p>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 <em>smaller</em> tree, albeit in the amortized sense ("amortized" is iirc, because I don't have access to the paper any more) See:</p>

<p>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>

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

CC BY-SA 2.5
2010-10-14T14:26:41.167Z
This method assumes that one already has pointers (or "fingers") to the two boundaries.
jbapple
CC BY-SA 2.5
2010-10-14T07:03:17.423Z
2010-10-14T07:03:17.423Z
Maverick Woo
<p>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. </p>

<ol>
<li>Descend from the root in time $O(\lg n)$ to the smallest element that is $\ge a$ (aka, $a$'s successor).</li>
<li>Start from there an in-order traversal that build an array with the desired elements in $O(m)$ time.</li>
<li>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)$.</li>
</ol>

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

<p><strong>Update</strong>, 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.</p>

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

<p><strong>Second update</strong>: 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.</p>

CC BY-SA 2.5
2010-09-07T22:16:56.120Z
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
CC BY-SA 2.5
2010-09-08T08:21:54.460Z
You can get the count in O(lg n) by storing subtree sizes in their roots.
Radu GRIGore
CC BY-SA 2.5
2010-09-10T12:01:30.507Z
... 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
CC BY-SA 2.5
2010-09-11T20:32:20.560Z
Binary trees can be perfectly rebalanced using only CONSTANT extra space (in addition to the tree itself): http://www.eecs.umich.edu/~qstout/abs/CACM86.html
Jeffε
CC BY-SA 2.5
2010-09-12T12:00:35.370Z
@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
CC BY-SA 2.5
2010-09-07T18:17:54.477Z
2010-09-12T12:03:53.457Z
2010-09-12T12:03:53.457Z
Radu GRIGore
<p>This answer combines some of my comments to the question and expand them.</p>

<p>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).</p>

<p>First notice that the subrange operation can be implemented by two split operations.  Here the <em>split</em> 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.</p>

<p>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 <em>join</em> 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<sub>L</sub>−r<sub>R</sub>|+1), where r<sub>L</sub> and r<sub>R</sub> 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.</p>

<p>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.</p>

<p>As a side note, the Set and the Map modules of <a href="http://caml.inria.fr/ocaml/">Objective Caml</a> 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 <a href="http://caml.inria.fr/cgi-bin/viewcvs.cgi/ocaml/trunk/stdlib/set.ml?view=log">the implementation of the Set module</a>.</p>

<p>References</p>

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

CC BY-SA 2.5
2010-09-12T13:39:54.947Z
@Radu GRIGore: Yes, unless I am missing something.
Tsuyoshi Ito
CC BY-SA 2.5
2010-09-12T14:06:01.647Z
@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
CC BY-SA 2.5
2010-09-12T16:02:11.807Z
@Radu GRIGore: In that case, I think that extra space is O(1), though I have not checked it carefully.
Tsuyoshi Ito
CC BY-SA 2.5
2010-09-12T17:42:43.033Z
@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
CC BY-SA 2.5
2010-09-12T20:09:34.247Z
The problem for immutable trees is different from the one for mutable trees. I understand the difference so I had nothing to ask about it. Now, zooming in on one of the two problems there are two aspects to discuss---memory and time. You didn't say how much memory you use and it didn't seem obvious to me what's the answer so I asked. I fail to see how this made you think that I ignore the difference between the two problems.
Radu GRIGore
CC BY-SA 2.5
2010-09-12T20:13:21.070Z
For the record, I'm the first one who upvoted your answer. I mention this only because you seem to think I'm somehow comparing my solution to yours, which I don't since they address different specializations of the question. Moreover, the OP clearly stated that he's more interested in the specialization that you addressed.
Radu GRIGore
CC BY-SA 2.5
2010-09-12T20:33:16.650Z
@Radu GRIGore: Thanks for explaining the motivation to your question, and I apologize about my incorrect presumption that you are comparing your solution to mine.  I agree that yours and mine are solutions to different problems.  (more)
Tsuyoshi Ito
CC BY-SA 2.5
2010-09-12T20:37:06.457Z
@Radu GRIGore: (cont’d)  However, rethinking about it, I cannot really understand if it matters whether work space is O(log n) or O(1) when the output space is O(log n).  I do not think that an algorithm requiring O(1) work space and producing 20 log n output space is better than an algorithm requiring 10 log n work space and producing 10 log n output space in any way.  I know that the difference of work space matters if the output is specified precisely so that we cannot enlarge the output space, but in the case of this question, the output is not specified “precisely” in this sense.
Tsuyoshi Ito
CC BY-SA 2.5
2010-09-13T11:44:38.847Z
Figuring out if the extra space is O(1) or O(lg n) probably entails better understanding what's going on. That's the main reason I'm curious.
Radu GRIGore
CC BY-SA 2.5
2010-09-11T20:17:22.173Z
2010-09-12T13:45:12.193Z
2010-09-12T13:45:12.193Z
Tsuyoshi Ito
<p>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 <em>append</em>  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?</p>

<p>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.</p>

<p>Of course, an upper bound for the complexity would be the complexity of traversing one tree and constructing the other by adding elements.</p>

CC BY-SA 2.5
2010-09-07T16:31:15.927Z
@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
CC BY-SA 2.5
2010-09-07T17:38:22.737Z
@Radu I added a couple of paragraphs to better explain my question.
Daniel C. Sobral
CC BY-SA 2.5
2010-09-07T21:35:23.587Z
Are trees immutable?
Tsuyoshi Ito
CC BY-SA 2.5
2010-09-07T21:45:02.543Z
Also, did you mean upper bound instead of lower bound in the last paragraph?
Tsuyoshi Ito
CC BY-SA 2.5
2010-09-07T22:11:19.027Z
@Tsuyoshi Indeed, yes. Fixing...
Daniel C. Sobral
CC BY-SA 2.5
2010-09-07T22:14:54.507Z
@Tsuyoshi Preferably, immutable trees and no temporary data structure storing all elements -- like in Radu's answer. However, anything helps.
Daniel C. Sobral
CC BY-SA 2.5
2010-09-08T01:03:26.020Z
If the trees are immutable, I wonder if O(polylog n) time is possible, where n is the number of elements in the original tree.  Of course, it is easy to construct a binary search tree consisting of the desired range in O(log n) time (because you can share subtrees if trees are immutable), and the “only” nontrivial part is to recover the invariants of the red-black tree.  I wonder how many nodes have to change their colors to recover the invariants.
Tsuyoshi Ito
CC BY-SA 2.5
2010-09-08T08:30:39.567Z
@Daniel: If trees are immutable then I don't see how you can avoid using $\lg n$ auxiliary space (typically in the form of a call stack). (You ask for $o(m)$ auxiliary space, but it's not clear what dependence on n you want.)
Radu GRIGore
CC BY-SA 2.5
2010-09-09T12:10:35.743Z
The subrange operation can be implemented by two split operations, and the split operation might be easier to consider.  I will not be surprised if split (and hence subrange) on a red-black tree can be implemented in worst-case time O(log n), where n is the number of elements in the original tree.
Tsuyoshi Ito
CC BY-SA 2.5
2010-09-09T14:20:03.620Z
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: http://www.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
<ds.data-structures><tree>
Subrange of a Red and Black Tree
Daniel C. Sobral
# Subrange of a Red and Black Tree

(Asked by: username_0 on 2010-09-07)

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.

**Tags:** ds.data-structures, tree
> **Comments:**
> **username_1**: @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.  
> **username_0**: @Radu I added a couple of paragraphs to better explain my question.  
> **username_2**: Are trees immutable?  
> **username_2**: Also, did you mean upper bound instead of lower bound in the last paragraph?  
> **username_0**: @Tsuyoshi Indeed, yes. Fixing...  
> **username_0**: @Tsuyoshi Preferably, immutable trees and no temporary data structure storing all elements -- like in Radu's answer. However, anything helps.  
> **username_2**: If the trees are immutable, I wonder if O(polylog n) time is possible, where n is the number of elements in the original tree.  Of course, it is easy to construct a binary search tree consisting of the desired range in O(log n) time (because you can share subtrees if trees are immutable), and the “only” nontrivial part is to recover the invariants of the red-black tree.  I wonder how many nodes have to change their colors to recover the invariants.  
> **username_3**: @Daniel: If trees are immutable then I don't see how you can avoid using $\lg n$ auxiliary space (typically in the form of a call stack). (You ask for $o(m)$ auxiliary space, but it's not clear what dependence on n you want.)  
> **username_2**: The subrange operation can be implemented by two split operations, and the split operation might be easier to consider.  I will not be surprised if split (and hence subrange) on a red-black tree can be implemented in worst-case time O(log n), where n is the number of elements in the original tree.  
> **username_2**: 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: http://www.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.  

---

## 4 answers

### Answer by username_2 on 2010-09-11. Score: 11 | Accepted answer

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](http://caml.inria.fr/ocaml/) 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](http://caml.inria.fr/cgi-bin/viewcvs.cgi/ocaml/trunk/stdlib/set.ml?view=log).

References

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

> **Comments:**
> **username_2**: @Radu GRIGore: Yes, unless I am missing something.  
> **username_2**: @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.”  
> **username_2**: @Radu GRIGore: In that case, I think that extra space is O(1), though I have not checked it carefully.  
> **username_2**: @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.  
> **username_3**: The problem for immutable trees is different from the one for mutable trees. I understand the difference so I had nothing to ask about it. Now, zooming in on one of the two problems there are two aspects to discuss---memory and time. You didn't say how much memory you use and it didn't seem obvious to me what's the answer so I asked. I fail to see how this made you think that I ignore the difference between the two problems.  
> **username_3**: For the record, I'm the first one who upvoted your answer. I mention this only because you seem to think I'm somehow comparing my solution to yours, which I don't since they address different specializations of the question. Moreover, the OP clearly stated that he's more interested in the specialization that you addressed.  
> **username_2**: @Radu GRIGore: Thanks for explaining the motivation to your question, and I apologize about my incorrect presumption that you are comparing your solution to mine.  I agree that yours and mine are solutions to different problems.  (more)  
> **username_2**: @Radu GRIGore: (cont’d)  However, rethinking about it, I cannot really understand if it matters whether work space is O(log n) or O(1) when the output space is O(log n).  I do not think that an algorithm requiring O(1) work space and producing 20 log n output space is better than an algorithm requiring 10 log n work space and producing 10 log n output space in any way.  I know that the difference of work space matters if the output is specified precisely so that we cannot enlarge the output space, but in the case of this question, the output is not specified “precisely” in this sense.  
> **username_3**: Figuring out if the extra space is O(1) or O(lg n) probably entails better understanding what's going on. That's the main reason I'm curious.  

---

### Answer by username_4 on 2011-02-03. Score: 8

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

> **Comments:**
> **username_5**: Welcome to the site, Danny !  
> **username_0**: 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.  

---

### Answer by username_6 on 2010-10-14. Score: 6

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

> **Comments:**
> **username_7**: This method assumes that one already has pointers (or "fingers") to the two boundaries.  

---

### Answer by username_3 on 2010-09-07. Score: 3

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.

> **Comments:**
> **username_0**: Thinking about this, I think I could get a rough count in `O(logn)`, with which I could avoid the temporary array.  
> **username_3**: You can get the count in O(lg n) by storing subtree sizes in their roots.  
> **username_3**: ... but storing sizes in nodes goes against the requirement to not use auxiliary space, so my observation doesn't address your concern about memory.  
> **username_8**: Binary trees can be perfectly rebalanced using only CONSTANT extra space (in addition to the tree itself): http://www.eecs.umich.edu/~qstout/abs/CACM86.html  
> **username_3**: @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!  

---

