Red-Black Tree Insertion

In order to insert into a red black tree, we should be very careful about the color of aunt node, which is node of grandparent's another child...

Case 1: The aunt node is red

1. Switch the color of grandparent node
2. Switch the color of parent and aunt nodes

By doing so, you solved the problem of this level, and leave the problem for the next level to solve

Case 2: The aunt node is black & parent and child nodes are aligned

1. Right or left rotation of parent and grandparent nodes. Depending of whether the parent is the right child of grandparent.
2. Switch the color of parent and grandparent

By doing so, you completely solved the problem

Case 3: The aunt node is black & parent and child nodes are not aligned

1. Right or left rotation of parent and child nodes, in order to make them aligned
2. After they aligned, this will become case2, therefore, follow the steps of case 2

By doing so, you completely solved the problem

The following image summarize the three cases

For more information, you can visit the website information