Re: rb-tree creation from sorted sequence


Arne Ehrlich wrote:
> Hi everyone!
>
> I could not find an Algorithm-Newsgroup so I tried comp.theory
> as most people an this list seem to have a rather broad knowlede
> of CS. :-)
>
> I've been trying to find a Paper describing a method to
> construct a red-black tree from a sorted sequence in
> linear time.
>
> Does anyone remember articles/papers about this issue?

No, but why not just create a perfectly balanced tree,
using the median as the root, etc. Alternately color the
levels red and black, with red at the bottom (in case the
bottom level is not completely filled in).

.