An AVL Tree is a type of a balanced binary tree. We need them so that the height of the BSTs are not that much so that search times are faster.
Insertion Operation:
The basic concept is after we insert the new node like a normal binary tree, we have to balance the tree again. After an insertion, the only nodes that might be unbalanced are the ones that are on the path from the inserted node. By re-balancing the tree at the deepest levels of these nodes, it restores the balance of the tree.
How to re-balance the tree?
Let the node to be re-balanced be T
There are 4 possibilities:
1. The inserted node is located at the left sub tree of the left child of T.
2. The inserted node is located at the right sub tree of the right child of T.
3. The inserted node is located at the right sub tree of the left child of T.
4. The inserted node is located at the left sub tree of the right child of T.
To re-balance, we do what is called rotation. For the 1st and 2nd possibilities can be fixed with a single rotation while the 3rd and 4th possibility are fixed with double rotation.
After inserting a new node, we have to restore the balance condition. We do this by first tracing the the new node to the root of the tree. For each node on this path, check if the heights og the left or right subtree are different at most 1. If yes, proceed to the parent node, however, if the difference is more than 1, we have to fix the subtree by single or double rotation.
LL rotation: the new node is inserted in
the left sub-tree of the left sub-tree of the critical node
RR rotation: the new node is inserted in
the right sub-tree of the right sub-tree of the critical node.
LR rotation: the new node is inserted in
the right sub-tree of the left sub-tree of the critical node
RL rotation: the new node is inserted in
the left sub-tree of the right sub-tree of the critical node
Single rotation:
Double rotation:
Deletion Operation:
This process is the same as deleting a node from a binary search tree but with roation afterwards to re-balance the tree.
