Summary
Highlights
A red-black tree requires the root node to be black and prohibits two red nodes from being directly connected. Newly inserted nodes are initially red, unless they are the root, in which case they are black. There are two main cases for handling red-red conflicts: if the uncle is black or null, perform rotation and recoloring; if the uncle is red, recolor the parent and uncle to black and the grandparent to red, then repeat the process upwards.
Next, 60 is inserted, creating another red-red conflict. This time, the uncle is red (case two). The parent and uncle are recolored to black, and the grandparent (30) would normally become red, but since it's the root, it remains black.
20 is inserted without conflict. When 10 is inserted, a red-red conflict arises. With no uncle, a left-left rotation is performed. Node 20 becomes black, and 30 becomes red.
70 is inserted, leading to a right-right rotation due to no uncle; 60 becomes black, and 50 becomes red. 80 is inserted, and its red uncle triggers recoloring: parent and uncle become black, grandparent becomes red. 90 is inserted, and a left rotation is performed due to no uncle, making 80 black and 70 red.
Finally, 100 is inserted, and its red uncle triggers recoloring (parent and uncle black, grandparent red). This creates another red-red problem for which the uncle is black, leading to a left rotation where 60 becomes black and 40 becomes red, completing the insertion process.
First, 30 is inserted as the black root. Then 40 is inserted as a red child without conflict. When 50 is inserted, a red-red conflict occurs. Since there is no uncle (it's null), a right-right rotation is performed. Node 40 becomes black, and 30 becomes red.