What is Red-Black Tree?

A Red-Black Tree is self-balancing binary search tree (BST). It ensures that the tree remains approximately balanced at all times, guaranteeing O(log n) time complexity for insertion, deletion, and searching operations. But what makes an RBT different from a normal BST? It assigns a color (🟥 or ⬛) to each node and enforces certain rules that control how nodes can be linked together.

Properties of a Red-Black Tree

A Red-Black Tree must satisfy these five properties:

1. Each node is either red or black.
2. The root node must be black.
3. All leaves (null nodes) are considered black.
4. If a node is red, then both of its children must be black.
5. Every path from a node to its descendant leaves must have the same number of black nodes.

These simple rules prevent the tree from being too unbalanced (degenerate).

How Red-Black Tree maintain balance

When we insert or delete nodes, Red-Black Tree may temporarily violate one or more of their properties. To fix these violations, the tree uses:

1. Recoloring - changing node colors
2. Rotations - restructuring the tree

These operations restore the Red-Black Tree rules and keep the tree balanced. One of the key strengths of the Red-Black Tree is that its height is always logarithmic relative to the number of nodes.

• The maximum height of a Red-Black Tree with n nodes is:
• h(t) ≤ 2log2(n(t) + 1)

This means the height difference between the longest and shortest paths from the root is at most 2, so the tree remains efficiently balanced. In short, tree height is kept at O(log n) due to Red-Black balancing rules.

Search in Red-Black Tree

Searching in an RBT is just like in any Binary Search Tree (BST).
How it works:

1. Start at the root.
2. Compare the target value to the current node.
3. If it's equal, return the node. If it's smaller, go left. If it's larger, go right.
   Repeat until you find the value or hit a null.

Time Complexity: O(log n)

Why? Searching is a traversal from root to a leaf, so it’s bounded by the tree’s height.

Insertion in Red-Black Tree

Insertion starts like a normal BST insertion, but additional steps are required to restore red-black properties. How it works:

1. Insert the new node as a red leaf using BST rules.
2. Fix any violations of RBT rules by recoloring and rotations: If the parent is black: no action needed. If the parent is red: violation -> Resolve using Case 1 (recoloring) or Case 2/3 (rotations) depending on the uncle’s color. Left Rotation and Right Rotation help move the red node down and balance the tree. These are constant-time operations.

Time Complexity: O(log n)

Why? The fixing process involves at most O(log n) steps due to the tree's height.

Deletion in Red-Black Tree

Deletion is more complex than insertion due to the possibility of black-height imbalance. Steps: Use BST deletion rules: If the node has two children, replace it with its in-order successor or predecessor. If the deleted node or its replacement is black, RBT properties may be violated. Restore balance using: Recoloring Rotations Double black fix-up strategies (extra blackness passed up the tree) This process ensures the red-black properties are maintained even after deletion.

Time Complexity: O(log n)

Why? Although more complicated than insertion, the fix-up still takes logarithmic time.

Time Complexity Summary

Operation	Time Complexity
Search	O(log n)
Insertion	O(log n)
Deletion	O(log n)

Thanks to its balancing rules, a Red-Black Tree ensures all basic operations stay efficient even in the worst case.