CS301 Lecture No. 22

CS301 Lecture No. 22
In the previous lecture, we discussed how to make insertions in the AVL tree. It was
seen that due to the insertion of a node, the tree has become unbalanced. Resultantly, it was difficult to fix it with the single rotation. We have analyzed the insertion method again and talked about the α node. The new node will be inserted at the left or right subtree of the α’s left child or at the left or right subtree of the α’s right child. Now the question arises whether the single rotation help us in balancing the tree or not. If the new node is inserted in the left subtree of the α’s left child or in the right subtree of α’s right child, the balance will be restored through single rotation.
However, if the new node goes inside the tree, the single rotation is not going to be
successful in balancing the tree.

We face four scenarios in this case. We said that in the case-1 and case-4, single
rotation is successful while in the case-2 and case-3 single rotation does not work.
Let’s see the tree in the diagram given below.