Balancing a Binary Tree (AVL)

Question

Ok, this is another one in the theory realm for the CS guys around.

In the 90's I did fairly well in implementing BST's. The only thing I could never get my head around was the intricacy of the algorithm to balance a Binary Tree (AVL).

Can you guys help me on this?

Answer 1

I don't think it's good to post complete codes for node balancing algorithms here since they get quite big. However, the Wikipedia article on red-black trees contains a complete C implementation of the algorithm and the article on AVL trees has several links to high-quality implementations as well.

These two implementations are enough for most general-purpose scenarios.

Answer 2

A scapegoat tree possibly has the simplest balance-determination algorithm to understand. If any insertion causes the new node to be too deep, it finds a node around which to rebalance, by looking at weight balance rather than height balance. The rule for whether to rebalance on delete is also simple. It doesn't store any arcane information in the nodes. It's trickier to prove that it's correct, but you don't need that to understand the algorithm...

However, unlike an AVL it isn't height-balanced at all times. Like red-black its unbalance is bounded, but unlike red-black it's tunable with a parameter, so for most practical purposes it looks as balanced as you need it to be. I suspect that if you tune it too tightly, though, it ends up as bad or worse than AVL for worst-case insertions.

Response to question edit

I'll provide my personal path to understanding AVL trees.

First you have to understand what a tree rotation is, so ignore everything else you've ever heard the AVL algorithms and understand that. Get straight in your head which is a right rotation and which is a left rotation, and what each does to the tree, or else the descriptions of the precise methods will just confuse you.

Next, understand that the trick for balancing AVL trees is that each node records in it the difference between the height of its left and right subtrees. The definition of 'height balanced' is that this is between -1 and 1 inclusive for every node in the tree.

Next, understand that if you have added or removed a node, you may have unbalanced the tree. But you can only have changed the balance of nodes which are ancestors of the node you added or removed. So, what you're going to do is work your way back up the tree, using rotations to balance any unbalanced nodes you find, and updating their balance score, until the tree is balanced again.

The final part of understanding it is to look up in a decent reference the specific rotations used to rebalance each node you find: this is the "technique" of it as opposed to the high concept. You only have to remember the details while modifying AVL tree code or maybe during data structures exams. It's years since I last had AVL tree code so much as open in the debugger - implementations tend to get to a point where they work and then stay working. So I really do not remember. You can sort of work it out on a table using a few poker chips, but it's hard to be sure you've really got all the cases (there aren't many). Best just to look it up.

Then there's the business of translating it all into code.

I don't think that looking at code listings helps very much with any stage except the last, so ignore them. Even in the best case, where the code is clearly written, it will look like a textbook description of the process, but without the diagrams. In a more typical case it's a mess of C struct manipulation. So just stick to the books.

Answer 3

I've been doing some work with AVL trees lately.

The best help I was able to find on how to balance them was through searching google.

I just coded around this pseudo code (if you understand how to do rotations it is pretty easy to implement).

IF tree is right heavy
{
  IF tree's right subtree is left heavy
  {
     Perform Double Left rotation 
  }
  ELSE
  {
     Perform Single Left rotation
  }
}
ELSE IF tree is left heavy
{
  IF tree's left subtree is right heavy
  {
     Perform Double Right rotation
  }
  ELSE
  {
     Perform Single Right rotation
  }
}

Answer 4

I agree, a complete program would not be appropriate.

While classical AVL and RB tree use a deterministic approach, I would suggest to have a look at "Randomized binary search trees" that are less costly to keep balanced and guarantee a good balancing regardless the statistical distribution of the keys.