Implementation
Rotation
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.
Pic:
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