RedBlackTrees: Insertion

Cases

Case 1: Aunt is red Swap the colors of the parent, aunt, and grandparent. Then, check if there are any other violations and fix if there are.
Case 2: Aunt is null Treat the aunt node as a black node. If parent is black and chidl is red, rotate. Else, rotate and swap colors between the grandparent and parent.
Case 3: Zig Zag When the child node is on the opposite side as the parent from the grandparent. Rotate the parent and child nodes. Then check for more violations and reapply cases on tree.

Learn More