Design and Analysis of Algorithm

Advanced Data Structure

(Red Black Tree)
(Properties, Rotation and Insertion)
Red Black Tree
• A red-black tree is a binary search tree + 1 bit per node: an
attribute color, which is either red or black.
• All leaves are empty (nil) and colored black.
• A single sentinel, nil[T ], is used for all the leaves of red-
black tree T .
• Color of [nil[T ]] is black.
• The root′s parent is also nil[T ].
• All other attributes of binary search trees are inherited by red-
black trees (i.e. key, left, right, and p as parent).
• We don′t care about the key in nil[T ].
Red Black Tree Properties

1. Every node is either red or black.

2. The root is always black.
3. Every leaf (nil[T]) is black.
4. If a node is red, then both its children are black.
(Hence no two reds in a row on a simple path from
the root to a leaf is allowed .)
5. For each node, all paths from the node to descendant
leaves(NIL) contain the same number of black nodes.
Red Black Tree
Height of a red-black tree
h=4

• Height of a node is the

bh=2
26

number of edges in a
h=3

longest path to a leaf.

h=1 bh=2
bh=1

• Black-height of a node x:
17 41

bh(x) is the number of

h=2
h=2 bh=1

black nodes (including

bh=1 47
30

nil[T ]) on the path from x

h=1
h=1

to leaf, not counting x. By

bh=1
bh=1

property 5, black-height is
38 50

well defined. NIL

Red Black Tree-Rotations
• Needed to maintain red-black trees as balanced
binary search trees.
• Changes the local pointer structure. (Only pointers
are changed.)
• Won′t upset the binary-search-tree property.
Algorithm Left Rotation
Red Black Tree
Rotations (Example)
Demonstrate of left rotation that maintains in-
order ordering of keys.
Red Black Tree
Rotations (Example)
Demonstrate of left rotation that maintains in-
order ordering of keys.
Red Black Tree
Rotations (Example)
Demonstrate of left rotation that maintains in-
order ordering of keys.
Red Black Tree
Rotations (Example)
Demonstrate of left rotation that maintains in-
order ordering of keys.
• Before rotation: keys of left subtree ≤
11 ≤ keys of left subtree ≤ 18 ≤ keys of
right subtree.
• Rotation makes left subtree into right
subtree.
• After rotation: keys of left subtree ≤ 11
≤ keys of right subtree ≤ 18 ≤ keys of
right subtree.
• Time complexity : O(1) for both
LEFT-ROTATE and RIGHT-ROTATE,
since a constant number of pointers
are modified.
Red Black Tree
Insertion:

Start by doing regular binary-search-tree

insertion:
Red Black Tree- Insertion
Algorithms
 Red Black Tree
Insertion:
• RB-INSERT ends by coloring the new node z
red.
• Then it calls RB-INSERT-FIXUP to maintain
the properties of a red-black Tree.
Which
1. Every property
node might
is either red be violated?
or black. OK
2. The root is always black. If z is the root, then there′s a violation.
Otherwise, OK.
3. Every leaf (nil[T]) is black. OK
4. If a node is red, then both its If p[z] is red, there′s a violation: both z
children are black. and p[z] are red.

5. For each node, all paths from the OK

node to descendant leaves contain
the same number of black nodes.
Insert Fixup Cases
Case 1- ‘z’ is uncle ‘y’ is red
-color parent and uncle to balck
-color grandparent to red
- set move ‘z’ to grandparent
Case 2- ‘z’ uncle ‘y’ is black and ‘z’ is right child
-move ‘z’ to z’parent
-left rotate ‘z’
Case 3- ‘z’ uncle ‘y’ is black and ‘z’ is left child
- color parent black
- color grandparent red
- right rotate grandparent of ‘z’
Red Black Tree- RB Insert Fixup
Red Black Tree
Insertion (Example):
Insert the following elements into an empty RB-Tree.
[ 11, 2, 14, 1, 7, 15, 5, 8, 4]
Insert -11

11
z
Red Black Tree
Insertion (Example 1):
Insert the following elements into an empty RB-Tree.
[ 11, 2, 14, 1, 7, 15, 5, 8, 4]
Insert -11

11 Apply Fix up 11
z
Red Black Tree
Insertion (Example 1):
Insert the following elements into an empty RB-Tree.
[ 11, 2, 14, 1, 7, 15, 5, 8, 4]
Insert -2

11

