?
Solved

Balancing a binary tree

Posted on 2003-12-10
5
Medium Priority
?
1,197 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

Free Tool: SSL Checker

Scans your site and returns information about your SSL implementation and certificate. Helpful for debugging and validating your SSL configuration.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

Question has a verified solution.

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

Container Orchestration platforms empower organizations to scale their apps at an exceptional rate. This is the reason numerous innovation-driven companies are moving apps to an appropriated datacenter wide platform that empowers them to scale at a …
This guide will walk you through the essential considerations and tech stack for building scalable websites. Know how to grow your business the smart way!
Monitoring a network: why having a policy is the best policy? Michael Kulchisky, MCSE, MCSA, MCP, VTSP, VSP, CCSP outlines the enormous benefits of having a policy-based approach when monitoring medium and large networks. Software utilized in this v…
In this brief tutorial Pawel from AdRem Software explains how you can quickly find out which services are running on your network, or what are the IP addresses of servers responsible for each service. Software used is freeware NetCrunch Tools (https…

770 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