12-May-23
Red Black Trees
“A red-black tree is a kind of self-balancing binary search tree
where each node has an extra bit, and that bit is interpreted as
the colour (red or black). These colours are used to ensure that
the tree remains balanced during insertions and deletions.”
Although the balance of the tree is not perfect, it is good
enough to reduce the searching time and maintain it around
O(log n) time, where n is the total number of elements in the
tree. This tree was invented in 1972 by Rudolf Bayer.
21
21
Red Black Trees
22
22
1
12-May-23
Rules for Red Black Trees
1. Every node has a colour either red or black.
2. The root and leaves (NULL) of a tree are
always black.
3. There are no two adjacent red nodes (A red
node cannot have a red parent or red
child).
4. Every path from a node (including root) to
any of its descendant NULL node has the
same number of black nodes.
23
23
Red Black Trees vs AVL Trees
The AVL trees are more balanced compared to Red-Black Trees,
but they may cause more rotations during insertion and
deletion. So if your application involves frequent insertions and
deletions, then Red-Black trees should be preferred. And if the
insertions and deletions are less frequent and search is a more
frequent operation, then AVL tree should be preferred over
Red-Black Tree.
24
24
2
12-May-23
Operations on Red Black Trees
There are three basic operations on Red Black Trees:
1. Search
2. Insert
Change the tree structure
3. Remove
25
25
Rotations in Red Black Trees
We will apply the following two basic rotations to different
nodes of a BST (invalid RB) to make it a valid Red Black Tree
1. Left Rotation
2. Right Rotation
26
26
3
12-May-23
Understanding Relationships in Red Black Trees
• Same as standard binary
search trees.
• We will use these
relationships to determine
cases for rotation.
27
27
Insertion in Red Black Trees
1. Insert ‘Z’ and color it red
2. Recolour and rotate to fix
the violations
28
28
4
12-May-23
Insertion in Red Black Trees
After insertion of Z, 4 possible
scenarios:
1. Z = root
2. Z.Parent = Black
3. Z.uncle = Red
4. Z.uncle = Black (Triangle)
5. Z.uncle = Black (Line)
29
29
Insertion in Red Black Trees
Scenario 1: Z = Root
Solution:
Color Z Black
30
30
5
12-May-23
Insertion in Red Black Trees
Scenario 2: Z.Parent = Black
Solution:
No rule is violated
31
31
Insertion in Red Black Trees
Scenario 3: Z.uncle = Red
Solution:
Recolour Z’s
• Parent
• Grandparent
• Uncle
32
32
6
12-May-23
Insertion in Red Black Trees
Scenario 4: Z.uncle = Black (Triangle)
Solution:
Rotate Z’s
• Parent
• In opposite direction to Z
33
33
Insertion in Red Black Trees
Scenario 5: Z.uncle = Black (Line)
Solution:
Rotate Z’s
• Grandparent
• In opposite direction to Z
• Recolour Parent and
Grandparent
34
34
7
12-May-23
References:
1. https://www.guru99.com/avl-tree.html
2. https://en.wikipedia.org/wiki/AVL_tree
3. https://en.wikipedia.org/wiki/Red-black_tree
4. https://www.geeksforgeeks.org/avl-tree-set-1-insertion/?ref=lbp
5. https://www.youtube.com/watch?v=qvZGUFHWChY
6. https://www.geeksforgeeks.org/red-black-tree-set-1-introduction-2/
35
35
