Left rotate: 2 nodes with 3 childrens, childrens have same relative postion, and move underneath nodes from right child to left child. Exchange the 2 nodes.


3. At most one above is violated.

There are 6 cases, but 3 of them are symmetric(z’s parent is a left child or right child)
Known: z.p.p exists

Core: Make Root RED

Case1: z’s uncle y is RED EZ
Uncle = parent neighbour
Known: Both z.p and y are RED
Change them BLACK, and color z.p.p RED, make z two levels up.

Case2 && 3
Case 2 can change to 3
Case 2: z’s uncle y is black and z is right child
Use a LeftRotation to case 3(From right child to left child)

Case 3: z’s uncle y is black and z is left child