C++ – Balance factor of nodes in AVL Tree

avl-treec

To calculate the balance factor of a node in an AVL tree we need to find the height of its left subtree and the height of its right subtree. Then we subtract the height of right subtree from the height of its left subtree:

balancefactor = leftsubtreeheigh - rightsubtreeheight

My question is: How do I calculate the height of the left subtree or the right subtree?

For example in the given figure^₁ the height of the left subtree of the root node 40 is 4 and the height of the right subtree of 40 is 2 so the difference of the heights is 2.

How do I do this in C++? I don't want to use recursion because it's very confusing. Using an explicit stack instead of recursion is much more understandable.

^₁ The figure has been deleted from the imgur servers.

Best Answer

The depth of a node is 1 more then the depth of it's deepest child.

You can do this quite simply with recursion.

unsigned int depth(node *n)
{
    if (n == NULL)
        return 0;
    else
        return MAX(depth(n->left), depth(n->right)) + 1;
}

Part 1 - height

As starblue says, height is just recursive. In pseudo-code:

height(node) = max(height(node.L), height(node.R)) + 1

Now height could be defined in two ways. It could be the number of nodes in the path from the root to that node, or it could be the number of links. According to the page you referenced, the most common definition is for the number of links. In which case the complete pseudo code would be:

height(node): 
   if node == null:
        return -1
   else:
        return max(height(node.L), height(node.R)) + 1

If you wanted the number of nodes the code would be:

height(node): 
   if node == null:
        return 0
   else:
        return max(height(node.L), height(node.R)) + 1

Either way, the rebalancing algorithm I think should work the same.

However, your tree will be much more efficient (O(ln(n))) if you store and update height information in the tree, rather than calculating it each time. (O(n))

Part 2 - balancing

When it says "If the balance factor of R is 1", it is talking about the balance factor of the right branch, when the balance factor at the top is 2. It is telling you how to choose whether to do a single rotation or a double rotation. In (python like) Pseudo-code:

if balance factor(top) = 2: // right is imbalanced
     if balance factor(R) = 1: // 
          do a left rotation
     else if balance factor(R) = -1:
          do a double rotation
else: // must be -2, left is imbalanced
     if balance factor(L) = 1: // 
          do a left rotation
     else if balance factor(L) = -1:
          do a double rotation

I hope this makes sense

Best Answer

Related Solutions

How is Wikipedia’s example of an unbalanced AVL tree really unbalanced

The best way to calculate the height in a binary search tree? (balancing an AVL-tree)

Part 1 - height

Part 2 - balancing

Related Topic