Red Black Trees are a data structure that a specific type of balanced binary tree. In order to maintaine it's balance and have a search, insert, and delete time complexity of O(logn), it has rules that ensure that deleting or inserting nodes into the tree doesn't mess up the structure, order, and rules.
1. All nodes must be colored red or black.
2. The root node of the RBT must be black.
3. A red node parent can not have a red child.
4. The height of the black nodes must be the same throughout the tree.
5. All leaf nodes must be colored black.
Inserting nodes into an RBT tree is a tricky process. All the rules must be followed while inserted the node, so restructuring and recoloring are an important part of insertion. First, start with inserting the node as a normal Binary Search Tree insert. Then recheck via the insertion rules below.
First case folllows that if the uncle is red, then the parent and uncle node of the inserted child should be recolored to black. Then recur upwards in the tree to check for other violations.
If the node is a right child, then a left rotation should be done on the parent.
If the node is a left child, then a right rotation should be done on the grandparent node. The nodes should be recolored.
The parent node needs to be rotated and the sibling and parent nodes need to be recolored.
Rotate the parent node and the sibling node and recolor the nodes.
Rotate the sibling and child node, and then recheck the steps above.
