13 Red-Black Trees
13 Red-Black Trees
13 Red-Black Trees
Red-Black Tree
Hsu, Lih-Hsing
Red-black trees
One of 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.
Chapter 13
P.2
Each node of the tree now contains the fields color, key, left, right, and p. If a child or the parent of a node does not exist, the corresponding pointer field of the node contains the value NIL. We shall regard these NILs as being pointers to external nodes(leaves) of the binary search tree and the normal, key-bearing nodes as being internal nodes of the tree.
Chapter 13 P.4
A binary search tree is a red-black tree if it satisfies the following 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.
Chapter 13 P.5
Chapter 13
P.6
Chapter 13
P.7
Chapter 13
P.8
Lemma 13.1
Chapter 13
P.9
Proof.
We start by showing that the subtree rooted at any node x contains at least 2bh(x) 1 internal nodes. We prove this claim by induction on the height of x. if the eight of x is 0, then x must be a leaf(NIL[T]), and the sub tree rooted at x indeed contains at least 2bh(x) 1 = 20 1 =0 internal nodes.
P.10
Chapter 13
For the inductive step, consider a node x that has positive height and is an internal node with two children. Each child has a blackheight of either bh(x) or bh(x) 1, depending on whether its color is red or black, respectively. Since the height of a child of x is less than the height of x itself, we can apply the inductive hypothesis to conclude that each child has at least 2bh(x)-1 -1 internal nodes. Thus, the subtree rooted at x contains at least (2bh(x)-1 1)+(2bh(x)-1 1) +1 = 2bh(x) 1 internal nodes, which proves the claim.
Chapter 13 P.11
To complete the proof of the lemma, let h be the height of the tree. According to property 4, at least half the nodes on any simply path from the root to a leaf, not including the root, must be black. Consequently, the black-height of the root must be at least h/2; thus, n 2h/2 -1. Moving the 1 to the left-hand side and taking logarithms on both sides yields lg(n + 1) h/2, or h 2lg (n+1).
Chapter 13 P.12
13.2 Rotations
Chapter 13
P.13
LEFT-ROTATE(T,x)
1 y right[x] 2 right[x] left[y] 3 p[left[y]] x The code for RIGHT-ROTATE is symmetric. Both LEFT-ROTATE and RIGHT-ROTATE 4 p[y] p[x] run in O(1) time. 5 If p[x] = nil[T] 6 then root[T] y 7 else if x = left[p[x]] 8 then left[p[x]] y 9 else right[p[x]] y 10 left[y] x 11 p[x] y
Chapter 13 P.14
An example of LEFT-ROTATE(T,x)
Chapter 13
P.15
13.3 Insertion
RB-INSERT(T,x)
1 2 3 4 5 6 7 8
Chapter 13
y nil[T] x root[T] while x nil[T] do y x if key[z] < key[x] then x left[x] else x right[x] p[z] y
P.16
9 10 11 12 13 14 15 16 17
Chapter 13
if y = nil[T] then root[T] z else if key[z] < key[y] then left[y] z else right[y] z left[z] nil[T] right[z] nil[T] color[z] RED RB-INSERT-FIXUP(T, z)
P.17
RB-INSERT-FIXUP(T,z)
1 while color[p[z]] = RED 2 do if p[z] = left[p[p[z]]] 3 then y right[p[p[z]]] 4 if color[y] = RED 5 then color[p[z]] BLACK 6 color[y] BLACK 7 color[p[p[z]]] RED 8 z p[p[z]]
Chapter 13
9 10 11 12 13 14 15
else if z = right[p[z]] then z p[p[z]] Case 2 LEFT-ROTATE(T,z) Case 2 color[p[z]] BLACK Case 3 color[p[p[z]]] RED Case 3 RIGHT-ROTATE(T,p[p[z]]) Case 3 else (same as then clause with right and left exchanged) 16 color[root[T]] BLACK
Chapter 13 P.19
Chapter 13
P.20
Chapter 13
P.21
Chapter 13
P.22
Chapter 13
P.23
Analysis
RB-INSERT take a total of O(lg n) time. It never performs more than two rotations, since the while loop terminates if case 2 or case 3 executed.
Chapter 13
P.24
13.4 Deletion
RB-DELETE(T,z)
1 2 3 4 5 6 7 8 if left[z] = nil[T] or right[z] = nil[T] then y z else y TREE-SUCCESSOR(z) if left[y] nil[T] then x left[y] else x right[y] p[x] p[y] if p[y] = nil[T]
P.25
Chapter 13
9 then root[T] x 10 else if y = left[p[y]] 11 then left[p[y]] x 12 else right[p[y]] x 13 if y z 14 then key[z] key[y] 15 copy ys satellite data into z 16 if color[y] = BLACK 17 then RB-DELETE-FIXUP(T, x) 18 return y
Chapter 13 P.26
RB-DELETE-FIXUP(T, x)
RB-DELETE-FIXUP
1 2 3 4 5 6 7 8 while x root[T] and color[x] = BLACK do if x = left[p[x]] then w right[p[x]] if color[w] = RED then color[w] BLACK Case1 color[p[x]] = RED Case1 LEFT-ROTATE(T,p[x]) Case1 w right[p[x]] Case1
P.27
Chapter 13
9 10 11 12 13 14 15 16 17
Chapter 13
if color[right[w]] = BLACK and color[right[w]= BLACK then color[w] RED Case2 x p[x] Case2 else if color[right[w]] = BLACK then color[left[w]] BLACK Case3 color[w] RED Case3 RIGHT-ROTATE(T,w) Case3 w right[p[x]] Case3 color[w] color[p[x]] Case4
P.28
18 19 20 21 22
color[p[x]] BLACK Case4 color[right[w]] BLACK Case4 LEFT-ROTATE(T,p[x]) Case4 x root[T] Case4 else (same as then clause with right and left exchanged)
23 color[x] BLACK
Chapter 13
P.29
Chapter 13
P.30
Chapter 13
P.31
Analysis
The RB-DELETE-FIXUP takes O(lg n) time and performs at most three rotations. The overall time for RB-DELETE is therefore also O(lg n)
Chapter 13
P.32