No Fixup required
2
z
Red Black Tree
Insertion (Example 1):
Insert the following elements into an empty RB-Tree.
[ 11, 2, 14, 1, 7, 15, 5, 8, 4]
Insert -14

11

No Fixup required
2 14
z
Red Black Tree
Insertion (Example 1):
Insert the following elements into an empty RB-Tree.
[ 11, 2, 14, 1, 7, 15, 5, 8, 4]
Insert -1

11

2 14
z

1
Red Black Tree
Insertion (Example 1):
Insert the following elements into an empty RB-Tree.
[ 11, 2, 14, 1, 7, 15, 5, 8, 4]
Insert -1

11

2 14
z

1
Red Black Tree
Insertion (Example 1):
Insert the following elements into an empty RB-Tree.
[ 11, 2, 14, 1, 7, 15, 5, 8, 4]
Insert -1
11
11
Case 1
Fixup Apply 2 14
2 14 z
z
y
1
1
Red Black Tree
Insertion (Example 1):
Insert the following elements into an empty RB-Tree.
[ 11, 2, 14, 1, 7, 15, 5, 8, 4]
Insert -1 z z

11
11 11

Case 1
Fixup Apply 2 14 Apply Fix up
14 2 14
2
z
y
y
1
1 1
Red Black Tree
Insertion (Example 1):
Insert the following elements into an empty RB-Tree.
[ 11, 2, 14, 1, 7, 15, 5, 8, 4]
Insert -7
11

14 No Fixup required
2

1 7
z
Red Black Tree
Insertion (Example 1):
Insert the following elements into an empty RB-Tree.
[ 11, 2, 14, 1, 7, 15, 5, 8, 4]
Insert -15
11

No Fixup required
2 14

1 7 15
z
Insertion (Example 1):
Red Black Tree
Insert the following elements into an empty RB-Tree.
[ 11, 2, 14, 1, 7, 15, 5, 8, 4]
Insert -5

11

2 14

1 7 15

5
z
Red Black Tree
Insertion (Example 1):
Insert the following elements into an empty RB-Tree.
[ 11, 2, 14, 1, 7, 15, 5, 8, 4]
Insert -5
11
11

Case 1 z
2 14
2 14 Fixup Apply

1 7 15
1 7 15

5
5
z
Red Black Tree
Insertion (Example 1):
Insert the following elements into an empty RB-Tree.
[ 11, 2, 14, 1, 7, 15, 5, 8, 4]
Insert -8
11

No Fixup required
2 14
15

1 7
8

z
Red Black Tree
Insertion (Example 1):
Insert the following elements into an empty RB-Tree.
[ 11, 2, 14, 1, 7, 15, 5, 8, 4]
Insert -4
Red Black Tree
Insertion (Example 1):
Insert the following elements into an empty RB-Tree.
[ 11, 2, 14, 1, 7, 15, 5, 8, 4]
Insert -4
Red Black Tree
Insertion (Example 1):
Insert the following elements into an empty RB-Tree.
[ 11, 2, 14, 1, 7, 15, 5, 8, 4]
Insert -4
Insertion (Example 1):
Red Black Tree
Insert the following elements into an empty RB-Tree.
[ 11, 2, 14, 1, 7, 15, 5, 8, 4]
Insert -4
Insertion (Example):
Red Black Tree
Insert the following elements into an empty RB-Tree.
[ 11, 2, 14, 1, 7, 15, 5, 8, 4]
Insert -4
Red Black
Insertion (Example 1):
Tree
Insert the following elements into an empty RB-Tree.
[ 11, 2, 14, 1, 7, 15, 5, 8, 4]
Insert -4
Insertion (Example
Red Black 1): Tree
Insert the following elements into an empty RB-Tree.
[ 11, 2, 14, 1, 7, 15, 5, 8, 4]
Insert -4
Insertion (Example
Red Black 1): Tree
Insert the following elements into an empty RB-Tree.
[ 11, 2, 14, 1, 7, 15, 5, 8, 4]
Insert -4
Red Black Tree
Insertion (Example 1):
Insert the following elements into an empty RB-Tree.
[ 11, 2, 14, 1, 7, 15, 5, 8, 4]
Insert -4
Red Black Tree
Insertion (Example 1):
Insert the following elements into an empty RB-Tree.
[ 11, 2, 14, 1, 7, 15, 5, 8, 4]
Insert -4
Red Black Tree
Insertion (Example 2):
Insert the following elements into an empty RB-Tree.
[ 50, 40, 30, 45, 20, 5]
Insert -50

