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
5
Medium Priority
?
1,198 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
[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
  • Learn & ask questions
  • 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 1500 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

Ask an Anonymous Question!

Don't feel intimidated by what you don't know. Ask your question anonymously. It's easy! Learn more and upgrade.

Question has a verified solution.

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

The core idea of this article is to make you acquainted with the best way in which you can export Exchange mailbox to PST format.
Here in this article, you will get a step by step guidance on how to restore an Exchange database to a recovery database. Get a brief on Recovery Database and how it can be used to restore Exchange database in this section!
An overview on how to enroll an hourly employee into the employee database and how to give them access into the clock in terminal.
With the power of JIRA, there's an unlimited number of ways you can customize it, use it and benefit from it. With that in mind, there's bound to be things that I wasn't able to cover in this course. With this summary we'll look at some places to go…

636 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