Want to win a PS4? Go Premium and enter to win our High-Tech Treats giveaway. Enter to Win

x
Solved

# Balancing a binary tree

Posted on 2003-12-10
Medium Priority
1,198 Views
I have a binary tree that i can alot with but to make things simplier i want to be able to make it balanced. Does any EXPERT know the algorithum or the code for this. I can not figure it out for the life of me
0
Question by:Azrael1o
[X]
###### Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

• Help others & share knowledge
• Earn cash & points
• 3

LVL 11

Expert Comment

ID: 9916026
What is the configuration of the tree to begin with? Is this actually a binary search tree? I would guess this is the case.

It is typically easiest to balance a binary tree while building it. The AVL tree (http://sky.fit.qut.edu.au/~maire/avl/System/AVLTree.html) uses a mechanism known as rotation to restore balance to an almost balanced tree. The insertion operation is standard for a BST but is followed by a step that checks if the tree has gone out of balance. If it has, a rotation (right or left) is performed. Similar rebalancing might be necessary following a deletion. If you need more explanation, ask.

-bcl
0

Author Comment

ID: 9916062
thanks for the help but i also have to be able to balance the tree later on not just when i am adding to the tree.  I know this is alot harder but its an option that i want to add
0

LVL 11

Accepted Solution

ID: 9916125
Okay. What would that entail? Just about any balancing of the tree is as costly (in big-O time) as building a new tree and balancing it as you go. You can avoid having duplicate data by pulling the first tree apart, storing pointers to the nodes in a queue and then insert each of them into the new tree.

Hope this helps,
-bcl
0

LVL 11

Expert Comment

ID: 9916815
Looked around and found some lecture notes http://user.it.uu.se/~pierref/courses/AD1/Slides/AVLtrees.pdf

-bcl
0

LVL 4

Expert Comment

ID: 9919647
Hi Azrael1o,

I know of 2 kinds of balanced trees. One is calle 2-3-4 tree, and the swcond is called red-black tree.

The 2-3-4 is made of nodes containing 2, 3 or 4 subnodes (surprisingly), so it isn't a binary tree. Inserting (and deleting) in such a tree is matter of changing the node types (2, 3, 4) and splitting the higher level nodes into lower level ones. Draw some pictures and you'll find what to do and whot to not.

The red-black is exactly the same as 2-3-4 (almost). The 2, 3, 4 nodes there are transfered into binary structures (little subtrees) where leaves are coloured red and the rest is coloured black (or vice versa). All the folowing algorithms are used similar to 2-3-4 trees.

Search the web and read something about the trees. You may try: http://www.cs.brown.edu/courses/cs016/book/slides/234_RB_trees2x2.pdf but there are many other good resources.

Cheers!
0

## Featured Post

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question