Data Structure (2130702)

BE | Semester-3   Summer-2019 | 06/04/2019

Q4) (c)

Explain insert and delete operations in AVL trees with suitable examples.

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.
AVL Tree Right Rotation

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
AVL Tree - 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
AVL Tree - 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.
AVL Tree Left Rotation AVL Tree Left Rotation Example

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

AVL Tree delete node AVL Tree delete node number 28 AVL Tree delete node number 30