Deleting a Node in AVL Tree

•Delete a node similar to a binary search tree. Deletion may disturb the balance factor of an AVL tree and therefore the tree needs to be rebalanced in order to maintain the AVLness. For this purpose, we need to perform rotations.

There are two types of rotations L rotation and R rotation, L and R basically represent the subtree from where the node is deleted. For example if deleted node exist in left subtree, then it is L rotation case.

Understanding R- Rotations

Let us consider that, A is the critical node and B is the root node of its left sub-tree. If node X, present in the right sub-tree of A, is to be deleted, then there can be three different situations:

• R0 rotation (Node B has balance factor 0 ) (BF = L-R)
• If the node B has 0 balance factor, and the balance factor of node A disturbed upon deleting the node X, then the tree will be rebalanced by rotating tree using R0 rotation.
• Fixing Strategy => treat as Left Left (LL) Case  => Right Rotation at critical node

• R1 Rotation (Node B has balance factor 1)
• R1 Rotation is to be performed if the balance factor of Node B is 1.
• Fixing Strategy => treat as Left Left (LL) Case => Right Rotation at critical node

• R -1 Rotation (Node B has balance factor -1)
• R-1 rotation is to be performed if the node B has balance factor -1.
• In this case, the node C, which is the right child of node B, becomes the root node of the tree with B and A as its left and right children respectively.
• Fixing Strategy => treated as Left Right (LR) case. => Left Rotation at B and then Right Rotation at critical node(A)

Similarly the L Rotations can be handled. Click on link , to watch video on Deleting Nodes in AVL tree

To summarize, use the following rules of Rotation