To verify whether the Red-Black tree is still balanced and still follows all of its requirements, we will use two concepts: recoloring and rotation.
After inserting a new node into the tree, this new node will be red. This does not affect the rule of the count of black nodes (rule 6), but it can affect rule 5: two adjacent red nodes cannot coexist. If the parent of the inserted node is black, then there is no problem. However, if the parent of the inserted node is red, then we have a violation of rule 5. To solve this violation, we simply need to change the color of the node's parent, the node's grandparent, and the node's uncle (because we are changing the parent color as well).
The ...
