Data Structure (2130702)

Insert operation in AVL Tree

1. Insertion into Left sub-tree of nodes Left child – Single Right Rotation.
2. Insertion into Right sub-tree of node’s Left child – Left Right Rotation.
3. Insertion into Left sub-tree of node’s Right child – Right Left Rotation.
4. 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

1. Detach leaf child’s right sub-tree.
2. Consider leaf child to be the new parent.
3. Attach old parent onto right of new parent.
4. 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

1. Detach right child’s leaf sub-tree.
2. Consider right child to be new parent.
3. Attach old parent onto left of new parent.
4. 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