50 Aply Fix up
z
Red Black Tree
Insertion (Example 2):
Insert the following elements into an empty RB-Tree.
[ 50, 40, 30, 45, 20, 5]
Insert -50

50 Apply Fix up 50
z
Red Black Tree
Insertion (Example 2):
Insert the following elements into an empty RB-Tree.
[ 50, 40, 30, 45, 20, 5]
Insert -50

50 Apply Fix up 50
z
Red Black
Insertion (Example 2):
Tree No Fixup required

Insert the following elements into an empty RB-Tree.

[ 50, 40, 30, 45, 20, 5]
Insert -40

50

No Fixup required
40
z
Red Black
Insertion (Example 2):
Tree No Fixup required

Insert the following elements into an empty RB-Tree.

[ 50, 40, 30, 45, 20, 5]
Insert -30

50

40 NIL

30
z
Red Black
Insertion (Example 2):
Tree
Insert the following elements into an empty RB-Tree.
[ 50, 40, 30, 45, 20, 5]
RR

Insert -30 50
50
Case 3
Fixup Apply 40 NIL
40 NIL y
y

30
30

Fix
u
Aft
p Ap
e
40

ply
rR
R
z
30 50
Red Black
Insertion (Example 2):
Tree
Insert the following elements into an empty RB-Tree.
[ 50, 40, 30, 45, 20, 5]
Insert -45

40

30 50
y

z 45
Red Black
Insertion (Example 2):
Tree
Insert the following elements into an empty RB-Tree.
[ 50, 40, 30, 45, 20, 5]
Insert -45

40

30 50
y

z 45
Red Black
Insertion (Example 2):
Tree
Insert the following elements into an empty RB-Tree.
[ 50, 40, 30, 45, 20, 5]
Insert -45

40 40
Case 1
Fixup Apply

30 30 50
y 50 y

z 45 z 45
Red Black
Insertion (Example 2):
Tree
Insert the following elements into an empty RB-Tree.
[ 50, 40, 30, 45, 20, 5]
Insert -45

40 40 40
Case 1
Fixup Apply Apply Fix up

30 30 30 50
y 50 y 50 y

z z 45 z 45
45
Red Black
Insertion (Example 2):
Tree
Insert the following elements into an empty RB-Tree.
[ 50, 40, 30, 45, 20, 5]
Insert -20

40

30 50

z 20
45
Red Black
Insertion (Example 2):
Tree
Insert the following elements into an empty RB-Tree.
[ 50, 40, 30, 45, 20, 5]
Insert -20

40

30 50
No Fixup required

z 20
45
Red Black
Insertion (Example 2):
Tree
Insert the following elements into an empty RB-Tree.
[ 50, 40, 30, 45, 20, 5]
Insert -5

40

30 50

20
45

z
Red Black
Insertion (Example 2):
Tree
Insert the following elements into an empty RB-Tree.
[ 50, 40, 30, 45, 20, 5]
Insert -5

40

30 50

20 NIL 45

y
5

z
Red Black Tree
Insertion (Example 2):
Insert the following elements into an empty RB-Tree.
[ 50, 40, 30, 45, 20, 5]
Insert -5
40
40
RR
Case 3
Fixup Apply
30 50
30 50

F i
20

x
NIL 45

u
Afte
p
20 45

Appl
NIL

rR
y
R
y
5
y
5 40
z
z
20 50

5 30 45

z
Red Black Tree
Insertion (Example 2):
Insert the following elements into an empty RB-Tree.
[ 50, 40, 30, 45, 20, 5]
Insert -5
40
40
RR
Case 3
Fixup Apply
30 50
30 50

F i
20

x
NIL 45

u
Afte
p
20 45

Appl
NIL

rR
y
R
y
5
y
5 40
z
z
20 50

5 30 45

z
Red Black Tree
Insertion (Example 2):
Insert the following elements into an empty RB-Tree.
[ 50, 40, 30, 45, 20, 5]
Insert -5
40
40
RR
Case 3
Fixup Apply
30 50
30 50

F i
20

x
NIL 45

u
Afte
p
20 45

Appl
NIL

rR
y
R
y
5
y
5 40
z
z
20 50

5 30 45

z
Red Black Tree
Insertion (Example 2):
Insert the following elements into an empty RB-Tree.
[ 50, 40, 30, 45, 20, 5]
Insert -5
40
40
RR
Case 3
Fixup Apply
30 50
30 50

