Return to Answer

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.

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.

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)$.

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.

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: Put a red node on the long ones (and place it close to the leaves). (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)$.

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)$.