Red Black Trees
Submitted by: Submitted by saurabhkasliwal
Views: 10
Words: 901
Pages: 4
Category: Science and Technology
Date Submitted: 02/17/2016 04:44 PM
Red-Black Trees
CLRS page 308
Insertion into a Red-Black Tree
insert:
20
85
15
70
20
20
20
20
85
15
85
15
20
85
70
15
85
70
Double Red Problem
case 1 sibling of parent
is red
Insertion into a Red-Black Tree
insert:
17
20
20
15
85
70
15
60
20
85
17 70
15
20
85
15
17 70
70
17 60
60
Double Red Problem
case 3 sibling of parent
is BLACK (or nil)
Right Rotate
3
85
Insertion into a Red-Black Tree
insert:
30
20
20
15
15
70
17 60
85
20
70
17 60
70
15
85
30
17 60
85
30
Double Red Problem
case 1 sibling of parent
is RED
4
Insertion into a Red-Black Tree
50
insert:
20
20
70
15
17 60
30
20
85
17 60
70
15
70
15
85
30
50
Double Red Problem
case 2 sibling of parent
is BLACK (or nil)
Left Rotate
20
17 60
70
15
85
17 50
50
30 60
30
Double Red Problem
case 3 sibling of parent
is BLACK (or nil)
Right Rotate
5
85
Insertion into a Red-Black Tree
65
insert:
20
15
15
70
17 50
85
30 60
15
70
17 50
85
30 60
65
Double Red Problem
case 1 sibling of
parent is RED
50
20
20
20
70
17 50
15
85
30 60
65
Double Red Problem
case 2 sibling of
parent is BLACK
or NULL
17 30
70
20
50
70
60
15
85
30 60
85
65
17
65
Double Red Problem
case 3 sibling of
parent is BLACK
or NULL
6
63
50
insert:
50
20
15
17
20
70
30 60
85
65
15
17
50
20
70
30 60
85
65
63
Double Red Problem
case 2 sibling of
parent is BLACK
or NULL
15
17
50
70
30 60
20
85
15
63
63
30
63
17
65
Double Red Problem
case 3 sibling of
parent is BLACK
or NULL
7
70
63
60 65
85
Bottom-Up Insertion into RB tree
•
•
•
•
First insert as you would in standard binary search...