F i
20

x
NIL 45

u
Afte
p
20 45

Appl
NIL

rR
y
R
y
5
y
5 40
z
z
20 50

5 30 45

z
Red Black Tree
Insertion (Example 3):
Insert the following elements into an empty RB-Tree.
[ 41, 38, 31, 12, 19, 8]
Insert -50

41
z
Red Black Tree
Insertion (Example 3):
Insert the following elements into an empty RB-Tree.
[ 41, 38, 31, 12, 19, 8]
Insert -50

41 Aply Fix up 41
z z
Red Black Tree
Insertion (Example 3):
Insert the following elements into an empty RB-Tree.
[ 41, 38, 31, 12, 19, 8]
Insert -38

41

38
z
Red Black Tree
Insertion (Example 3):
Insert the following elements into an empty RB-Tree.
[ 41, 38, 31, 12, 19, 8]
Insert -38

41

No Fixup required

38
z
Red Black Tree
Insertion (Example 3):
Insert the following elements into an empty RB-Tree.
[ 41, 38, 31, 12, 19, 8]
Insert -31

41

38

31
z
Red Black Tree
Insertion (Example 3):
Insert the following elements into an empty RB-Tree.
[ 41, 38, 31, 12, 19, 8]
Insert -31

41

38 NIL

y
31
z
Red Black Tree
Insertion (Example 3):
Insert the following elements into an empty RB-Tree.
[ 41, 38, 31, 12, 19, 8]
Insert -31

41

Case 3
Fixup Apply
38 NIL

y
31
z
Red Black Tree
Insertion (Example 3):
Insert the following elements into an empty RB-Tree.
[ 41, 38, 31, 12, 19, 8]
Insert -31 RR

41
41

Case 3
Fixup Apply
38 NIL
38 NIL

y
y 31
31
z
z
Red Black Tree
Insertion (Example 3):
Insert the following elements into an empty RB-Tree.
[ 41, 38, 31, 12, 19, 8]
Insert -31 RR

41
41
After RR
Case 3 Fixup Apply
Fixup Apply
38 NIL
38 NIL

y
y 31
31
z
z
Red Black Tree
Insertion (Example 3):
Insert the following elements into an empty RB-Tree.
[ 41, 38, 31, 12, 19, 8]
Insert -31 RR

38
41
41
After RR
Case 3 Fixup Apply
Fixup Apply 31 41
38 NIL
38 NIL
z

y
y 31
31
z
z
Red Black Tree
Insertion (Example 3):
Insert the following elements into an empty RB-Tree.
[ 41, 38, 31, 12, 19, 8]
Insert -12

38

31 41

12
z
Red Black Tree
Insertion (Example 3):
Insert the following elements into an empty RB-Tree.
[ 41, 38, 31, 12, 19, 8]
Insert -12

38

31 41

y
12
z
Red Black Tree
Insertion (Example 3):
Insert the following elements into an empty RB-Tree.
[ 41, 38, 31, 12, 19, 8]
Insert -12

38
Case 1
Fixup Apply

31 41

y
12
z
Red Black Tree
Insertion (Example 3):
Insert the following elements into an empty RB-Tree.
[ 41, 38, 31, 12, 19, 8]
Insert -12
z 38
38
Case 1
Fixup Apply

31 31 41
41

y y
12 12

z
Red Black Tree
Insertion (Example 3):
Insert the following elements into an empty RB-Tree.
[ 41, 38, 31, 12, 19, 8]
Insert -19

38

31 41

12

19
z
Red Black Tree
Insertion (Example 3):
Insert the following elements into an empty RB-Tree.
[ 41, 38, 31, 12, 19, 8]
Insert -19

38

31 41

NIL
12

y
19
z
Red Black Tree
Insertion (Example 3):
Insert the following elements into an empty RB-Tree.
[ 41, 38, 31, 12, 19, 8]
Insert -19

38
38

Case 2
Fixup Apply
31 41 31 41

LL
NIL
12 NIL
12
z
y
y
19
z 19
Red Black Tree
Insertion (Example 3):
Insert the following elements into an empty RB-Tree.
[ 41, 38, 31, 12, 19, 8]
Insert -19
38
38
38
After LL
Case 2 Fixup Apply
Fixup Apply 31 41
31 41 31 41

