Solved

Balancing a binary tree

Posted on 2003-12-10
5
1,180 Views
Last Modified: 2013-11-15
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
Comment
Question by:Azrael1o
  • 3
5 Comments
 
LVL 11

Expert Comment

by:bcladd
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

by:Azrael1o
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

by:
bcladd earned 500 total points
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

by:bcladd
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

by:skypalae
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

What Should I Do With This Threat Intelligence?

Are you wondering if you actually need threat intelligence? The answer is yes. We explain the basics for creating useful threat intelligence.

Join & Write a Comment

Storage devices are generally used to save the data or sometime transfer the data from one computer system to another system. However, sometimes user accidentally erased their important data from the Storage devices. Users have to know how data reco…
In our personal lives, we have well-designed consumer apps to delight us and make even the most complex transactions simple. Many enterprise applications, however, are a bit behind the times. For an enterprise app to be successful in today's tech wo…
The viewer will learn how to clear a vector as well as how to detect empty vectors in C++.
XMind Plus helps organize all details/aspects of any project from large to small in an orderly and concise manner. If you are working on a complex project, use this micro tutorial to show you how to make a basic flow chart. The software is free when…

758 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

22 Experts available now in Live!

Get 1:1 Help Now