Cormen Algo-lec10
This document was uploaded by user and they confirmed that they have the permission to share it. If you are author or own the copyright of this book, please report to us by using this DMCA report form. Report DMCA
Overview
Download & View Cormen Algo-lec10 as PDF for free.
More details
- Words: 1,701
- Pages: 29
Introduction to Algorithms
6.046J/18.401J
LECTURE 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
Balanced search trees
Balanced search tree: A search-tree data structure for which a height of O(lg n) is guaranteed when implementing a dynamic set of n items.
Examples:
October 19, 2005
• AVL trees
• 2-3 trees • 2-3-4 trees • B-trees • Red-black trees
Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson
L7.2
Red-black trees
This data structure requires an extra onebit color field in each node. Red-black properties: 1. Every node is either red or black. 2. The root and leaves (NIL’s) are black. 3. If a node is red, then its parent is black.
4. All simple paths from any node x 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.3
Example of a red-black tree 77 33 NIL
18 18 NIL
10 10 88
11 11
NIL NIL NIL NIL
October 19, 2005
h=4
22 22 NIL
26 26 NIL
Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson
NIL
L7.4
Example of a red-black tree 77 33 NIL
18 18 NIL
10 10 88
22 22 11 11
NIL NIL NIL NIL
NIL
26 26 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
Example of a red-black tree 77 33 NIL
18 18 NIL
10 10 88
22 22 11 11
NIL NIL NIL NIL
NIL
26 26 NIL
NIL
2. The root and leaves (NIL’s) are black.
October 19, 2005
Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson
L7.6
Example of a red-black tree 77 33 NIL
18 18 NIL
10 10 88
22 22 11 11
NIL NIL NIL NIL
NIL
26 26 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
Example of a red-black tree 77 bh = 2 33 NIL
18 18 bh = 2 NIL
bh = 1 10 10 bh = 1
88
22 22 11 11
bh = 0 NIL NIL NIL NIL
NIL
26 26 NIL
NIL
4. All simple paths from any node x 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
Height of a red-black tree
Theorem. A red-black tree with n keys has height
h ≤ 2 lg(n + 1).
Proof. (The book uses induction. Read carefully.)
INTUITION:
• Merge red nodes into their black parents.
October 19, 2005
Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson
L7.9
Height of a red-black tree
Theorem. A red-black tree with n keys has height
h ≤ 2 lg(n + 1).
Proof. (The book uses induction. Read carefully.)
INTUITION:
• Merge red nodes into their black parents.
October 19, 2005
Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson
L7.10
Height of a red-black tree
Theorem. A red-black tree with n keys has height
h ≤ 2 lg(n + 1).
Proof. (The book uses induction. Read carefully.)
INTUITION:
• Merge red nodes into their black parents.
October 19, 2005
Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson
L7.11
Height of a red-black tree
Theorem. A red-black tree with n keys has height
h ≤ 2 lg(n + 1).
Proof. (The book uses induction. Read carefully.)
INTUITION:
• Merge red nodes into their black parents.
October 19, 2005
Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson
L7.12
Height of a red-black tree
Theorem. A red-black tree with n keys has height
h ≤ 2 lg(n + 1).
Proof. (The book uses induction. Read carefully.)
INTUITION:
• Merge red nodes into their black parents.
October 19, 2005
Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson
L7.13
Height of a red-black tree
Theorem. A red-black tree with n keys has height
h ≤ 2 lg(n + 1).
Proof. (The book uses induction. Read carefully.)
INTUITION:
• Merge red nodes h′ into their black parents. • This process produces a tree in which each node has 2, 3, or 4 children. • The 2-3-4 tree has uniform depth h′ of leaves. October 19, 2005
Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson
L7.14
Proof (continued)
• We have h′ ≥ h/2, since at most half the leaves on any path are red.
h
• The number of leaves
in each tree is n + 1
⇒ n + 1 ≥ 2h' ⇒ lg(n + 1) ≥ h' ≥ h/2 ⇒ h ≤ 2 lg(n + 1).
h′
October 19, 2005
Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson
L7.15
Query operations
Corollary. The queries SEARCH, MIN, MAX, SUCCESSOR, and PREDECESSOR all 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
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 via “rotations”.
October 19, 2005
Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson
L7.17
Rotations RIGHT-ROTATE(B)
BB
LEFT-ROTATE(A)
AA αα
AA
ββ
γγ
αα
BB ββ
γγ
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
Insertion into a red-black tree
IDEA: Insert x in tree. Color x red. Only redblack property 3 might be violated. Move the violation up the tree by recoloring until it can be fixed with rotations and recoloring. Example:
77 33
18 18 10 10 88
October 19, 2005
22 22 11 11
Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson
26 26
L7.19
Insertion into a red-black tree
IDEA: Insert x in tree. Color x red. Only redblack property 3 might be violated. Move the violation up the tree by recoloring until it can be fixed with rotations and recoloring. Example: 33 • Insert x =15.
• Recolor, moving the
violation up the tree.
77 18 18 10 10 88
22 22 11 11
26 26
15 15 October 19, 2005
Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson
L7.20
Insertion into a red-black tree
IDEA: Insert x in tree. Color x red. Only redblack property 3 might be violated. Move the violation up the tree by recoloring until it can be fixed with rotations and recoloring. Example: 33 • Insert x =15.
• Recolor, moving the
violation up the tree.
• RIGHT-ROTATE(18). October 19, 2005
77 18 18 10 10 88
22 22 11 11
26 26
15 15
Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson
L7.21
Insertion into a red-black tree
IDEA: Insert x in tree. Color x red. Only redblack property 3 might be violated. Move the violation up the tree by recoloring until it can be fixed with rotations and recoloring. 77
Example: 33 • Insert x =15.
88 • Recolor, moving the
violation up the tree.
• RIGHT-ROTATE(18). • LEFT-ROTATE(7) and recolor. October 19, 2005
10 10 18 18 11 11 15 15
Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson
22 22 26 26 L7.22
Insertion into a red-black tree
IDEA: Insert x in tree. Color x red. Only redblack property 3 might be violated. Move the violation up the tree by recoloring until it can be fixed with rotations and recoloring. Example: 77 • Insert x =15.
• Recolor, moving the 33 88 violation up the tree.
• RIGHT-ROTATE(18). • LEFT-ROTATE(7) and recolor. October 19, 2005
10 10 18 18 11 11 15 15
Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson
22 22 26 26
L7.23
Pseudocode
RB-INSERT(T, x) TREE-INSERT(T, x) color[x] ← RED ⊳ only RB property 3 can be violated while x ≠ root[T] and color[p[x]] = RED do if p[x] = left[p[p[x]] then y ← right[p[p[x]] ⊳ y = aunt/uncle of x if color[y] = RED then 〈Case 1〉 else if x = right[p[x]] then 〈Case 2〉 ⊳ Case 2 falls into Case 3 〈Case 3〉 else 〈“then” clause with “left” and “right” swapped〉 color[root[T]] ← BLACK October 19, 2005
Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson
L7.24
Graphical notation
Let All
October 19, 2005
denote a subtree with a black root. ’s have the same black-height.
Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson
L7.25
Case 1 Recolor
CC DD
AA
x
BB
new x DD
AA BB
(Or, children of A are swapped.)
October 19, 2005
y
CC
Push C’s black onto
A and D, and recurse, since C’s parent may be red.
Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson
L7.26
Case 2
CC AA
x
BB
LEFT-ROTATE(A)
CC
y
y
BB
x
AA
Transform to Case 3.
October 19, 2005
Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson
L7.27
Case 3
CC BB
x
AA
RIGHT-ROTATE(C) y
BB
AA
CC
Done! No more violations of RB property 3 are possible. October 19, 2005
Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson
L7.28
Analysis
• Go up the tree performing Case 1, which only recolors nodes. • If Case 2 or Case 3 occurs, perform 1 or 2 rotations, and terminate. Running time: O(lg n) with O(1) rotations.
RB-DELETE — same asymptotic running time and number of rotations as RB-INSERT (see textbook). October 19, 2005
Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson
L7.29
6.046J/18.401J
LECTURE 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
Balanced search trees
Balanced search tree: A search-tree data structure for which a height of O(lg n) is guaranteed when implementing a dynamic set of n items.
Examples:
October 19, 2005
• AVL trees
• 2-3 trees • 2-3-4 trees • B-trees • Red-black trees
Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson
L7.2
Red-black trees
This data structure requires an extra onebit color field in each node. Red-black properties: 1. Every node is either red or black. 2. The root and leaves (NIL’s) are black. 3. If a node is red, then its parent is black.
4. All simple paths from any node x 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.3
Example of a red-black tree 77 33 NIL
18 18 NIL
10 10 88
11 11
NIL NIL NIL NIL
October 19, 2005
h=4
22 22 NIL
26 26 NIL
Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson
NIL
L7.4
Example of a red-black tree 77 33 NIL
18 18 NIL
10 10 88
22 22 11 11
NIL NIL NIL NIL
NIL
26 26 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
Example of a red-black tree 77 33 NIL
18 18 NIL
10 10 88
22 22 11 11
NIL NIL NIL NIL
NIL
26 26 NIL
NIL
2. The root and leaves (NIL’s) are black.
October 19, 2005
Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson
L7.6
Example of a red-black tree 77 33 NIL
18 18 NIL
10 10 88
22 22 11 11
NIL NIL NIL NIL
NIL
26 26 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
Example of a red-black tree 77 bh = 2 33 NIL
18 18 bh = 2 NIL
bh = 1 10 10 bh = 1
88
22 22 11 11
bh = 0 NIL NIL NIL NIL
NIL
26 26 NIL
NIL
4. All simple paths from any node x 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
Height of a red-black tree
Theorem. A red-black tree with n keys has height
h ≤ 2 lg(n + 1).
Proof. (The book uses induction. Read carefully.)
INTUITION:
• Merge red nodes into their black parents.
October 19, 2005
Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson
L7.9
Height of a red-black tree
Theorem. A red-black tree with n keys has height
h ≤ 2 lg(n + 1).
Proof. (The book uses induction. Read carefully.)
INTUITION:
• Merge red nodes into their black parents.
October 19, 2005
Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson
L7.10
Height of a red-black tree
Theorem. A red-black tree with n keys has height
h ≤ 2 lg(n + 1).
Proof. (The book uses induction. Read carefully.)
INTUITION:
• Merge red nodes into their black parents.
October 19, 2005
Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson
L7.11
Height of a red-black tree
Theorem. A red-black tree with n keys has height
h ≤ 2 lg(n + 1).
Proof. (The book uses induction. Read carefully.)
INTUITION:
• Merge red nodes into their black parents.
October 19, 2005
Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson
L7.12
Height of a red-black tree
Theorem. A red-black tree with n keys has height
h ≤ 2 lg(n + 1).
Proof. (The book uses induction. Read carefully.)
INTUITION:
• Merge red nodes into their black parents.
October 19, 2005
Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson
L7.13
Height of a red-black tree
Theorem. A red-black tree with n keys has height
h ≤ 2 lg(n + 1).
Proof. (The book uses induction. Read carefully.)
INTUITION:
• Merge red nodes h′ into their black parents. • This process produces a tree in which each node has 2, 3, or 4 children. • The 2-3-4 tree has uniform depth h′ of leaves. October 19, 2005
Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson
L7.14
Proof (continued)
• We have h′ ≥ h/2, since at most half the leaves on any path are red.
h
• The number of leaves
in each tree is n + 1
⇒ n + 1 ≥ 2h' ⇒ lg(n + 1) ≥ h' ≥ h/2 ⇒ h ≤ 2 lg(n + 1).
h′
October 19, 2005
Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson
L7.15
Query operations
Corollary. The queries SEARCH, MIN, MAX, SUCCESSOR, and PREDECESSOR all 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
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 via “rotations”.
October 19, 2005
Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson
L7.17
Rotations RIGHT-ROTATE(B)
BB
LEFT-ROTATE(A)
AA αα
AA
ββ
γγ
αα
BB ββ
γγ
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
Insertion into a red-black tree
IDEA: Insert x in tree. Color x red. Only redblack property 3 might be violated. Move the violation up the tree by recoloring until it can be fixed with rotations and recoloring. Example:
77 33
18 18 10 10 88
October 19, 2005
22 22 11 11
Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson
26 26
L7.19
Insertion into a red-black tree
IDEA: Insert x in tree. Color x red. Only redblack property 3 might be violated. Move the violation up the tree by recoloring until it can be fixed with rotations and recoloring. Example: 33 • Insert x =15.
• Recolor, moving the
violation up the tree.
77 18 18 10 10 88
22 22 11 11
26 26
15 15 October 19, 2005
Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson
L7.20
Insertion into a red-black tree
IDEA: Insert x in tree. Color x red. Only redblack property 3 might be violated. Move the violation up the tree by recoloring until it can be fixed with rotations and recoloring. Example: 33 • Insert x =15.
• Recolor, moving the
violation up the tree.
• RIGHT-ROTATE(18). October 19, 2005
77 18 18 10 10 88
22 22 11 11
26 26
15 15
Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson
L7.21
Insertion into a red-black tree
IDEA: Insert x in tree. Color x red. Only redblack property 3 might be violated. Move the violation up the tree by recoloring until it can be fixed with rotations and recoloring. 77
Example: 33 • Insert x =15.
88 • Recolor, moving the
violation up the tree.
• RIGHT-ROTATE(18). • LEFT-ROTATE(7) and recolor. October 19, 2005
10 10 18 18 11 11 15 15
Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson
22 22 26 26 L7.22
Insertion into a red-black tree
IDEA: Insert x in tree. Color x red. Only redblack property 3 might be violated. Move the violation up the tree by recoloring until it can be fixed with rotations and recoloring. Example: 77 • Insert x =15.
• Recolor, moving the 33 88 violation up the tree.
• RIGHT-ROTATE(18). • LEFT-ROTATE(7) and recolor. October 19, 2005
10 10 18 18 11 11 15 15
Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson
22 22 26 26
L7.23
Pseudocode
RB-INSERT(T, x) TREE-INSERT(T, x) color[x] ← RED ⊳ only RB property 3 can be violated while x ≠ root[T] and color[p[x]] = RED do if p[x] = left[p[p[x]] then y ← right[p[p[x]] ⊳ y = aunt/uncle of x if color[y] = RED then 〈Case 1〉 else if x = right[p[x]] then 〈Case 2〉 ⊳ Case 2 falls into Case 3 〈Case 3〉 else 〈“then” clause with “left” and “right” swapped〉 color[root[T]] ← BLACK October 19, 2005
Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson
L7.24
Graphical notation
Let All
October 19, 2005
denote a subtree with a black root. ’s have the same black-height.
Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson
L7.25
Case 1 Recolor
CC DD
AA
x
BB
new x DD
AA BB
(Or, children of A are swapped.)
October 19, 2005
y
CC
Push C’s black onto
A and D, and recurse, since C’s parent may be red.
Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson
L7.26
Case 2
CC AA
x
BB
LEFT-ROTATE(A)
CC
y
y
BB
x
AA
Transform to Case 3.
October 19, 2005
Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson
L7.27
Case 3
CC BB
x
AA
RIGHT-ROTATE(C) y
BB
AA
CC
Done! No more violations of RB property 3 are possible. October 19, 2005
Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson
L7.28
Analysis
• Go up the tree performing Case 1, which only recolors nodes. • If Case 2 or Case 3 occurs, perform 1 or 2 rotations, and terminate. Running time: O(lg n) with O(1) rotations.
RB-DELETE — same asymptotic running time and number of rotations as RB-INSERT (see textbook). October 19, 2005
Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson
L7.29
Related Documents
Cormen Algo-lec15
December 2019 12
Cormen Algo-lec12
December 2019 12
Cormen Algo-lec16
December 2019 11
Cormen Algo-lec13
December 2019 11
Cormen Algo-lec10
December 2019 1