1 of 30

Red Black Trees

Prof. Prateek Vishnoi

2 of 30

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 30

Deletion

  • Delete acc. To BST.
  • Case 1: If the node to be deleted is RED, DELETE it and EXIT.
  • Case 2 : If DB is ROOT, remove DB.
  • Case 3 : If DB’s sibling is BLACK and both its NEPHEW are BLACK
  • REMOVE DB.
  • Make sibling RED.
  • Add BLACK to PARENT.

​

  • Case 4 : If DB’s sibling is RED,
  • SWAP color’s of DB’s parent and DB’s sibling.
  • Rotate parent in DB’s direction.
  • Reapply a suitable case.

​

4 of 30

Deletion

  • Case 5: If DB’s sibling is BLACK, far nephew is BLACK & near nephew is RED :
          • SWAP colors of DB’s siblings & DB’s near NEPHEW.
          • ROTATE DB’s sibling in opposite direction of DB.
          • Apply Case 6.

​

  • Case 6 : If DB’s sibling is BLACK & far nephew is RED.
          • SWAP colors of DB’s parent & DB’s sibling.
          • ROTATE DB’s parent in DB’s direction.
          • Change color of RED nephew to BLACK.
          • REMOVE DB.

5 of 30

Delete 50

40

20

60

80

50

70

10

30

90

99

40

20

60

80

70

10

30

90

99

N

Acc. To BST

6 of 30

Delete 50

40

20

60

80

70

10

30

90

99

N

Case 4

SWAP color

40

20

60

80

70

10

30

90

99

N

7 of 30

40

20

60

80

70

10

30

90

99

N

40

20

80

70

10

30

90

99

N

60

Rotate the parent in DB’s direction

8 of 30

40

20

80

70

10

30

90

99

N

60

40

20

80

70

10

30

90

99

60

Case 3

9 of 30

Delete 20

40

20

80

70

10

30

90

99

60

BST Deletion

40

30

80

70

10

30

90

99

60

10 of 30

Delete 20

Delete leaf 30

40

30

80

70

10

30

90

99

60

40

30

80

70

10

90

99

60

N

11 of 30

Delete 20

40

30

80

70

10

90

99

60

N

40

80

70

10

90

99

60

30

Case 3

12 of 30

Delete 20

80

70

10

90

99

60

Case 3

40

80

70

10

90

60

30

30

40

99

13 of 30

Delete 20

80

70

10

90

99

60

30

80

70

10

90

99

60

30

40

Case 2

40

14 of 30

Delete 99

80

70

10

90

60

30

Case 1

40

80

70

10

90

99

60

30

40

15 of 30

Delete 90

80

70

10

60

30

BST deletion

40

80

70

10

90

60

30

40

N

16 of 30

Delete 90

80

70

10

60

30

40

N

Case 5

80

70

10

60

30

40

N

17 of 30

Delete 90

Case 5

80

70

10

60

30

40

N

80

60

10

70

30

40

N

18 of 30

Delete 90

Case 6

80

60

10

70

30

40

N

80

60

10

70

30

40

N

19 of 30

Delete 90

Case 6

80

60

10

70

30

40

N

70

60

10

80

30

40

N

20 of 30

Delete 90

Case 6

70

60

10

80

30

40

N

70

60

10

80

30

40

21 of 30

Delete 40

BST Deletion

70

60

10

80

30

40

70

60

10

80

30

60

22 of 30

Delete 60

Case 3

70

10

80

30

60

N

70

10

80

30

60

23 of 30

Delete 60

Case 3

70

10

80

30

60

70

10

80

30

60

24 of 30

Delete 60

BST Deletion

70

10

80

30

60

70

10

80

30

70

25 of 30

Delete 70(internal node)

BST Deletion

70

10

80

30

70

80

10

80

30

70

26 of 30

Delete 80(leaf node)

Case 1

80

10

80

30

70

80

10

30

70

27 of 30

Delete 70

BST Deletion

80

10

30

70

80

10

30

80

28 of 30

Delete 80(leaf node)

BST Deletion

80

10

30

70

10

30

80

N

29 of 30

Delete 80(leaf node)

Case 6

10

30

80

N

10

30

80

N

30 of 30

Delete 80(leaf node)

Case 6

10

30

80

N

10

30

80