LL z NIL
NIL 19
12 NIL
12
z
y
y
y 12
19
z 19
Red Black Tree
Insertion (Example 3):
Insert the following elements into an empty RB-Tree.
[ 41, 38, 31, 12, 19, 8]
Insert -19 38 38

RR
After LL Case 3
Fixup Apply 31 41 Fixup Apply 31 41

NIL NIL
19 19
z
y z
y
12 12
Red Black Tree
Insertion (Example 3):
Insert the following elements into an empty RB-Tree.
[ 41, 38, 31, 12, 19, 8]
Insert -19 38 38

RR
After LL Case 3

Afte Apply
Fix
Fixup Apply 31 41 Fixup Apply

up
31 41

r RR
NIL NIL
19 19
z
y z
y
12 12
Red Black Tree
Insertion (Example 3):
Insert the following elements into an empty RB-Tree.
[ 41, 38, 31, 12, 19, 8]
Insert -19 38 38

RR
After LL Case 3

Afte Apply
Fix
Fixup Apply 31 41 Fixup Apply

up
31 41

r RR
NIL NIL
19 19
z 38
y z
y
12 12
19 41

z
12 31
Red Black Tree
Insertion (Example 3):
Insert the following elements into an empty RB-Tree.
[ 41, 38, 31, 12, 19, 8]
Insert -8
38

19 41

12 31

8
Red Black Tree
Insertion (Example 3):
Insert the following elements into an empty RB-Tree.
[ 41, 38, 31, 12, 19, 8]
Insert -8
38

19 41

12 31

z y
8
Red Black Tree
Insertion (Example 3):
Insert the following elements into an empty RB-Tree.
[ 41, 38, 31, 12, 19, 8]
Insert -8
38

19 41 Case 1
Fixup Apply

12 31

z
y
8
Red Black Tree
Insertion (Example 3):
Insert the following elements into an empty RB-Tree.
[ 41, 38, 31, 12, 19, 8]
Insert -8
38
38

19 41 Case 1 19 41
Fixup Apply

12 31
12 31
z
y z
y
8
8
Red Black Tree
Insertion (Example 4):
Insert the following elements into an empty RB-Tree.
[ 5, 10 ,15 , 25, 20 ,30]
Insert -5

5
z
Red Black Tree
Insertion (Example 4):
Insert the following elements into an empty RB-Tree.
[ 5, 10 ,15 , 25, 20 ,30]
Insert -5

5 Aply Fix up 5
z z
Red Black Tree
Insertion (Example 4):
Insert the following elements into an empty RB-Tree.
[ 5, 10 ,15 , 25, 20 ,30]
Insert -10

10

z
Red Black Tree
Insertion (Example 4):
Insert the following elements into an empty RB-Tree.
[ 5, 10 ,15 , 25, 20 ,30]
Insert -10

No Fixup required

10

z
Red Black Tree
Insertion (Example 4):
Insert the following elements into an empty RB-Tree.
[ 5, 10 ,15 , 25, 20 ,30]
Insert -15

10

15

z
Red Black Tree
Insertion (Example 4):
Insert the following elements into an empty RB-Tree.
[ 5, 10 ,15 , 25, 20 ,30]
Insert -15

NIL
10

15

z
Red Black Tree
Insertion (Example 4):
Insert the following elements into an empty RB-Tree.
[ 5, 10 ,15 , 25, 20 ,30]
Insert -15

5
Case 3
Fixup Apply

NIL
10

15

z
Red Black Tree
Insertion (Example 4):
Insert the following elements into an empty RB-Tree.
[ 5, 10 ,15 , 25, 20 ,30]
Insert -15

5 10
Case 3
Fixup Apply

NIL
10 5 15

y
z
15

z
Red Black Tree
Insertion (Example 4):
Insert the following elements into an empty RB-Tree.
[ 5, 10 ,15 , 25, 20 ,30]
Insert -25

10

5 15

25

z
Red Black Tree
Insertion (Example 4):
Insert the following elements into an empty RB-Tree.
[ 5, 10 ,15 , 25, 20 ,30]
Insert -25

10

5 15

25

z
Red Black Tree
Insertion (Example 4):
Insert the following elements into an empty RB-Tree.
[ 5, 10 ,15 , 25, 20 ,30]
Insert -25

10

Case 1
5 Fixup Apply
15

25

z
Red Black Tree
Insertion (Example 4):
Insert the following elements into an empty RB-Tree.
[ 5, 10 ,15 , 25, 20 ,30]
Insert -25

