Red-Black Trees
Prof. Prateek Vishnoi
September 9, 2024
One Genuine Question???
Everyone’s Question
Prof. Prateek Vishnoi Red-Black Trees
One Genuine Question???
Everyone’s Question
Why DSA wants to make our life hell by introducing one more
Data Structure??
Prof. Prateek Vishnoi Red-Black Trees
Motivation
Remember from Prerequisite
Prof. Prateek Vishnoi Red-Black Trees
Motivation
Remember from Prerequisite
BST performs INSERT, DELETE, SEARCH operations in
O(log n) time if there height is O(log n).
Prof. Prateek Vishnoi Red-Black Trees
Motivation
Remember from Prerequisite
BST performs INSERT, DELETE, SEARCH operations in
O(log n) time if there height is O(log n).
If the height of BST blow up to Ω(n) then time complexity of
above operations become Ω(n)
Prof. Prateek Vishnoi Red-Black Trees
Motivation
Remember from Prerequisite
BST performs INSERT, DELETE, SEARCH operations in
O(log n) time if there height is O(log n).
If the height of BST blow up to Ω(n) then time complexity of
above operations become Ω(n)
What is the need of an hour??
Guarntee
Prof. Prateek Vishnoi Red-Black Trees
Motivation
Remember from Prerequisite
BST performs INSERT, DELETE, SEARCH operations in
O(log n) time if there height is O(log n).
If the height of BST blow up to Ω(n) then time complexity of
above operations become Ω(n)
What is the need of an hour??
Guarntee
Height of BST should be O(log n) for all possible inputs and all
above operations.
Prof. Prateek Vishnoi Red-Black Trees
Motivation
Remember from Prerequisite
BST performs INSERT, DELETE, SEARCH operations in
O(log n) time if there height is O(log n).
If the height of BST blow up to Ω(n) then time complexity of
above operations become Ω(n)
What is the need of an hour??
Guarntee
Height of BST should be O(log n) for all possible inputs and all
above operations.
Answer is Red-Black Trees
Prof. Prateek Vishnoi Red-Black Trees
Red Black Tree
An Informal Definition
Prof. Prateek Vishnoi Red-Black Trees
Red Black Tree
An Informal Definition
It is a BST with one extra bit of storage for color per node.
Prof. Prateek Vishnoi Red-Black Trees
Red Black Tree
An Informal Definition
It is a BST with one extra bit of storage for color per node.
Color of a node is either RED or BLACK.
Prof. Prateek Vishnoi Red-Black Trees
Red Black Tree
An Informal Definition
It is a BST with one extra bit of storage for color per node.
Color of a node is either RED or BLACK.
Each node of the tree now contains the attributes color, key,
left, right, and p.
Prof. Prateek Vishnoi Red-Black Trees
Red Black Tree
An Informal Definition
It is a BST with one extra bit of storage for color per node.
Color of a node is either RED or BLACK.
Each node of the tree now contains the attributes color, key,
left, right, and p.
Notice
Space Complexity of a single node is O(1).
Prof. Prateek Vishnoi Red-Black Trees
Red Black Tree
Properties
Prof. Prateek Vishnoi Red-Black Trees
Red Black Tree
Properties
A red-black tree is a binary search tree that satisfies the following :
Prof. Prateek Vishnoi Red-Black Trees
Red Black Tree
Properties
A red-black tree is a binary search tree that satisfies the following :
1 Every node is either red or black.
Prof. Prateek Vishnoi Red-Black Trees
Red Black Tree
Properties
A red-black tree is a binary search tree that satisfies the following :
1 Every node is either red or black.
2 The root is black.
Prof. Prateek Vishnoi Red-Black Trees
Red Black Tree
Properties
A red-black tree is a binary search tree that satisfies the following :
1 Every node is either red or black.
2 The root is black.
3 Every leaf (NIL) is black.
Prof. Prateek Vishnoi Red-Black Trees
Red Black Tree
Properties
A red-black tree is a binary search tree that satisfies the following :
1 Every node is either red or black.
2 The root is black.
3 Every leaf (NIL) is black.
4 If a node is red, then both its children are black.
Prof. Prateek Vishnoi Red-Black Trees
Red Black Tree
Properties
A red-black tree is a binary search tree that satisfies the following :
1 Every node is either red or black.
2 The root is black.
3 Every leaf (NIL) is black.
4 If a node is red, then both its children are black.
5 For each node, all simple paths from the node to descendant
leaves contain the same number of black nodes.
Prof. Prateek Vishnoi Red-Black Trees
Red Black Tree
Figure: Introduction to Algorithms, CLRS
Prof. Prateek Vishnoi Red-Black Trees
Red Black Tree
Figure: Introduction to Algorithms, CLRS
Black Height{ bh(x) }
For any node x, bh(x) represents number of black nodes in
simple path from x to leaf nodes(excluding x itself).
Prof. Prateek Vishnoi Red-Black Trees
Lemma
To Prove
A red-black tree with n internal nodes has height atmost
2 log(n + 1)
Prof. Prateek Vishnoi Red-Black Trees
Lemma
To Prove
A red-black tree with n internal nodes has height atmost
2 log(n + 1)
Proof.
1st Claim : Subtree rooted at any node x contains atleast
2bh(x) − 1 internal nodes.
Prof. Prateek Vishnoi Red-Black Trees
Lemma
To Prove
A red-black tree with n internal nodes has height atmost
2 log(n + 1)
Proof.
1st Claim : Subtree rooted at any node x contains atleast
2bh(x) − 1 internal nodes.
Prove it via mathematical induction on height of node x.
Prof. Prateek Vishnoi Red-Black Trees
Lemma
To Prove
A red-black tree with n internal nodes has height atmost
2 log(n + 1)
Proof.
1st Claim : Subtree rooted at any node x contains atleast
2bh(x) − 1 internal nodes.
Prove it via mathematical induction on height of node x.
Base Case : If the height of x is 0, then x is a leaf, acc. to
claim, # internal nodes is 20 − 1 = 0 internal nodes.
Prof. Prateek Vishnoi Red-Black Trees
Lemma
To Prove
A red-black tree with n internal nodes has height atmost
2 log(n + 1)
Proof.
1st Claim : Subtree rooted at any node x contains atleast
2bh(x) − 1 internal nodes.
Prove it via mathematical induction on height of node x.
Base Case : If the height of x is 0, then x is a leaf, acc. to
claim, # internal nodes is 20 − 1 = 0 internal nodes.
Consider node x with +ve height and is internal node with 2
children.
Prof. Prateek Vishnoi Red-Black Trees
Lemma
To Prove
A red-black tree with n internal nodes has height atmost
2 log(n + 1)
Proof.
1st Claim : Subtree rooted at any node x contains atleast
2bh(x) − 1 internal nodes.
Prove it via mathematical induction on height of node x.
Base Case : If the height of x is 0, then x is a leaf, acc. to
claim, # internal nodes is 20 − 1 = 0 internal nodes.
Consider node x with +ve height and is internal node with 2
children.
Each child has a black-height of either bh(x) or bh(x) − 1
Prof. Prateek Vishnoi Red-Black Trees
Lemma
Proof.
1st Claim : Subtree rooted at any node x contains atleast
2bh(x) − 1 internal nodes.
Prove it via mathematical induction on height of node x.
Base Case : If the height of x is 0, then x is a leaf, acc. to
claim, # internal nodes is 20 − 1 = 0 internal nodes.
Consider node x with +ve height and is internal node with 2
children.
Each child has a black-height of either bh(x) or bh(x) − 1
Prof. Prateek Vishnoi Red-Black Trees
Lemma
Proof.
1st Claim : Subtree rooted at any node x contains atleast
2bh(x) − 1 internal nodes.
Prove it via mathematical induction on height of node x.
Base Case : If the height of x is 0, then x is a leaf, acc. to
claim, # internal nodes is 20 − 1 = 0 internal nodes.
Consider node x with +ve height and is internal node with 2
children.
Each child has a black-height of either bh(x) or bh(x) − 1
Since, ht(child(x)) ≤ ht(x), from inductive hypothesis,
child(x) has atleast 2bh(x)−1 − 1 internal nodes.
Prof. Prateek Vishnoi Red-Black Trees
Lemma
Proof.
1st Claim : Subtree rooted at any node x contains atleast
2bh(x) − 1 internal nodes.
Prove it via mathematical induction on height of node x.
Base Case : If the height of x is 0, then x is a leaf, acc. to
claim, # internal nodes is 20 − 1 = 0 internal nodes.
Consider node x with +ve height and is internal node with 2
children.
Each child has a black-height of either bh(x) or bh(x) − 1
Since, ht(child(x)) ≤ ht(x), from inductive hypothesis,
child(x) has atleast 2bh(x)−1 − 1 internal nodes.
Thus, subtree rooted at x, contains atleast
(2bh(x)−1 − 1) + (2bh(x)−1 − 1) + 1 = 2bh(x) − 1 internal nodes.
Prof. Prateek Vishnoi Red-Black Trees
Lemma
Proof.
Subtree rooted at any node x contains atleast 2bh(x) − 1
internal nodes.
Prof. Prateek Vishnoi Red-Black Trees
Lemma
Proof.
Subtree rooted at any node x contains atleast 2bh(x) − 1
internal nodes.
Let h be the height of tree.
Prof. Prateek Vishnoi Red-Black Trees
Lemma
Proof.
Subtree rooted at any node x contains atleast 2bh(x) − 1
internal nodes.
Let h be the height of tree.
Acc. to property 4, atleast half the nodes on any simple path
from root to leaf , excluding the root must be BLACK.
Prof. Prateek Vishnoi Red-Black Trees
Lemma
Proof.
Subtree rooted at any node x contains atleast 2bh(x) − 1
internal nodes.
Let h be the height of tree.
Acc. to property 4, atleast half the nodes on any simple path
from root to leaf , excluding the root must be BLACK.
Thus, bh(root) ≥ h/2
Prof. Prateek Vishnoi Red-Black Trees
Lemma
Proof.
Subtree rooted at any node x contains atleast 2bh(x) − 1
internal nodes.
Let h be the height of tree.
Acc. to property 4, atleast half the nodes on any simple path
from root to leaf , excluding the root must be BLACK.
Thus, bh(root) ≥ h/2
From above claim, n ≥ 2h/2 − 1
Prof. Prateek Vishnoi Red-Black Trees
Lemma
Proof.
Subtree rooted at any node x contains atleast 2bh(x) − 1
internal nodes.
Let h be the height of tree.
Acc. to property 4, atleast half the nodes on any simple path
from root to leaf , excluding the root must be BLACK.
Thus, bh(root) ≥ h/2
From above claim, n ≥ 2h/2 − 1
Adding 1 on both sides and taking logarithms, we get,
h ≤ 2 log(n + 1)
Prof. Prateek Vishnoi Red-Black Trees
Rotations
Figure: Introduction to Algorithms, CLRS
Prof. Prateek Vishnoi Red-Black Trees
Form BST with left rotate on 11-18
Sequence of keys
7, 4,3,2,6,11,9, 18,19,22,20,14,12,17
Prof. Prateek Vishnoi Red-Black Trees
Left Rotations Example
Figure: Introduction to Algorithms, CLRS
Prof. Prateek Vishnoi Red-Black Trees