Archived

This topic is now archived and is closed to further replies.

Balancing a Binary Sort Tree (seems silly, I know)

This topic is 5008 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Are there any efficient methods to ''balancing'' a binary sort tree? For example, if I add items (0, 1, 2) to a tree in a sequential order, the tree more or less just becomes a bulky linked list.
   0
  / \
null 1
      \
       2
 
Not a big deal with only 3 objects, but with a 1000 objects, clearly inefficient. I''d like to some how ''balance'' the tree, so that instead of having nothing but right nodes, I end up with:
   1
  / \
0    2
 
Much more efficient. Are there any easy ways to do this, if at all possible I''d like to avoid rebuilding the entire tree. Spending 5 seconds rebuilding the tree to generate code that executes in 10 ms instead of 5000 ms because the tree is balanced is a trade I''ll make however =P Any ideas?

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Look up red-black trees. They should do what you want.

Share this post


Link to post
Share on other sites
Red-black/AVL/splay/B/B+/B*-trees all maintain a balance condition to offer guaranteed logarithmic (or, for the splay tree, amortized logarithmic) lookups, which is as good as you''ll get for a sorted structure. Skip lists represent another way of achieving the same performance bound.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
2-3-4 trees as well, which are equivalent to RB trees.

Share this post


Link to post
Share on other sites
As a matter of fact, I had to do a lab on Red Black trees for a programming class at college about a month ago. You''re looking for something called a ''rotation'', which rotates nodes, resetting their left, right, and parent pointers. In your example, you would use a ''left rotation'' on the topmost node (0). This causes the nodes to shift so the tree is balanced in your result.

Look up Red Black Trees in Google - there''s thousands of resources out there! There''s many algorithms for that process in eneral, and even code for specific languages. Look it up, and find out how to do rotations. That should help solve your problems.

Grant Palin

Share this post


Link to post
Share on other sites