Red-Black Trees

Definition

• A Red-Black Tree is a self-balancing Binary Search Tree where every node carries an extra color attribute (red or black), and a set of coloring rules is enforced after every insertion/deletion to keep the tree approximately balanced — guaranteeing O(log n) height without requiring the strict balance-factor bookkeeping an AVL tree needs.

The 5 Red-Black Properties

1. Every node is either red or black.
2. The root is always black.
3. Every leaf (the NIL/null sentinel children) is black.
4. No red node has a red child — a red node's children must both be black (no two reds in a row on any path).
5. Every path from a given node down to any of its descendant NIL leaves contains the same number of black nodes (the node's black-height).

Properties 4 and 5 together bound the height: the longest possible root-to-leaf path (alternating red/black) can be at most twice as long as the shortest (all black), giving a guaranteed $O(\log n)$ height for n nodes.

Rebalancing After Insertion

A newly inserted node is always colored red first (this can't violate property 5, since a red node adds nothing to any black-height count) — but it may violate property 4 if its parent is also red. Fix depends on the color of the node's uncle (the parent's sibling):

• Uncle is red → recolor only: flip parent and uncle to black, grandparent to red, then re-check the violation one level up (may cascade toward the root).
• Uncle is black (or NIL) → rotate + recolor, using the same four shape cases as AVL (LL, RR, LR, RL), fixing the violation in O(1) rotations without needing to continue upward.

Red-Black vs AVL vs Plain BST

Exam Angle

Examiners expect you to trace an insertion sequence and show the color of every node at each step, naming whether each fix was a recolor or a rotation. The recurring trap: forgetting that the root must always be re-colored black at the very end, even if a recoloring step temporarily made it red.

📌 Sample & Repeated FPSC Questions (2016–2026)

📝 Full Construction Trace — Ascending vs Descending Insertion

2017, Paper I, Q5(a) (8 marks) — Draw and build a Red-Black tree for the following keys (50, 60, 70, 80, 90) and (50, 40, 30, 20, 10). Would a binary tree be suitable for the insertion of these keys?

Tree 1 — inserting 50, 60, 70, 80, 90 (ascending order):

• Insert 50 → root, colored black (property 2).
• Insert 60 → red, right child of 50 (black parent) → no violation.
• Insert 70 → red, right child of 60 (red parent) → violation. Uncle (50's other child) is NIL/black → RR case: left-rotate at 50, recolor. New subtree: 60(black), left=50(red), right=70(red).
• Insert 80 → red, right child of 70 (red parent) → violation. Uncle = 50, which is red → recolor only: 70→black, 50→black, 60→red; since 60 is root, recolor it back to black.
• Insert 90 → red, right child of 80 (red parent) → violation. Uncle (70's other child) is NIL/black → RR case: left-rotate at 70, recolor. New subtree under 60's right: 80(black), left=70(red), right=90(red).

     60(B)
   /      \
50(B)     80(B)
          /    \
        70(R)  90(R)

Tree 2 — inserting 50, 40, 30, 20, 10 (descending order):

• Insert 50 → root, black.
• Insert 40 → red, left child of 50 → no violation.
• Insert 30 → red, left child of 40 (red parent) → violation. Uncle is NIL/black → LL case: right-rotate at 50, recolor. New subtree: 40(black), left=30(red), right=50(red).
• Insert 20 → red, left child of 30 (red parent) → violation. Uncle = 50, which is red → recolor only: 30→black, 50→black, 40→red → recolor root back to black.
• Insert 10 → red, left child of 20 (red parent) → violation. Uncle is NIL/black → LL case: right-rotate at 30, recolor. New subtree under 40's left: 20(black), left=10(red), right=30(red).

         40(B)
       /      \
    20(B)     50(B)
   /    \
10(R)  30(R)

Would a plain binary tree be suitable? No. Inserting keys already in sorted order (ascending or descending) into a plain, unbalanced BST produces a fully skewed tree — effectively a linked list of height n — giving O(n) search/insert/delete instead of O(log n). Both traces above end at height 2–3 for 5 nodes precisely because the Red-Black recoloring/rotation rules intervened at every violation; a plain BST has no such mechanism and would have degenerated to a straight chain (50→60→70→80→90, or the mirror image) in exactly this scenario — which is the whole motivation for using a self-balancing structure whenever the insertion order can't be guaranteed random.

📜 Past-Paper Questions & MCQs (CSS 2016–2026)

2017 · Paper-I · Q5(a) · 8 marks

Q. Draw and build a red-black tree for the keys (50, 60, 70, 80, 90) and (50, 40, 30, 20, 10). Would a binary tree be suitable for inserting these keys?

Ans.

• Rules: the root is black, a red node has black children, and every path from a node to its leaves has the same number of black nodes. A new node is red.
• Keys 50, 60, 70, 80, 90:
  • 50 is the root (black). 60 is red.
  • 70 is red under a red parent with no uncle: left rotation, recolour. Tree: 60(50, 70).
  • 80: uncle 50 is red, so recolour 50 and 70 black and 60 red, then make the root black. 80 is red.
  • 90: parent 80 is red with no uncle: left rotation at 70, recolour.

      60 (B)
    /        \
50 (B)      80 (B)
            /     \
        70 (R)   90 (R)

• Keys 50, 40, 30, 20, 10 (mirror image): the same steps with right rotations.

          40 (B)
        /        \
    20 (B)      50 (B)
    /     \
10 (R)   30 (R)

• Is a plain binary search tree suitable? No. Sorted keys give a skewed tree, which is a chain of height 5 and O(n) search. The red-black tree keeps the height near log n.