Re: rb-tree creation from sorted sequence

Arne Ehrlich <newsreaderREMOVETHIS@xxxxxxxxxx> writes:

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

There is a rather nice O(n) time, O(1) additional space algorithm
for fully balancing a binary tree. I have a description of it
(although I did not invent it) at
http://adtinfo.org/libavl.html/Balancing-a-BST.html

Once you have a balanced tree, you can just color the nodes.
--
Peter Seebach on managing engineers:
"It's like herding cats, only most of the engineers are already
sick of laser pointers."
.

Relevant Pages

  • Re: Functional programming problem
    ... > Des anyone have any suggestions for how to get my expressions evaluated ... > functionally in linear time again? ... Instead of constructing a tree and then evaluating it with a function ...
    (comp.lang.functional)
  • Find the center of unicyclic graph
    ... To find the center of a tree is trival (by deleting leaves recursively), ... but how to find the center of unicyclic graph in linear time? ... unicyclic graph, however I cannot figure it out. ...
    (sci.math)
  • Find the center of unicyclic graph
    ... To find the centerof a tree is trival (by deleting leaves recursively), ... but how to find the centerof unicyclic graph in linear time? ... unicyclic graph, however I cannot figure it out. ...
    (comp.theory)
  • Re: linked list to binary tree
    ... >> If you want a balanced binary tree, ... > Also, I think the GPL license makes it less than useful as a library, ... There are many balanced tree libraries with many licenses. ... Peter Seebach on managing engineers: ...
    (comp.programming)