Computer Science Programming Homework
xyf123
CH13RB-Tree-P1-5-7-2019.pdf
5/7/2019
1
CS146 Data Structures and
Algorithms
Chapter 13: Red-Black Trees
Slides made by Dr. Mike Wu of SJSU and some adopted from other universities such as Stanford and U of NC at Chapel Hills.
• Many search-tree schemes that are “balanced” in order to guarantee that basic dynamic-set
operations take O(lg n ) time in the worse case.
e.g. AVL trees
Red-black trees
Balanced search Trees
L13.2
AVL Trees
• a self-balancing (or height-balanced) binary search tree is any node-based binary search tree that automatically keeps its
height (maximal number of levels below the root) small in the
face of arbitrary item insertions and deletions.
L13.3
An example of an unbalanced tree;
following the path from the root to a node
takes an average of 3.27 node accesses.
The same tree after being
height-balanced; the average
path effort decreased to 3.00
node accesses.
Red-Black Trees
• Red-black trees are a variation of binary search trees to ensure that the tree is balanced.
▪ Height is O(lg n), where n is the number of nodes.
• To guarantee that operations take O(lg n) time in the worst case.
L13.4
5/7/2019
2
Red-Black Tree
• Binary search tree with + 1 bit per node: the attribute color, which is either red or black.
• All other attributes of BSTs are inherited:
▪ key, left, right, and p.
• All empty trees (leaves) are colored black. ▪ We use a single sentinel, nil, for all the leaves of
red-black tree T, with nil.color = black.
▪ The root’s parent is also T.nil.
L13.5 L13.6
Example of a Red-black Tree
Leaves and the root’s parent omitted
entirely
We omit the leaves when we draw BR trees, because we generally
confine our interest to the internal nodes, since they hold the key.
L13.7
Example of a Red-black Tree
L13.8
5/7/2019
3
Red-black Properties
1. Every node is either red or black.
2. The root is black.
3. Every leaf (nil) is black.
4. If a node is red, then both its children are
black.
5. For each node, all paths from the node to
descendant leaves contain the same number
of black nodes. (i.e. black-height(x)).
L13.9
Example of a Red-black Tree
L13.10
1. Every node is either red or black.
Example of a Red-black Tree
L13.11
2. 3. The root and leaves (NIL’s) are black.
Example of a Red-black Tree
L13.12
5/7/2019
4
4. If a node is red, then its children are black.
?? Means
If a node is red, then its parent is black.
Example of a Red-black Tree
L13.13
5. All simple paths from any node x to a
descendant leaf have the same number of
black nodes = black-height(x).
Example of a Red-black Tree
L13.14
black-height of the node: bh(x)
# of black nodes on any path from, but not including,
a node x down to a leaf
black-height of a RB tree = black-height of its root
L13.15 L13.16
5/7/2019
5
Leaves and the root’s parent omitted
entirely
We omit the leaves when we draw BR trees, because we generally
confine our interest to the internal nodes, since they hold the key.
L13.17
Height of a Red-black Tree
• Height of a node: ▪ h(x) = number of edges in a longest path to a leaf.
• Black-height of a node x, bh(x): ▪ bh(x) = number of black nodes (including T.nil)
on the path from x to leaf, not counting x.
• Black-height of a red-black tree is the black-height of its root.
▪ By Property 5, black height is well defined.
L13.18
Height of a Red-black Tree
• Example:
• Height of a node:
h(x) = # of edges in a
longest path to a leaf.
• Black-height of a node bh(x) = # of black nodes on path from x to leaf,
not counting x.
• How are they related? ▪ bh(x) ≤ h(x) ≤ 2 bh(x)
26
17
30 47
38 50
41
T.nil
h=4
bh=2
h=3
bh=2
h=2
bh=1
h=2
bh=1 h=1
bh=1
h=1
bh=1
h=1
bh=1
L13.19
Lemma “RB Height”
Consider a node x in an RB tree: The longest
descending path from x to a leaf has length h(x),
which is at most twice the length of the shortest
descending path from x to a leaf.
Proof:
# black nodes on any path from x = bh(x) (prop 5)
# nodes on shortest path from x, s(x). (prop 1)
But, there are no consecutive red (prop 4),
and we end with black (prop 3), so h(x) ≤ 2 bh(x).
Thus, h(x) ≤ 2 s(x). QED
L13.20
5/7/2019
6
Bound on RB Tree Height
• Lemma: The subtree rooted at any node x has 2bh(x)–1 internal nodes.
• Proof: By induction on height of x.
▪ Base Case: Height h(x) = 0 x is a leaf bh(x) = 0. Subtree has 20–1 = 0 nodes.
▪ Induction Step: Height h(x) = h > 0 and bh(x) = b.
o Each child of x has height h - 1 and black-height either b (child is red) or b - 1 (child is black).
o By ind. hyp., each child has 2bh(x)– 1–1 internal nodes.
o Subtree rooted at x has 2 (2bh(x) – 1 – 1)+1 = 2bh(x) – 1 internal nodes. (The +1 is for x itself.)
L13.21
Bound on RB Tree Height
• Lemma: The subtree rooted at any node x has 2bh(x)–1 internal nodes.
• Lemma 13.1: A red-black tree with n internal nodes has height at most 2 lg(n+1).
• Proof: ▪ By the above lemma, n 2bh – 1,
▪ and since bh h/2, we have n 2h/2 – 1.
▪ h 2 lg(n + 1).
L13.22
Examples of RB Trees based on full BST of 15 nodes Operations on RB Trees
• All operations can be performed in O(lg n) time.
• The query operations, which don’t modify the tree, are performed in exactly the same way as they are in BSTs.
• These operations take O(lg n) time: ▪ Minimum(), Maximum()
▪ Successor(), Predecessor()
▪ Search()
• Insert() and Delete(): ▪ Will also take O(lg n) time
• Insertion and Deletion are not straightforward. Why?
L13.24
5/7/2019
7
Red-Black Trees: An Example
• Color this tree: 7
5 9
1212
5 9
7
Red-black properties:
1. Every node is either red or black
2. The root is always black
3. Every leaf (NIL pointer) is black
4. If a node is red, both children are black
5. Every path from node to descendent leaf
contains the same number of black nodes L13.25
• Insert 8 ▪ Where does it go?
Red-Black Trees:
The Problem With Insertion
12
5 9
7
Red-black properties:
1. Every node is either red or black
2. The root is always black
3. Every leaf (NIL pointer) is black
4. If a node is red, both children are black
5. Every path from node to descendent leaf
contains the same number of black nodes L13.26
• Insert 8 ▪ Where does it go?
▪ What color
should it be?
Red-Black Trees:
The Problem With Insertion
12
5 9
7
8
Red-black properties:
1. Every node is either red or black
2. The root is always black
3. Every leaf (NIL pointer) is black
4. If a node is red, both children are black
5. Every path from node to descendent leaf
contains the same number of black nodes L13.27
• Insert 8 ▪ Where does it go?
▪ What color
should it be?
Red-Black Trees:
The Problem With Insertion
12
5 9
7
8
Red-black properties:
1. Every node is either red or black
2. The root is always black
3. Every leaf (NIL pointer) is black
4. If a node is red, both children are black
5. Every path from node to descendent leaf
contains the same number of black nodes L13.28
5/7/2019
8
Red-Black Trees:
The Problem With Insertion
• Insert 11 ▪ Where does it go?
12
5 9
7
8
Red-black properties:
1. Every node is either red or black
2. The root is always black
3. Every leaf (NIL pointer) is black
4. If a node is red, both children are black
5. Every path from node to descendent leaf
contains the same number of black nodes L13.29
Red-Black Trees:
The Problem With Insertion
• Insert 11 ▪ Where does it go?
▪ What color? 12
5 9
7
8
11
Red-black properties:
1. Every node is either red or black
2. The root is always black
3. Every leaf (NIL pointer) is black
4. If a node is red, both children are black
5. Every path from node to descendent leaf
contains the same number of black nodes L13.30
Red-Black Trees:
The Problem With Insertion
• Insert 11 ▪ Where does it go?
▪ What color?
o Can’t be red! (#4) 12
5 9
7
8
11
Red-black properties:
1. Every node is either red or black
2. The root is always black
3. Every leaf (NIL pointer) is black
4. If a node is red, both children are black
5. Every path from node to descendent leaf
contains the same number of black nodes L13.31
Red-Black Trees:
The Problem With Insertion
• Insert 11 ▪ Where does it go?
▪ What color?
o Can’t be red! (#4)
o Can’t be black! (#5)
12
5 9
7
8
11
Red-black properties:
1. Every node is either red or black
2. The root is always black
3. Every leaf (NIL pointer) is black
4. If a node is red, both children are black
5. Every path from node to descendent leaf
contains the same number of black nodes L13.32
5/7/2019
9
Red-Black Trees:
The Problem With Insertion
• Insert 11 ▪ Where does it go?
▪ What color?
o Solution:
recolor the tree
12
5 9
7
8
11
Red-black properties:
1. Every node is either red or black
2. The root is always black
3. Every leaf (NIL pointer) is black
4. If a node is red, both children are black
5. Every path from node to descendent leaf
contains the same number of black nodes L13.33
Red-Black Trees:
The Problem With Insertion
• Insert 10 ▪ Where does it go?
12
5 9
7
8
11
Red-black properties:
1. Every node is either red or black
2. The root is always black
3. Every leaf (NIL pointer) is black
4. If a node is red, both children are black
5. Every path from node to descendent leaf
contains the same number of black nodes L13.34
Red-Black Trees:
The Problem With Insertion
• Insert 10 ▪ Where does it go?
▪ What color? 12
5 9
7
8
11
10 Red-black properties:
1. Every node is either red or black
2. The root is always black
3. Every leaf (NIL pointer) is black
4. If a node is red, both children are black
5. Every path from node to descendent leaf
contains the same number of black nodes L13.35
Red-Black Trees:
The Problem With Insertion
• Insert 10 ▪ Where does it go?
▪ What color?
o Answer: no color! Tree
is too imbalanced
o Must change tree structure
to allow recoloring
▪ Goal: restructure tree in
O(lg n) time
12
5 9
7
8
11
10
L13.36
5/7/2019
10
RB Trees: Rotation
y
x
Left-Rotate(T, x)
x
y
Right-Rotate(T, y)
• Does rotation preserve inorder key ordering? • What would the code for rightRotate()
actually do?
L13.37
RB Trees: Rotation
• Answer: A lot of pointer manipulation ▪ x keeps its left child
▪ y keeps its right child
▪ x’s right child becomes y’s left child
▪ x’s and y’s parents change
• What is the running time?
y
x
Left-Rotate(T, x)
x
y
Right-Rotate(T, y)
L13.38
Rotation Example
• Rotate left about 9:
12
5 9
7
8
11
L13.39
Rotation Example
• Rotate left about 9:
5 12
7
9
118
L13.40
5/7/2019
11
RB Trees: Rotation
• Rotations are the basic tree-restructuring operation for almost all balanced search trees.
• Rotation takes a red-black-tree and a node, • Changes pointers to change the local structure, and • Won’t violate the binary-search-tree property. • Left rotation and right rotation are inverses.
y
x
Left-Rotate(T, x)
x
y
Right-Rotate(T, y)
L13.41
Left Rotation – Pseudo-code Left-Rotate (T, x)
1. y = x.right // Set y.
2. x.right = y.left //Turn y’s left subtree into x’s right subtree.
3. if y.left T.nil
4. then y.left.p = x
5. y.p = x.p // Link x’s parent to y.
6. if x.p == T.nil
7. then T.root = y
8. else if x == x.p.left
9. then x.p.left = y
10. else x.p.right = y
11. y.left = x // Put x on y’s left.
12. x.p = y
y
x
Left-Rotate(T, x)
x
y
Right-Rotate(T, y)
L13.42
Rotation
• The pseudo-code for Left-Rotate assumes that ▪ X.right T.nil, and
▪ root’s parent is T.nil.
• Left Rotation on x, makes x the left child of y, and the left subtree of y into the right subtree of x.
• Pseudocode for Right-Rotate is symmetric: exchange left and right everywhere.
• Time: O(1) for both Left-Rotate and Right-Rotate, since a constant number of pointers are modified.
