• ### What is your GameDev Story?

#### Archived

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

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

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

## 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 on other sites
Look up red-black trees. They should do what you want.

##### 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 on other sites
2-3-4 trees as well, which are equivalent to RB trees.

##### 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 on other sites
Red-and-black trees are quite complicated, they have so many cases. A much easier and cleaner balandce BST is AA-trees, google for it. Here is the oringinal paper.

LizardCPP

• ### What is your GameDev Story?

In 2019 we are celebrating 20 years of GameDev.net! Share your GameDev Story with us.

• 15
• 14
• 46
• 22
• 27
• ### Forum Statistics

• Total Topics
634044
• Total Posts
3015215
×