Insert operation in AVL Tree
- Insertion into Left sub-tree of nodes Left child – Single Right Rotation.
- Insertion into Right sub-tree of node’s Left child – Left Right Rotation.
- Insertion into Left sub-tree of node’s Right child – Right Left Rotation.
- Insertion into Right sub-tree of node’s Right child – Single Left Rotation.
1) Insertion into Left sub-tree of nodes Left child – Single Right Rotation
If node becomes unbalanced after insertion of new node at Left sub-tree of nodes Left child, then we need to perform Single Right Rotation for unbalanced node.
Right Rotation
- Detach leaf child’s right sub-tree.
- Consider leaf child to be the new parent.
- Attach old parent onto right of new parent.
- Attach old leaf child’s old right sub-tree as leaf sub-tree of new right child.
2) Insertion into Right sub-tree of node’s Left child – Left Right Rotation
If node becomes unbalanced after insertion of new node at Right sub-tree of node’s Left child, then we need to perform Left Right Rotation for unbalanced node.
Left rotation of left child followed by right rotation of parent
3) Insertion into Left sub-tree of node’s Right child – Right Left Rotation
If node becomes unbalanced after insertion of new node at Left sub-tree of node’s Right child, then we need to perform Right Left Rotation for unbalanced node.
Single right rotation of right child followed by left rotation of parent
4) Insertion into Right sub-tree of node’s Right child – Single Left Rotation
If node becomes unbalanced after insertion of new node at Right sub-tree of nodes Right child, then we need to perform Single Left Rotation for unbalanced node.
Left Rotation
- Detach right child’s leaf sub-tree.
- Consider right child to be new parent.
- Attach old parent onto left of new parent.
- Attach old right child’s old left sub-tree as right sub-tree of new left child.
Deleting node from AVL Tree
- If element to be deleted does not have empty right sub-tree, then element is replaced with its In-Order successor and its In-Order successor is deleted instead.
- During winding up phase, we need to revisit every node on the path from the point of deletion upto the root, rebalance the tree if require.
Example of deleting a node from AVL Tree
We are given AVL Tree. Delete node 28 & 31 and draw the tree after each deletion