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 α.
