AVL Tree Insertion and Deletion Algorithm

AVL Tree in Data Structure

AVL stands for Adelson Velskii Landis. In Data Structure, AVL Tree is a binary search tree in which the balance factor of any node can have only three values -1, 0 or 1. The name AVL comes from the Russian mathematician G.M Adelson – Velskii – E.M. Landis developed this tree in 1962.

Balance factor = height of left sub-tree (h1) – height of right sub-tree (h2)

AVL Tree Insertion

At first, insert an item into the AVL tree according to the rules of insertion into a binary search tree. Then check whether the tree balanced or not. If it is unbalanced, then find the nearest ancestor node to the inserted node to the root node. It says the pivot node. Then it performs one of the following four rotations on the unbalanced tree to make it balanced. It depends on some criteria:

1. Left to Left Rotation: When the pivot node is left heavy and the new node is inserted in the left subtree of the left child of the pivot node. Then the rotation performs left to left rotation.

2. Right to Right Rotation: When the pivot node is right heavy and the new node is inserted in the right subtree of the right child of the pivot node. Then the rotation performed is right to right rotation.

3. Left to Right Rotation: When the pivot node is left heavy and the new node is inserted in the right subtree of the left child of the pivot node. Then the rotation performed is left to right rotation.

4. Right to Left Rotation: When the pivot node is right heavy and the new node inserts in the left subtree of the right child of the pivot node. Then the rotation performs right to left rotation.

AVL Tree Deletion

If the deletion of a node from an AVL search tree makes the tree unbalanced, then first find the pivot node in the tree. Now, perform the following rotations on the unbalanced tree to make it balance.

1. R0 Rotation: If deletion takes place from the right subtree of P and the balance factor of the left child (A) of P is 0. Then it performs R0 rotation.

2. R1 Rotation: If deletion takes place from the right subtree of P and the balance factor of the left child (A) of P is 1, then perform R1 rotation.

3. R-1 Rotation: If deletion takes place from the right subtree of P and the balance factor of the left child (A) of P is -1. Then it performs R2 rotation.

4. L0 Rotation: If deletion takes place from the left subtree of P and the balance factor of the right child (A) of P is 0. Then it performs L0 rotation.

5. L1 Rotation: If deletion takes place from the left subtree of P and the balance factor of the right child (A) of P is 1, then perform L1 rotation.

6. L-1 Rotation: If deletion takes place from the left subtree of P and the balance factor of the right child (A) of P is -1. Then it performs L2 rotation.