This PDF 1.4 document has been generated by dvips(k) 5.96.1 Copyright 2007 Radical Eye Software / GPL Ghostscript 8.70, and has been sent on pdf-archive.com on 28/03/2017 at 11:21, from IP address 208.54.x.x.
The current document download page has been viewed 489 times.
File size: 144.06 KB (27 pages).
Privacy: public file
CSE 2331
Red-Black Trees
8.1
CSE 2331
Red-Black Trees
Definition. A red-black tree is a binary search tree with the
following properties:
• Every node is either red or black;
• The root is black;
• Every leaf is NIL and 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.
(Note: Every node in a binary tree is either a leaf or has BOTH a
left AND right child.)
8.2
CSE 2331
Red-Black Tree: Example
7
3
l 26 SSSSS
l
l
SSSS
ll
l
l
SSS
l
l
l
l
17 Kl
41 A
K
s
s
AA
KKK
s
s
s
s
AA
s
s
K
s
s
K
s
s
s
s
14 A
21
30 A
47
0
''
A
A
| 00
AA
A
|
}}
A
}
|
A
A
}}
||
''
10
16
19
23
28
38 B
0
0
'
'
'
BB
''
00
00
''
''
BB
'
'
'
%%%
%
12
15
''
''
00
00
20
000
0
35
'''
'
39
''
''
...
8.3
CSE 2331
Red-Black Tree: Example
7
3
l 26 SSSSS
l
l
SSSS
ll
l
l
SSS
l
l
l
l
17 Kl
41 A
K
s
s
AA
KKK
s
s
s
s
AA
s
s
K
s
s
K
s
s
s
s
14 A
21
30 A
47
0
A
A
AA
AA
|| 00
}}
|
}
A
A
}
|
}
|
10
16
19
23
28
38 B
0
0
BB
00
00
BB
12
15
20
35
39
8.4
CSE 2331
NOT a Red-Black Tree
This tree is NOT a red-black tree. Why not?
7
ii 46 RRRRR
i
i
i
RRR
ii
i
i
i
RRR
i
i
i
i
i
i
25 Ii
65 >
I
u
u
>>
II
u
u
u
u
II
u
u
>
uu
uu
17 >
40 @
53 >
72
@
>
>
~
>>
>>
@@
~
~
~
10
21
29
43
49
60 @
/
/
.
@@
//
//
..
@
13
20
36
42
45
56
62
8.5
CSE 2331
Red-Black Tree Exercise
Color the following tree so that it is a red-black tree:
20 ?
o
o
??
o
o
??
o
o
o
oo
13 ?
26 ?
?
??
??
??
?
8
16
32
,
/
//
,
/
,,
//
//
50
00
8.6
CSE 2331
Red-Black Tree: Red Nodes
Definition. A red-black tree satisfies the following properties:
• Every node is either red or black;
• The root is black;
• Every leaf is NIL and 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.
Let h be the height of some red-black tree.
Let x be a leaf of the red-black tree.
How many red nodes can be on a path from the root to x?
8.7
CSE 2331
Red-Black Tree Height
Definition. A red-black tree satisfies the following properties:
• Every node is either red or black;
• The root is black;
• Every leaf is NIL and 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.
Theorem. A red-black tree with n internal nodes has height at
most 2 log2 (n + 1).
8.8
CSE 2331
Complete Binary Tree Size
Theorem 1. A complete binary search tree of height h has
2h+1 − 1 nodes.
Proof. Level i has 2i nodes (i = 0, 1, . . . , h).
1 + 2 + 22 + 23 + . . . + 2h = 2h+1 − 1.
8.9
08_red_black_tree.pdf (PDF, 144.06 KB)
Use the permanent link to the download page to share your document on Facebook, Twitter, LinkedIn, or directly with a contact by e-Mail, Messenger, Whatsapp, Line..
Use the short link to share your document on Twitter or by text message (SMS)
Copy the following HTML code to share your document on a Website or Blog