---
title: "Red-Black tree and its purpose"
subject: "Data Structure and Algorithm"
chapter: 6
key: "semester_4/data_structure_and_algorithm:red-black-tree"
source: https://www.bctengineer.com/q/semester_4/data_structure_and_algorithm/red-black-tree
site: BCT Engineering
---

# Red-Black tree and its purpose

Data Structure and Algorithm · Chapter 6: Trees

- Asked in: 2070 Magh, 2 marks; 2068 Magh, 2 marks (asked 2 times)
- Video: [Lec-62: Introduction to Red-Black Tree | Data Structure for Beginners](https://www.youtube.com/watch?v=hq_3iqS0Hq0) — Gate Smashers
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_4/data_structure_and_algorithm/red-black-tree
- Whole chapter: https://www.bctengineer.com/md/semester_4/data_structure_and_algorithm/chapter-6

## Question

Define Red-Black tree and mention its purpose.

## Short answer

A Red-Black tree is a self-balancing BST where each node is red or black; properties include a black root, no consecutive red nodes, and equal black-height on all paths. It guarantees O(log n) search, insertion, and deletion by cheap recoloring and rotations, used in C++ STL map and Java TreeMap.

## Answer

#### Definition
A **Red-Black tree** is a self-balancing binary search tree in which every node has an extra bit of information, its colour (red or black). The colours obey these rules:

1. Every node is either red or black.
2. The root is black.
3. Every leaf (NIL / null link) is black.
4. A red node cannot have a red child (no two red nodes in a row).
5. Every path from a node to its descendant leaves has the same number of black nodes (equal black-height).

These rules guarantee that the longest path from the root is at most twice the shortest path, so the tree height is at most 2·log₂(n + 1).

```text
        13(B)
       /     \
    8(R)      17(R)
   /   \     /    \
 1(B) 11(B) 15(B)  25(B)
```

#### Purpose
- An ordinary BST can become skewed and degrade to O(n) search. A Red-Black tree keeps the height O(log n), so search, insertion and deletion all take O(log n) time in the worst case.
- It restores balance after an update using only recolouring and at most 2 rotations on insertion (3 on deletion), so updates are cheaper than in a strict AVL tree.
- It is used where frequent insertions and deletions occur, e.g. `map`/`set` in the C++ STL, Java `TreeMap`, and process scheduling in the Linux kernel.

## Check yourself

The answer's key points as multiple-choice questions, with the correct option and why.

1. What is a Red-Black tree?
   A. An unsorted tree with colours
   B. A self-balancing BST with a colour bit on each node
   C. A graph with red edges
   D. A heap of two colours
   Answer: B. Colour rules keep the tree balanced. (Key point: Definition)

2. Which rule is correct?
   A. Root is red
   B. Leaves are red
   C. A red node cannot have a red child
   D. Black heights may differ
   Answer: C. No two red nodes in a row; root and leaves black; equal black-height. (Key point: Rule)

3. What is the purpose of a Red-Black tree?
   A. Make search O(1)
   B. Store unsorted data
   C. Avoid rotations entirely
   D. Keep height O(log n) so search, insert and delete are O(log n) worst case
   Answer: D. Longest path is at most twice the shortest. (Key point: Purpose)

## Related in other subjects

- [Earthing purpose and points to be earthed](https://www.bctengineer.com/question.md?key=semester_6%2Findustrial_power_distribution_and_illumination%3Aearthing-purpose-points-earthed) — Industrial Power Distribution and Illumination, chapter 2, asked 2×
- [Role of parse tree in CFG](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Aparse-tree-role) — Theory of Computation, chapter 3
- [Three urns; both balls from Urn B](https://www.bctengineer.com/question.md?key=semester_5%2Fprobability_and_statistics%3Aurns-red-black-both-from-b) — Probability and Statistics, chapter 1
- [Resistor value from colour code](https://www.bctengineer.com/question.md?key=semester_2%2Fbasic_electronics_engineering%3Aresistor-color-code-value) — Basic Electronics Engineering, chapter 1