AVL Trees

If the heights of both left and right subtrees are given then the searching in binary tree is efficient. When we frequently make insertions and deletions in a binary search tree, it is likely to get unbalanced.The efficiency of searching is ideal if the difference between the heights of left and right subtrees of all the nodes in a binary tree is at the most one.

So, a need arises to balance out the existing BST. Named after their inventor Adelson, Velski & Landis, AVL trees are height balancing binary search tree.

AVL tree checks the height of the left and the right sub-trees and assures that the difference is not more than 1. This difference is called the Balance Factor. Balance factor can be calculated as:

BalanceFactor = height(leftsubtree) – height(rightsubtree)

If the value of the BalanceFactor is more than 1, then the tree is balanced using some rotation techniques.

AVL Rotations

A tree rotation can be an intimidating concept at first. You end up in a situation where you're juggling nodes, and these nodes have trees attached to them, and it can all become confusing very fast

AVL Tree following are some approach :

• Left rotation

• Right rotation

• Left-Right rotation

• Right-Left rotation

Left Rotation

Imagine we have this situation:

                       a

                         \

                          b

                            \

                              c

To fix this, we must perform a left rotation, rooted at a. This is done in the following steps:

b becomes the new root.

a takes ownership of b's left child as its right child, or in this case, null.

b takes ownership of a as its left child.

The tree now looks like this:

                      b

                     / \

                    a c

Right Rotation

A right rotation is a mirror of the left rotation operation described above. Imagine we have this situation:

                 c

                /

              b

             /

          a

To fix this, we will perform a single right rotation, rooted at C. This is done in the following steps:

b becomes the new root.

c takes ownership of b's right child, as its left child. In this case, that value is null.

b takes ownership of c, as it's right child.

The resulting tree:

          b

         / \

        a c

Left-Right Rotation or Double Left

Sometimes a single left rotation is not sufficient to balance an unbalanced tree. Take this situation:

                a

                 \

                   c

Perfect. It's balanced. Let's insert 'b'.

                  a

                  \

                   c

                  /

                  b

Our initial reaction here is to do a single left rotation. Let's try that.

                c

               /

              a

               \

                b

Our left rotation has completed, and we're stuck in the same situation. If we were to do a single right rotation in this situation, we would be right back where we started. What's causing this? The answer is that this is a result of the right subtree having a negative balance.

In other words, because the right subtree was left heavy, our rotation was not sufficient. What can we do? The answer is to perform a right rotation on the right subtree. Read that again. We will perform a right rotation on the right subtree. We are not rotating on our current root. We are rotating on our right child. Think of our right subtree, isolated from our main tree, and perform a right rotation on it:

Before:

           c

           / 

         b

After

        b

         \

          c

After performing a rotation on our right subtree, we have prepared our root to be rotated left. Here is our tree now:

              a

               \

                b

                 \

                   c

Looks like we're ready for a left rotation. Let's do that:

                b

               / \

               a c

Violation Problem solved.

Right-Left Rotation or Double right

A double right rotation, or right-left rotation, or simply RL, is a rotation that must be performed when attempting to balance a tree which has a left subtree, that is right heavy. This is a mirror operation of what was illustrated in the section on Left-Right Rotations, or double left rotations.

Let's look at an example of a situation where we need to perform a Right-Left rotation.

             c

            /

           a

            \

             b

In this situation, we have a tree that is unbalanced. The left subtree has a height of 2, and the right subtree has a height of 0. This makes the balance factor of our root node, c, equal to -2. What do we do? Some kind of right rotation is clearly necessary, but a single right rotation will not solve our problem.

Let's try it:

          a

          \

           c

           /

         b

Looks like that didn't work. Now we have a tree that has a balance of 2. It would appear that we did not accomplish much. That is true. What do we do? Well, let's go back to the original tree, before we did our pointless right rotation:

            c

           /

          a

           \

            b

The reason our right rotation did not work, is because the left subtree, or 'a', has a positive balance factor, and is thus right heavy. Performing a right rotation on a tree that has a left subtree that is right heavy will result in the problem we just witnessed. What do we do? The answer is to make our left subtree left-heavy. We do this by performing a left rotation our left subtree. Doing so leaves us with this situation:

            c

           / 

          b

          /

          a

This is a tree which can now be balanced using a single right rotation. We can now perform our right rotation rooted at c. The result:

           b

           / \

           a c

Balance at last.