CS301 Lecture No. 21

CS301 Lecture No. 21
Cases of Rotation
The single rotation does not seem to restore the balance. We will re-visit the tree and
rotations to identify the problem area. We will call the node that is to be rotated as α
(node requires to be re-balanced). Since any node has at the most two children, and a
height imbalance requires that α’s two sub-trees differ by two (or –2), the violation
will occur in four cases:
1. An insertion into left subtree of the left child of α.
2. An insertion into right subtree of the left child of α.
3. An insertion into left subtree of the right child of α.
4. An insertion into right subtree of the right child of α.