Hi folks;
I'm looking for an easy implementable search tree balancing algorithm and one of my friends recommended red-black trees.
Is there any better solution ? (keyword is "simple" :P)
Posted on 2007-03-19 19:14:22 by Dite
Simplest would be to dump the tree into a sorted array, and then exactly in the middle you'll have the root node. In the middle of the segment to the left you have the left node, and in the middle of the segment (of the array) you have the right node. And so forth.
In the chars ABCDEFG, D will be root, its left child-node is B, right node is F. B's child-nodes are A and C, F's nodes are E and G.
Posted on 2007-03-19 19:45:55 by Ultrano
thanks man
Posted on 2007-03-20 10:24:31 by Dite

The more clever implementations of self-organizing (and self-balancing) trees are indeed part tree and part linear array.
The Node structures which make up such a Tree are often themselves stored as a linear array, and so we can view such a tree as both a hierarchy AND a sorted array , simultaneously... and if the nodes are NOT all the same size, we'll generally find them stored as a linear array of Pointers to nodes, so there is no fundamental difference in that respect.
These more-clever implementations often provide both hierarchical and linear searching/sorting algorithms, and it's even possible to use two Heuristics to generate a tree which is most optimal for both kinds of access at once.
Posted on 2007-03-20 22:34:58 by Homer
HAHA simple? Well you need to list out the features of the trees that you need and which algorithm suits it the best.
Posted on 2007-03-24 01:20:49 by roticv
roticv o_O ? I see no problem - dumping into a sorted array (I would dump only pointers to the nodes, btw) is done by simple recursive walking through the three (in any one of the two approaches).
Most importantly - you don't have to care about what the tree-nodes contain. You don't even have to bother knowing how big the node-structs are (or even if they're not fixed-sized) if you dump pointers into that array.
Posted on 2007-03-24 06:26:31 by Ultrano

HAHA simple? Well you need to list out the features of the trees that you need and which algorithm suits it the best.

WOW What briliant mind ! I can't think of it !
Posted on 2007-03-26 07:33:22 by Dite