Design and Analysis of Algorithms
Unit 2: Graph and Tree Algorithms
Problems on Red Black Trees
Example 1:
• Create a red black tree by inserting following sequence of number :- 8, 18, 5, 15,
17, 25, 40, and 80.
• Insert (8)
→ Tree is empty. So insert newnode as root node with black color.
• Insert (18)
→ Tree is not empty. So insert newnode with red color
3 Problems on Red Black Trees
Example 1: (cont..)
Insert : 8, 18, 5, 15, 17, 25, 40, and 80.
• Insert (5)
→ Tree is empty. So insert newnode with red color
• Insert (15)
→ Tree is not empty. So insert newnode with red color
Here there are two consecutive red
nodes 18 and 15. The newnode’s
parent sibling color is red and
parent’s parent is root node. So we
use recolor to make it red black tree.
After recolor
4 Problems on Red Black Trees
Example 1: (cont..)
Insert : 8, 18, 5, 15, 17, 25, 40, and 80.
• Insert (17) : Tree is empty. So insert newnode with red color.
Here there two consecutive red
nodes 15 and [Link] newnode’s
parent sibling is null. So we need
rotation. Here we need LR rotation
and recolor.
After Left
Rotation
After Right Rotation
and Recolor
5 Problems on Red Black Trees
Example 1: (cont..)
Insert : 8, 18, 5, 15, 17, 25, 40, and 80.
• Insert (25) : Tree is empty. So insert newnode with red color.
There are two consecutive red
nodes 18 and 25. The newnode’s
parent sibling color is red and
parent’s parent is not root node. So
we use recolor and recheck.
After Recolor
After recolor operation, the tree is
satisfying all red black tree
properties.
6 Problems on Red Black Trees
Example 1: (cont..)
Insert : 8, 18, 5, 15, 17, 25, 40, and 80.
• Insert (40) : Tree is empty. So insert newnode with red color.
Here there are two consecutive red
nodes 25 and 40. The newnode’s
parent sibling is null. So we need
rotation and recolor. Here we use LL
rotation and recheck.
After LL Rotation
and Recolor
After LL rotation and recolor
operation, the tree satisfying all red
black tree properties.
7 Problems on Red Black Trees
Example 1: (cont..)
Insert : 8, 18, 5, 15, 17, 25, 40, and 80.
• Insert (80) : Tree is empty. So insert newnode with red color.
There are two consecutive red
nodes 40 and 80. The newnodes
parent sibling color is red and
parent’s parent is not root node. So
we use recolor and recheck.
After Recolor
After recolor again there are two
consecutive red nodes 17 and 25.
The newnode’s parent sibling color
is black. So we need rotation. We
use left rotation And recolor. (Case 2
– Uncle is Red is applied)
8 Problems on Red Black Trees
Example 1: (cont..)
Insert : 8, 18, 5, 15, 17, 25, 40, and 80.
After Left Rotation and
Recolor
Finally above tree is satisfying all the properties of red black tree
and it is a perfect red black tree.
9 Problems on Red Black Trees
Example 2:
• Show the red-black trees after successively inserting the keys 41, 38, 31,
12, 19, 8 into and initially empty red-black tree.
• [Link]
10 Problems on Red Black Trees
Example 2: Solution
11
Problems on Red Black Trees
Example 2: Solution (contd..)
12 Problems on Red Black Trees
Example 2: Solution (contd..)
13
Problems on Red Black Trees
Example 3:
Show the red-black trees after successively inserting the keys 10, 20, 30, 15, 25,
12, 5, 3, 8, 27, 40, 50, 45
14 Problems on Red Black Trees
Thank
You
