Insertion
Insertion in AVL tree is performed in the same way as it is performed in a binary search tree. The new node is added into AVL tree as the leaf node. However, it may lead to violation in the AVL tree property and therefore the tree may need balancing.
The tree can be balanced by applying rotations. Rotation is required only if, the balance factor of any node is disturbed upon inserting the new node, otherwise the rotation is not required.
Depending upon the type of insertion, the Rotations are categorized into four categories.
| SN | Rotation | Description |
|---|---|---|
| 1 | LL Rotation | The new node is inserted to the left sub-tree of left sub-tree of critical node. |
| 2 | RR Rotation | The new node is inserted to the right sub-tree of the right sub-tree of the critical node. |
| 3 | LR Rotation | The new node is inserted to the right sub-tree of the left sub-tree of the critical node. |
| 4 | RL Rotation | The new node is inserted to the left sub-tree of the right sub-tree of the critical node. |
Q. Construct an AVL tree by inserting the following elements in the given order.
63, 9, 19, 27, 18, 108, 99, 81
The process of constructing an AVL tree from the given set of elements is shown in the following figure.
At each step, we must calculate the balance factor for every node, if it is found to be more than 2 or less than -2, then we need a rotation to rebalance the tree. The type of rotation will be estimated by the location of the inserted element with respect to the critical node.
All the elements are inserted in order to maintain the order of binary search tree.
