1 of 27

Red Black Trees

Prof. Prateek Vishnoi

2 of 27

Properties

A red-black tree is a binary search tree that satisfies the following :
Every node is either red or black.
The root is black.
Every leaf (NIL) is black.
If a node is red, then both its children are black.
For each node, all simple paths from the node to descendant leaves contain the same number of black nodes.

3 of 27

Insertion in RB Tree

Insert the node similarly as of BST.
If the node is ROOT node, make its color BLACK.
If the tree is not EMPTY, create newnode as leaf node with color RED.
If parent of newnode is BLACK, then EXIT.
If parent of newnode is RED, check color of UNCLE :
If color is BLACK or NULL, do suitable ROTATION and RECOLOR.
If color is RED, then RECOLOR, check if parent’s parent is ROOT or not, if not then RECOLOR and RECHECK

4 of 27

Create a RB Tree with the following keys:�

10, 18, 7, 15, 16, 30, 25, 40, 60, 2, 1, 70

10

18

7

15

5 of 27

10, 18, 7, 15, 16, 30, 25, 40, 60, 2, 1, 70�

10

18

7

15

R-R conflict

6 of 27

10, 18, 7, 15, 16, 30, 25, 40, 60, 2, 1, 70�

10

18

7

15

7 of 27

10, 18, 7, 15, 16, 30, 25, 40, 60, 2, 1, 70�

10

18

7

15

16

R-R conflict

8 of 27

10, 18, 7, 15, 16, 30, 25, 40, 60, 2, 1, 70�

10

18

7

15

16

R-R conflict

10

18

7

Left Rotation

15

16

9 of 27

10, 18, 7, 15, 16, 30, 25, 40, 60, 2, 1, 70�

10

18

7

Right Rotation

15

16

10

16

7

15

18

10 of 27

10, 18, 7, 15, 16, 30, 25, 40, 60, 2, 1, 70�

10

16

7

15

18

10

16

7

15

18

Recoloring

11 of 27

10, 18, 7, 15, 16, 30, 25, 40, 60, 2, 1, 70�

10

16

7

15

18

30

R-R conflict

10

16

7

15

18

30

Recoloring

12 of 27

10, 18, 7, 15, 16, 30, 25, 40, 60, 2, 1, 70�

10

16

7

15

18

30

Recoloring

10

16

7

15

18

30

13 of 27

10, 18, 7, 15, 16, 30, 25, 40, 60, 2, 1, 70�

10

7

16

15

18

30

25

R-R conflict

Right Rotation

10

7

16

15

18

25

30

14 of 27

10, 18, 7, 15, 16, 30, 25, 40, 60, 2, 1, 70�

10

7

16

15

18

25

30

Left Rotation

10

7

16

15

25

30

18

15 of 27

10, 18, 7, 15, 16, 30, 25, 40, 60, 2, 1, 70�

10

7

16

15

25

30

18

Recoloring

10

7

16

15

25

30

18

16 of 27

10, 18, 7, 15, 16, 30, 25, 40, 60, 2, 1, 70�

10

7

16

15

25

30

18

40

R-R conflict

10

7

16

15

25

30

18

40

Recoloring

17 of 27

10, 18, 7, 15, 16, 30, 25, 40, 60, 2, 1, 70�

10

7

16

15

25

30

18

40

Recoloring

10

7

16

15

25

30

18

40

R-R conflict

18 of 27

10, 18, 7, 15, 16, 30, 25, 40, 60, 2, 1, 70�

10

7

16

15

25

30

18

40

Left Rotation

16

10

25

30

18

40

7

15

19 of 27

10, 18, 7, 15, 16, 30, 25, 40, 60, 2, 1, 70�

Recoloring

16

10

25

30

18

40

7

15

16

10

25

30

18

40

7

15

20 of 27

10, 18, 7, 15, 16, 30, 25, 40, 60, 2, 1, 70�

16

10

25

30

18

40

7

15

60

Left Rotation

16

10

25

40

18

30

7

15

60

21 of 27

10, 18, 7, 15, 16, 30, 25, 40, 60, 2, 1, 70�

INSERT 1

16

10

25

40

18

30

7

15

60

2

16

10

25

40

18

30

7

15

60

2

1

22 of 27

10, 18, 7, 15, 16, 30, 25, 40, 60, 2, 1, 70�

16

10

25

40

18

30

7

15

60

2

1

R-R conflict

Right Rotation

16

10

25

40

18

30

2

15

60

7

1

23 of 27

10, 18, 7, 15, 16, 30, 25, 40, 60, 2, 1, 70�

16

10

25

40

18

30

2

15

60

7

1

Recoloring

16

10

25

40

18

30

2

15

60

7

1

24 of 27

10, 18, 7, 15, 16, 30, 25, 40, 60, 2, 1, 70�

INSERT 70

16

10

25

40

18

30

2

15

60

7

1

16

10

25

40

18

30

2

15

60

7

1

70

R-R conflict

25 of 27

10, 18, 7, 15, 16, 30, 25, 40, 60, 2, 1, 70�

Recolor

16

10

25

40

18

30

2

15

60

7

1

70

R-R conflict

16

10

25

40

18

30

2

15

60

7

1

70

26 of 27

10, 18, 7, 15, 16, 30, 25, 40, 60, 2, 1, 70�

16

10

25

40

18

30

2

15

60

7

1

70

16

10

25

40

18

30

2

15

60

7

1

70

Recolor

R-R conflict

27 of 27

10, 18, 7, 15, 16, 30, 25, 40, 60, 2, 1, 70�

16

10

25

40

18

30

2

15

60

7

1

70

Recolor

16

10

25

40

18

30

2

15

60

7

1

70