Solved

Balancing a binary tree

Posted on 2003-12-10
5
1,184 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

Back Up Your Microsoft Windows Server®

Back up all your Microsoft Windows Server – on-premises, in remote locations, in private and hybrid clouds. Your entire Windows Server will be backed up in one easy step with patented, block-level disk imaging. We achieve RTOs (recovery time objectives) as low as 15 seconds.

Question has a verified solution.

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

A high-level exploration of how our ever-increasing access to information has changed the way we do our jobs.
Healthcare organizations in the United States must adhere to the guidance of both the HIPAA (Health Insurance Portability and Accountability Act) and HITECH (Health Information Technology for Economic and Clinical Health Act) for securing and protec…
Video by: Tony
This video teaches viewers how to export a project from Adobe Premiere Pro and the various file types involved.
The goal of the video will be to teach the user the concept of local variables and scope. An example of a locally defined variable will be given as well as an explanation of what scope is in C++. The local variable and concept of scope will be relat…

828 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