Insertion Algorithm in Red Black Tree

This page seeks to explain how to implement a Red Black Tree insertion algorithm, as taught in CS400 at UW Madison.

Steps to insert into a Red Black Tree

1. Refer to this Follow Along Guide as you complete the steps!

2. Determine if aunt of the newly inserted node is red or black. To do this, go up twice to the grandparent node of the newly inserted node, and go one node down on the opposite tree. This is the aunt node.

3. If aunt is red, turn the grandparent node red, and recolor the parent and the aunt node to black.

4. If aunt is black, check whether the newly inserted node is the same type of node as its parent (Left child or Right child).

5. If both are the same type of node (Left/Right child), rotate the parent and the grandparent, and then swap the colors of the parent and grandparent.

6. If both are not the same type of node (Left/Right child), rotate the child and the parent, in order to make them the same type of node, then refer to step 4.

7. CONGRATULATIONS! You have successfully learned the insertion algorithm for a Red Black Tree!