Red-Black Tree Operations

Rotations

A rotation is a local tree restructuring that preserves the BST ordering property and runs in $\Theta(1)$ time. Two symmetric operations:

• Left-rotate(T, x): node x’s right child y becomes the new parent; x becomes y’s left child; y’s former left subtree becomes x’s right subtree.
• Right-rotate(T, y): the inverse operation.

Rotations are the core mechanism for rebalancing after insertions and deletions. They change the structure without affecting the inorder traversal order.

Insertion

Standard BST insertion is performed first: the new node is added as a leaf and coloured red. This preserves Property 5 (black-height) but may violate Property 4 (red parent with red child) or Property 2 (red root).

If the new node’s parent is black, no fix is needed (Case 0). Otherwise, the insertion fix-up has three cases, distinguished by the colour of the uncle (the parent’s sibling).

Case 1: Uncle is Red

Both the parent and uncle are red. This corresponds to a 4-node in the 2-3-4 tree that has received an extra key.

Fix: Recolour the parent, uncle, and grandparent. The parent and uncle become black; the grandparent becomes red. The grandparent may now violate Property 4 against its own parent, so the problem moves up two levels. Repeat the fix-up from the grandparent.

Case 2: Uncle is Black, Node is a “Zig-Zag”

The new node is the right child of a left parent (or left child of a right parent). This is a “bent” configuration.

Fix: Rotate the parent away from the new node (left-rotate the left parent, or right-rotate the right parent). This transforms the situation into Case 3. The node that was the parent becomes the child.

Case 3: Uncle is Black, Node is a “Zig-Zig”

The new node is the left child of a left parent (or right child of a right parent). This is a “straight” configuration.

Fix: Rotate the grandparent in the opposite direction (right-rotate if both are left children, left-rotate if both are right children). Then recolour: the parent becomes black, the grandparent becomes red. This terminates the fix-up.

Example Walkthrough

Insert 4 into:

    5B
   /  \
  3R  NIL
 /
2R

4 is inserted as right child of 3R (Case 2: zig-zag). Left-rotate 3:

    5B
   /  \
  4R  NIL
 /
3R

Now 4R and 3R form a zig-zig (Case 3). Right-rotate 5 and recolour: 4 becomes black, 5 becomes red, 3 stays red. Final tree is valid.

Deletion (Outline)

Deletion is more complex than insertion. The high-level approach:

1. Perform standard BST deletion.
2. If the removed node was black, a “double-black” violation occurs at its replacement position (a path now has one fewer black node).
3. Fix the double-black by considering the sibling’s colour and its children’s colours, using rotations and recolouring.
4. Cases include: sibling is red (rotate and recolour to make sibling black), sibling is black with two black children (recolour sibling red, push double-black upward), sibling is black with at least one red child (rotate and recolour to absorb the extra black).

Full deletion is examinable at the concept level but not in exhaustive case-analysis detail. The key point: all fix-up cases run in $O(1)$ per level visited, and the problem moves up at most $O(\log n)$ levels.

Practical Considerations

Red-black trees require fewer rotations on average than AVL trees for insertions, making them preferred in practice (e.g. Linux kernel’s CFS scheduler, Java’s TreeMap, C++ STL std::map). Both guarantee $O(\log n)$ worst-case height; the constant factors favour red-black for insert-heavy workloads and AVL for search-heavy workloads.

Summary

Operation	Time	Notes
Rotate	$\Theta(1)$	Preserves BST order
Insert (BST phase)	$O(\log n)$	Colour new node red
Insert fix-up	$O(\log n)$	3 cases, at most 2 rotations
Case 1	Uncle red	Recolour, move up
Case 2	Uncle black, zig-zag	Rotate parent, reduces to Case 3
Case 3	Uncle black, zig-zig	Rotate grandparent, recolour, done
Delete (BST phase)	$O(\log n)$	Standard BST deletion
Delete fix-up	$O(\log n)$	Fix double-black violations