10
10
Case 1
z
Fixup Apply
5 15
5 15
y
y
25
25

z
Red Black Tree
Insertion (Example 4):
Insert the following elements into an empty RB-Tree.
[ 5, 10 ,15 , 25, 20 ,30]
Insert -25

10
10 10
Case 1 z
z Aply Fix up
Fixup Apply
5 15
5 5 15
15
y
y y
25
25 25

z
Red Black Tree
Insertion (Example 4):
Insert the following elements into an empty RB-Tree.
[ 5, 10 ,15 , 25, 20 ,30]
Insert -20

10

5 15

25

20

z
Red Black Tree
Insertion (Example 4):
Insert the following elements into an empty RB-Tree.
[ 5, 10 ,15 , 25, 20 ,30]
Insert -20

10

5 15

NIL
25

y
20

z
Red Black Tree
Insertion (Example 4):
Insert the following elements into an empty RB-Tree.
[ 5, 10 ,15 , 25, 20 ,30]
Insert -20

10
Case 2
Fixup Apply
5 15

NIL
25

y
20

z
Red Black Tree
Insertion (Example 4):
Insert the following elements into an empty RB-Tree.
[ 5, 10 ,15 , 25, 20 ,30]
Insert -20
10
10

Case 2
Fixup Apply 5 15
5 15
RR
NIL
25
NIL
25
y
z
y
20
20

z
Red Black Tree
Insertion (Example 4):
Insert the following elements into an empty RB-Tree.
[ 5, 10 ,15 , 25, 20 ,30]
Insert -20
10
After RR 10
10
Fixup Apply
Case 2
Fixup Apply 5 15 5 15
5 15
RR
NIL
25 NIL
NIL 20
25
y
z y
y
20 25
20
z
z
Red Black Tree
Insertion (Example 4):
Insert the following elements into an empty RB-Tree.
[ 5, 10 ,15 , 25, 20 ,30]
Insert -20

After RR 10
Fixup Apply

5 15

NIL
20

y
25

z
Red Black Tree
Insertion (Example 4):
Insert the following elements into an empty RB-Tree.
[ 5, 10 ,15 , 25, 20 ,30]
Insert -20

After RR 10
Fixup Apply

5 15

NIL
20

y
25

z
Red Black Tree
Insertion (Example 4):
Insert the following elements into an empty RB-Tree.
[ 5, 10 ,15 , 25, 20 ,30]
Insert -20

After RR 10
Case 3
Fixup Apply
Fixup Apply

5 15

NIL
20

y
25

z
Red Black Tree
Insertion (Example 4):
Insert the following elements into an empty RB-Tree.
[ 5, 10 ,15 , 25, 20 ,30]
Insert -20
10
After RR Case 3
Fixup Apply 10 Fixup Apply LL

5 15
5 15

NIL
20
NIL
20
y
25
y
25
z

z
Red Black Tree
Insertion (Example 4):
Insert the following elements into an empty RB-Tree.
[ 5, 10 ,15 , 25, 20 ,30]
Insert -20
10 After LL 10
After RR Case 3
Fixup Apply
Fixup Apply 10 Fixup Apply LL

5 5 20
15
5 15

NIL 15 25
20
NIL
20
y y z
25
y
25
z

z
Red Black Tree
Insertion (Example 4):
Insert the following elements into an empty RB-Tree.
[ 5, 10 ,15 , 25, 20 ,30]
Insert -30

10

5 20

15 25

y
30

z
Red Black Tree
Insertion (Example 4):
Insert the following elements into an empty RB-Tree.
[ 5, 10 ,15 , 25, 20 ,30]
Insert -30

10

5 20

15 25

y
30

z
Red Black Tree
Insertion (Example 4):
Insert the following elements into an empty RB-Tree.
[ 5, 10 ,15 , 25, 20 ,30]
Insert -30

10
Case 1
Fixup Apply
5 20

15 25

y
30

z
Red Black Tree
Insertion (Example 4):
Insert the following elements into an empty RB-Tree.
[ 5, 10 ,15 , 25, 20 ,30]
Insert -30

10 10
Case 1
Fixup Apply
5 5 20
20

z
15 15 25
25

y y
30 30

z
RB Tree Deletion
1. Transplant step
2. RB-delete
3. RB-delete fixup
RB Tree Deletion
RB-Delete Part 1
RB-Delete Part 2