Red-Black Tree

A Red-Black Tree should satisfy the following four conditions:

1. It is a binary search tree.

2. The root and leaves are black.

3. There are no two consecutive red nodes.

4. Every path from a node to its leaf nodes has the same number of black nodes.

   

Insertion

When inserting a node, the default color is red.

1. If the inserted node is the root, change it to black.
2. If the inserted node’s uncle is red, recolor the parent, uncle, and grandparent (f, u, g) to maintain balance, with g becoming the new insertion node.
3. If the inserted node’s uncle is black, apply rotations and recoloring (depending on LL, RR, LR, RL cases):
   • LL: Right rotation.
   • RR: Left rotation.
   • LR: Left rotation on the left child followed by a right rotation.
   • RL: Right rotation on the right child followed by a left rotation.

Deletion

1. Node with only left or right child: Replace the node with its child and recolor it to black.
2. Node with no children:
   • If the node is red: No adjustment is needed after deletion.
   • If the node is black (resulting in double black):
     • Sibling (s) is black:
       • If s has at least one red child: Use rotations (LL, RR, LR, RL) and recoloring to resolve the double black:
         • LL, RR: Recolor by setting the red node (r) to the sibling (s), s to parent (p), and p to black.
         • LR, RL: Recolor by setting the red node (r) to p, and p to black.
       • If s has all black nodes: Change s to red and move the double black upwards. When a red node or the root is encountered, convert the double black to a single black.
     • Sibling (s) is red:
       • Recolor s and p, and rotate towards the double black node to balance the tree.