AVL TREE

Rotating the subtrees in an AVL Tree

In rotation operation, the positions of the nodes of a subtree are interchanged.
There are two types of rotations:
In left-rotation, the arrangement of the nodes on the right is transformed into the arrangements on the left node.
Algorithm

1. Let the initial tree be:
   

   

2. If y has a left subtree, assign x as the parent of the left subtree of y.
   

   

3. If the parent of x p is NULL, make y as the root of the tree.
4. Else if x is the left child of p, make y as the left child of p.
5. Else assign y as the right child of p.
   

   

6. Make y as the parent of x.
   

   

---

Right Rotate

In left-rotation, the arrangement of the nodes on the left is transformed into the arrangements on the right node.

1. Let the initial tree be:
   

   

2. If x has a right subtree, assign y as the parent of the right subtree of x.
   

   

3. If the parent of y is NULL, make x as the root of the tree.
4. Else if y is the right child of its parent p, make x as the right child of p.
5. Else assign x as the left child of p.
   

   

6. Make x as the parent of y.
   

   

---

Left-Right and Right-Left Rotate

In left-right rotation, the arrangements are first shifted to the left and then to the right.

1. Do left rotation on x-y.
   

   

2. Do right rotation on y-z.
   

   

In left-right rotation, the arrangements are first shifted to the right and then to the left.

1. Do right rotation on x-y.
   

   

2. Do left rotation on z-y.
   

   

---

Algorithm to insert a newNode

A newNode is always inserted as a leaf node with balance factor equal to 0.

1. Let the initial tree be:
   

   

   
   Let the node to be inserted be:
   

   

2. Go to the appropriate leaf node to insert a newNode using the following recursive steps. Compare newKey with rootKey of current tree.
   1. If newKey < rootKey, call insertion algorithm on left subtree of current node until the leaf node is reached.
   2. Else if newKey > rootKey, call insertion algorithm on the right subtree of current node until the leaf node is reached.
   3. Else, return leafNode.
      

      

3. Compare leafKey obtained from above steps with newKey:
   1. If newKey < leafKey, make newNode as the leftChild of leafNode.
   2. Else, make newNode as rightChild of leafNode.
      

      

4. Update balanceFactor of the nodes.
   

   

5. If the nodes are unbalanced, then rebalance the node.
   1. If balanceFactor > 1, it means the height of the left subtree is greater than that of the right subtree. So, do right rotation or left-right rotation
      1. If newNodeKey < leftChildKey do right rotation.
      2. Else, do left-right rotation.
         

         

         

   2. If balanceFactor < -1, it means the height of the right subtree is greater than that of the left subtree. So, do right rotation or right-left rotation
      1. If newNodeKey > rightChildKey do left rotation.
      2. Else, do right-left rotation
6. The final tree is:
   

   

---

Algorithm to Delete a node

A node is always deleted as a leaf node. After deleting a node, the balance factors of the nodes get changed. In order to rebalance the balance factor, suitable rotations are performed.

1. Locate nodeToBeDeleted (recursion is used to find nodeToBeDeleted in the code used below).
   

   

2. There are three cases for deleting a node:
   1. If nodeToBeDeleted is the leaf node (ie. does not have any child), then remove nodeToBeDeleted.
   2. If nodeToBeDeleted has one child, then substitute the contents of nodeToBeDeleted with that of child. Remove the child.
   3. If nodeToBeDeleted has two children, find the inorder successor w of nodeToBeDeleted (ie. node with minimum value of key in the right subtree).
      

      

      1. Substitute the contents of nodeToBeDeleted with that of w.
         

         

      2. Remove the leaf node w.
         

         

3. Update balanceFactor of the nodes.
   

   

4. Rebalance the tree if balance factor of any of the nodes is not equal to -1, 0 or 1.
   1. If balanceFactor of currentNode > 1,
      1. If balanceFactor of leftChild >= 0, do right rotation.
         

         

      2. Else do left-right rotation.
   2. If balanceFactor of currentNode < -1,
      1. If balanceFactor of rightChild <= 0, do left rotation.
      2. Else do right-left rotation.
5. The final tree is:
   

   

---