View
229
Download
1
Category
Preview:
Citation preview
8/14/2019 Cormen Algo-lec10
1/29
Introduction to Algorithms
6.046J/18.401JLECTURE 10
Balanced Search Trees Red-black trees
Height of a red-black tree
Rotations
Insertion
Prof. Erik Demaine
October 19, 2005 Copyright 2001-5 by Erik D. Demaine and Charles E. Leiserson L7.1
8/14/2019 Cormen Algo-lec10
2/29
Balanced search trees
Balanced search tree: A search-tree datastructure for which a height ofO(lg n) isguaranteed when implementing a dynamicset ofn items.
AVL trees 2-3 treesExamples: 2-3-4 trees
B-trees Red-black trees
October 19, 2005 Copyright 2001-5 by Erik D. Demaine and Charles E. Leiserson L7.2
8/14/2019 Cormen Algo-lec10
3/29
Red-black trees
This data structure requires an extra one-
bit colorfield in each node.Red-black properties:
1. Every node is either red or black.
2. The root and leaves (NILs) are black.
3. If a node is red, then its parent is black.4. All simple paths from any nodex to a
descendant leaf have the same numberof black nodes = black-height(x).
October 19, 2005 Copyright 2001-5 by Erik D. Demaine and Charles E. Leiserson L7.3
8/14/2019 Cormen Algo-lec10
4/29
Example of a red-black tree
h = 4
88 1111
1010
1818
2626
2222
33
77
NIL NIL
NIL NIL NIL NIL
NIL
NIL NIL
October 19, 2005 Copyright 2001-5 by Erik D. Demaine and Charles E. Leiserson L7.4
8/14/2019 Cormen Algo-lec10
5/29
Example of a red-black tree
88 1111
1010
1818
2626
2222
33
77
NIL NIL
NIL NIL NIL NIL
NIL
NIL NIL
1. Every node is either red or black.October 19, 2005 Copyright 2001-5 by Erik D. Demaine and Charles E. Leiserson L7.5
8/14/2019 Cormen Algo-lec10
6/29
Example of a red-black tree
88 1111
1010
1818
2626
2222
33
77
NIL NIL
NIL NIL NIL NIL
NIL
NIL NIL
2. The root and leaves (NILs) are black.October 19, 2005 Copyright 2001-5 by Erik D. Demaine and Charles E. Leiserson L7.6
8/14/2019 Cormen Algo-lec10
7/29
Example of a red-black tree
88 1111
1010
1818
2626
2222
33
77
NIL NIL
NIL NIL NIL NIL
NIL
NIL NIL
3. If a node is red, then its parent is black.October 19, 2005 Copyright 2001-5 by Erik D. Demaine and Charles E. Leiserson L7.7
8/14/2019 Cormen Algo-lec10
8/29
Example of a red-black tree
88 1111
1010
1818
2626
2222
33
77
NIL NIL
NIL
bh = 2
bh = 1
bh = 1
bh = 2
bh = 0 NIL NIL NIL NIL NIL NIL4. All simple paths from any nodex to a
descendant leaf have the same number of
black nodes = black-height(x).October 19, 2005 Copyright 2001-5 by Erik D. Demaine and Charles E. Leiserson L7.8
8/14/2019 Cormen Algo-lec10
9/29
Height of a red-black tree
Theorem. A red-black tree with n keys has heighth 2 lg(n + 1).
Proof. (The book uses induction. Read carefully.)INTUITION: Merge red nodes
into their blackparents.
October 19, 2005 Copyright 2001-5 by Erik D. Demaine and Charles E. Leiserson L7.9
8/14/2019 Cormen Algo-lec10
10/29
Height of a red-black tree
Theorem. A red-black tree with n keys has heighth 2 lg(n + 1).
Proof. (The book uses induction. Read carefully.)INTUITION: Merge red nodes
into their blackparents.
October 19, 2005 Copyright 2001-5 by Erik D. Demaine and Charles E. Leiserson L7.10
8/14/2019 Cormen Algo-lec10
11/29
Height of a red-black tree
Theorem. A red-black tree with n keys has heighth 2 lg(n + 1).Proof. (The book uses induction. Read carefully.)
INTUITION: Merge red nodes
into their blackparents.
October 19, 2005 Copyright 2001-5 by Erik D. Demaine and Charles E. Leiserson L7.11
8/14/2019 Cormen Algo-lec10
12/29
Height of a red-black tree
Theorem. A red-black tree with n keys has heighth 2 lg(n + 1).Proof. (The book uses induction. Read carefully.)
INTUITION: Merge red nodes
into their blackparents.
October 19, 2005 Copyright 2001-5 by Erik D. Demaine and Charles E. Leiserson L7.12
8/14/2019 Cormen Algo-lec10
13/29
Height of a red-black tree
Theorem. A red-black tree with n keys has heighth 2 lg(n + 1).Proof. (The book uses induction. Read carefully.)
INTUITION: Merge red nodes
into their blackparents.
October 19, 2005 Copyright 2001-5 by Erik D. Demaine and Charles E. Leiserson L7.13
8/14/2019 Cormen Algo-lec10
14/29
Height of a red-black tree
Theorem. A red-black tree with n keys has heighth 2 lg(n + 1).Proof. (The book uses induction. Read carefully.)
INTUITION: Merge red nodes
into their blackparents.
h This process produces a tree in which each node
has 2, 3, or4 children.
The 2-3-4 tree has uniform depth hof leaves.October 19, 2005 Copyright 2001-5 by Erik D. Demaine and Charles E. Leiserson L7.14
8/14/2019 Cormen Algo-lec10
15/29
Proof (continued)
We have
h h/2, sinceat most half
the leaves on any path
are red. The number of leaves
in each tree is n + 1n + 1 2h'lg(n + 1) h'h/2h 2 lg(n + 1).
h
h
October 19, 2005 Copyright 2001-5 by Erik D. Demaine and Charles E. Leiserson L7.15
8/14/2019 Cormen Algo-lec10
16/29
Query operations
Corollary. The queries SEARCH, MIN,
MAX, SUCCESSOR, and PREDECESSORall run in O(lg n) time on a red-black
tree with n nodes.
October 19, 2005 Copyright 2001-5 by Erik D. Demaine and Charles E. Leiserson L7.16
8/14/2019 Cormen Algo-lec10
17/29
Modifying operations
The operations INSERT and DELETE cause
modifications to the red-black tree: the operation itself, color changes,
restructuring the links of the tree viarotations.
October 19, 2005 Copyright 2001-5 by Erik D. Demaine and Charles E. Leiserson L7.17
8/14/2019 Cormen Algo-lec10
18/29
Rotations
AA
BB
RIGHT-ROTATE(B)
BB
AA
LEFT-ROTATE(A)
Rotations maintain the inorder ordering of keys: a , b , c a A b B c.A rotation can be performed in O(1) time.
October 19, 2005 Copyright 2001-5 by Erik D. Demaine and Charles E. Leiserson L7.18
8/14/2019 Cormen Algo-lec10
19/29
Insertion into a red-black tree
IDEA: Insertx in tree. Colorx red. Only red-black property 3 might be violated. Move the
violation up the tree by recoloring until it canbe fixed with rotations and recoloring.
Example:
88
1010
1818
2626
2222
77
33
1111
October 19, 2005 Copyright 2001-5 by Erik D. Demaine and Charles E. Leiserson L7.19
8/14/2019 Cormen Algo-lec10
20/29
Insertion into a red-black tree
IDEA: Insertx in tree. Colorx red. Only red-black property 3 might be violated. Move the
violation up the tree by recoloring until it canbe fixed with rotations and recoloring.
Example: Insertx =15. Recolor, moving the
88 1111
1010
1818
2626
2222
77
1515
33
violation up the tree.October 19, 2005 Copyright 2001-5 by Erik D. Demaine and Charles E. Leiserson L7.20
8/14/2019 Cormen Algo-lec10
21/29
Insertion into a red-black tree
IDEA: Insertx in tree. Colorx red. Only red-black property 3 might be violated. Move the
violation up the tree by recoloring until it canbe fixed with rotations and recoloring.
Example: Insertx =15. Recolor, moving the
88 1111
1010
1818
2626
2222
77
1515
33
violation up the tree. RIGHT-ROTATE(18).
October 19, 2005 Copyright 2001-5 by Erik D. Demaine and Charles E. Leiserson L7.21
8/14/2019 Cormen Algo-lec10
22/29
Insertion into a red-black tree
IDEA: Insertx in tree. Colorx red. Only red-black property 3 might be violated. Move the
violation up the tree by recoloring until it canbe fixed with rotations and recoloring.
Example: Insertx =15. Recolor, moving the 88
1111
1010
1818
2626
2222
77
1515
33
violation up the tree. RIGHT-ROTATE(18).
LEFT-ROTATE(7) and recolor.October 19, 2005 Copyright 2001-5 by Erik D. Demaine and Charles E. Leiserson L7.22
8/14/2019 Cormen Algo-lec10
23/29
Insertion into a red-black tree
IDEA: Insertx in tree. Colorx red. Only red-black property 3 might be violated. Move the
violation up the tree by recoloring until it canbe fixed with rotations and recoloring.
Example: Insertx =15. Recolor, moving the
violation up the tree. RIGHT-ROTATE(18).
88 1111
1010
1818
2626
2222
77
1515
33
LEFT-ROTATE(7) and recolor.October 19, 2005 Copyright 2001-5 by Erik D. Demaine and Charles E. Leiserson L7.23
8/14/2019 Cormen Algo-lec10
24/29
Pseudocode
RB-INSERT(T,x)
TREE-INSERT(T,x)
color[x] RED only RB property 3 can be violatedwhilex root[T] and color[p[x]] = REDdo ifp[x] = left[p[p[x]]
theny right[p[p[x]] y = aunt/uncle ofxifcolor[y] = REDthen Case 1else ifx = right[p[x]]
then Case 2 Case 2 falls into Case 3Case 3
else then clause with left and right swappedcolor[root[T]] BLACK
October 19, 2005 Copyright 2001-5 by Erik D. Demaine and Charles E. Leiserson L7.24
8/14/2019 Cormen Algo-lec10
25/29
Graphical notation
Let denote a subtree with a black root.
All s have the same black-height.
October 19, 2005 Copyright 2001-5 by Erik D. Demaine and Charles E. Leiserson L7.25
8/14/2019 Cormen Algo-lec10
26/29
Case 1
BB
CC
DDAA
xy
BB
CC
DDAA
newxRecolor
(Or, children of Push Cs black onto A are swapped.) A andD, and recurse,since Cs parent may
be red.
October 19, 2005 Copyright 2001-5 by Erik D. Demaine and Charles E. Leiserson L7.26
8/14/2019 Cormen Algo-lec10
27/29
Case 2
BB
CC
AA
x
LEFT-ROTATE(A) CCy y
BB
x AA
Transform to Case 3.
October 19, 2005 Copyright 2001-5 by Erik D. Demaine and Charles E. Leiserson L7.27
8/14/2019 Cormen Algo-lec10
28/29
Case 3
Done! No more
violations of RBproperty 3 arepossible.
AA
CC
BB
x
y
RIGHT-ROTATE(C)
AA
BB
CC
October 19, 2005 Copyright 2001-5 by Erik D. Demaine and Charles E. Leiserson L7.28
8/14/2019 Cormen Algo-lec10
29/29
Analysis
Go up the tree performing Case 1, which only
recolors nodes.
If Case 2 or Case 3 occurs, perform 1 or2rotations, and terminate.
Running time: O(lg n) with O(1) rotations.RB-DELETE same asymptotic running timeand number of rotations as RB-INSERT (seetextbook).
October 19, 2005 Copyright 2001-5 by Erik D. Demaine and Charles E. Leiserson L7.29
Recommended