[OT] Rebalancing a Binary Search Tree

[Philipp]

Hello,
(sorry this is not a c++ question, but I didn't know any better NG to
post to)

Is there an easy algorithm to rebalance a binary search tree?
Is free example c++ code available somewhere?

I have found some on the web but all are much to complicated for my
simple application (needs not be fast, can have lots of memory).

I think that writing the BST out to an array by in-order traversal and
reconstructing the tree from there is probably the easiest.
Is there a beautiful recursive algorithm ro reconstruct the tree from an
ordered array so it ends up balanced?

Thanks for any answers
Phil

 

[Philipp]

Hello,
(sorry this is not a c++ question, but I didn't know any better NG to
post to)

Is there an easy algorithm to rebalance a binary search tree?
Is free example c++ code available somewhere?

I have found some on the web but all are much to complicated for my
simple application (needs not be fast, can have lots of memory).

I think that writing the BST out to an array by in-order traversal and
reconstructing the tree from there is probably the easiest.
Is there a beautiful recursive algorithm ro reconstruct the tree from an
ordered array so it ends up balanced?

OK nevermind. I figured it out myself...
(sorry for the noise)

 

[flopbucket]

Is there an easy algorithm to rebalance a binary search tree?
Is free example c++ code available somewhere?

Take a look at red-black trees:
http://en.wikipedia.org/wiki/Red-black_tree