Red-Black trees are a type of self-balancing binary search tree that use color-coding to maintain balance. They ensure efficient operations by keeping the tree's height logarithmic, making them ideal for applications requiring fast searches and updates.

These trees have specific properties and rules for insertion and deletion. By following these guidelines, Red-Black trees maintain their balance, guaranteeing logarithmic time complexity for key operations like search, insertion, and deletion.

Red-Black Tree Properties

Properties of Red-Black trees

• Assigns color attribute to each node either red or black to ensure balanced tree structure
• Root node always colored black to maintain consistency
• All leaf nodes (NIL or null) treated as black nodes for balancing purposes
• Red nodes cannot have red children prevents long paths of red nodes and maintains balance
• Equal number of black nodes along any path from root to leaf (black-height) ensures no path is more than twice as long as any other

Red-Black Tree Operations

Insertion in Red-Black trees

• New nodes initially colored red to minimize impact on tree balance
• Black parent requires no further action maintains valid tree structure
• Red parent triggers checks and adjustments:
  • Black sibling (or null) prompts rotations and color flips:
    1. Left-Left (LL) imbalance resolved by right rotating grandparent and flipping colors
    2. Left-Right (LR) imbalance fixed by left rotating parent then following LL steps
    3. Right-Right (RR) imbalance resolved by left rotating grandparent and flipping colors
    4. Right-Left (RL) imbalance fixed by right rotating parent then following RR steps
  • Red sibling requires color flip of parent, sibling, and grandparent then recheck from grandparent

Deletion in Red-Black trees

• Node replaced by successor (minimum in right subtree) or predecessor (maximum in left subtree)
• Deleting red node maintains valid tree structure no further action
• Deleting black node disrupts black-height balance requires fixes:
  1. Red successor/predecessor recolored black to replace deleted node
  2. Black successor/predecessor with red child recolors child black and replaces deleted node
  3. Black successor/predecessor lacking red child triggers color flips and rotations considering sibling color and children colors to restore balance

Time complexity of Red-Black trees

• Search: $O(\log n)$ worst case follows longest path at most twice shortest path due to black-height balance
• Insertion: $O(\log n)$ constant time insertion but color flips and rotations may traverse to root
• Deletion: $O(\log n)$ constant time deletion but color flips and rotations may traverse to root in worst case