AVL Tree

   Today let's talk about what an AVL tree is. An AVL tree is a subtype of the binary search tree. Named after it's inventors Adelson, Velskii, and Landis, and that's how they made the name AVL, taken by their initials. AVL trees have the property of dynamic self-balancing in addition to all the properties exhibited by binary search trees. Here are the operations of an AVL tree:

• Insertion
• Deletion

Insertion

   Inserting a new node can cause the balance factor of some node to become 2 or -2. In that case, we fix the balance factors by use of rotations. Also, only the heights of the nodes on the path from the insertion point to the root can be changed. So, after inserting, we go back up to the root and update heights of the nodes and if we find any node with a balance factor of 2 or -2, we fix it by rotation. There are two rotations, which are the left rotation and the right rotation.

   Here are steps to follow for insertion:
   Let the newly inserted node be w

1. Perform standard BST insert for w.
2. Starting from w, travel up and find the first unbalanced node. Let z be the first unbalanced node, y be the child of z that comes on the path from w to z and x be the grandchild of z that comes on the path from w to z.
3. Re-balance the tree by performing appropriate rotations on the subtree rooted with z. 

    There can be 4 possible cases that need to be handled as x, y, and z can be arranged in 4 ways. Following are the possible 4 arrangements:

1. y is the left child of z and x is the left child of y (Left Left Case)
2. y is the left child of z and x is the right child of y (Left Right Case)
3. y is the right child of z and x is the right child of y (Right Right Case)
4. y is the right child of z and x is the left child of y (Right Left Case)

 Left Left Case:

T1, T2, T3 and T4 are subtrees.
         z                                      y 
        / \                                   /   \
       y   T4      Right Rotate (z)          x      z
      / \          - - - - - - - - ->      /  \    /  \ 
     x   T3                               T1  T2  T3  T4
    / \
  T1   T2

Left Right Case:

z                               z                           x
    / \                            /   \                        /  \ 
   y   T4  Left Rotate (y)        x    T4  Right Rotate(z)    y      z
  / \      - - - - - - - - ->    /  \      - - - - - - - ->  / \    / \
T1   x                          y    T3                    T1  T2 T3  T4
    / \                        / \
  T2   T3                    T1   T2

Right Right Case:

z                                y
 /  \                            /   \ 
T1   y     Left Rotate(z)       z      x
    /  \   - - - - - - - ->    / \    / \
   T2   x                     T1  T2 T3  T4
       / \
     T3  T4

Right Left Case:

 z                            z                            x
  / \                          / \                          /  \ 
T1   y   Right Rotate (y)    T1   x      Left Rotate(z)   z      y
    / \  - - - - - - - - ->     /  \   - - - - - - - ->  / \    / \
   x   T4                      T2   y                  T1  T2  T3  T4
  / \                              /  \
T2   T3                           T3   T4

Deletion

   In deletion also, we delete the node to be deleted in the same way as we do with a normal binary search tree. After that, we fix the unbalance of any ancestor node with suitable rotations, which is either the left or right rotation. The only thing is that unlike insertion, it might be possible that the unbalance propagates above the tree in deletion which makes us rebalance the ancestor nodes. There can be three cases of deletion, which are when the node to be deleted has no child, the node to be deleted has one child or the node to be deleted has 2 children. In the third case when the node has 2 children, we replace the content of the nodes with its successor and it reduces to the deletion of the node with either one child or none. After the deletion procedure, the heights of ancestor nodes will decrease and this may cause unbalance in the tree. Let's take the operations in the mentioned 4 cases from insertion. Note that, unlike insertion, fixing the node z won’t fix the complete AVL tree. After fixing z, we may have to fix ancestors of z as well

Here is an example for an AVL Tree and a B-tree:
   Insert: 5, 6, 7, 0, 4, 3, 8
   Delete: 3, 4, 8

AVL Tree

• Insertion: 

• Deletion: 

B-Tree

• Insertion:

• Deletion: