AVL Tree Help!!!

[BarneyInTechno]

hi,
i was wondering, when you build an AVL tree, how do you check if it's balanced or not? Is there some generic loop that everyone basically uses? i can think of one, but im not really sure if that's be best way to do it. thanks =)

 

[Drekce]

It really isnt all that hard to visualize. Make sure that you have white board handy while debugging to make sure that the tree is rotating correctly.

Anyway...

An AVL tree should already be balanced everytime that you try to insert (That is why it is an
AVL tree), so that means that the only part that can be messed up is the side where the insertion was made. To check for balance, start at the parent of the new leaf node and check your children variables (Every node should have two variables that keep track of the number of left and right children that that node has). If the difference of these variables is more than one, then the tree needs to be rotated, after the rotation it will be balanced. If that node IS balanced correctly then you must move up to its parent and do the same thing. This must be done all the way up to the root node of the tree.

REMEMBER: The critical node is the LOWEST unbalanced node, so if the first node you check needs to be rotated, then you are done checking. If not, you must go up to the next. If you make it all the way to the root and none were unbalanced, then the tree was never out of AVL form.

Hope that helps.

 

[br0wn]

You can trace from the root to all the leaves,
the longest should be at most log(n) where n is the number of
elements.

 

[BarneyInTechno]

that was great help, thanks =) but i got one more question, i dont know when to use a single rotation and when to use a double rotation, and how do i write code that could distinguish between a single/double, left/right rotation?

 

[Drekce]

Too see whether you need a single or double rotation, you must trace the path from the new leaf to the critical node. If the path is straight, then all you need is a single rotation, but if you have a "dog-leg" in the path, then you must do a double rotation. You MUST figure all of this out visually before you try and code it or you will have a very tough time.

To code the single and double rotation, all that you need really is a single rotation function, but just run it twice to make the double rotation. Don't forget that for the double rotation, you must rotate in the opposite direction of the first rotation.