// 1. Right Rotate (LL Case) Node* rightRotate(Node *y) { Node *x = y->left; Node *T2 = x->right; x->right = y; y->left = T2; // Update heights y->height = max(height(y->left), height(y->right)) + 1; x->height = max(height(x->left), height(x->right)) + 1; return x; } // 2. Left Rotate (RR Case) Node* leftRotate(Node *x) { Node *y = x->right; Node *T2 = y->left; y->left = x; x->right = T2; // Update heights x->height = max(height(x->left), height(x->right)) + 1; y->height = max(height(y->left), height(y->right)) + 1; return y; }
Inserted node is in the left subtree of the left child. Solution: Single Right Rotation.
Inserted node is in the right subtree of the right child. Solution: Single Left Rotation.
Left child's right subtree. Solution: Left-then-Right Rotation.
Right child's left subtree. Solution: Right-then-Left Rotation.