then y ← right[p[p[z]]] if color [y] =RED then color p[z] ←BLACK color [y ] ←BLACK
//case 1 //case 1
color [p[p[z]]] ← RED //case 1 z ←[p[z]] else if z = right [p[z]] then z← p[z] LEFT-ROTATE(T,z) color [p[z]] ←BLACK //case 2 //case 2 //case 3
//Set y.
//Turn y’s left subtree into x’s right subtree.
//Link x’s parent to y.
11 left[y] ←x 12 p[x ] ←y
//Put x on y’s left
RB-INSERT(T,z) //insert z into T
(a)
x A
B D w
Case 1 restructure
E x A
D B new w C E w
α
β
γ
C
ε
δ
δ
(d) (C)
δ
ε
δ
α
β
γ
(b)
x A
B c D w
Case 2
recolor
E
new x B c A D
α
β γ
C
α δ
β γ
C
E
δ
ε
δ
ε
δ
Reduce 1 black height
Left rotation
C A C
Change color: parent & grandpa right rotation
B B z A C
α β
δy
B z z A
δy γ α
γ
case 2-1
α
β
γ
δ
β
case 3-1
Right rotate
C y
C B B C Az z A z
α
B z
y
A
α
– Root Property: The root is black. – External Property: Every external node is black. – Internal Property: The children of a red node are black. – Depth property: All the external nodes have the same black depth, which is defined as the number of black ancestors minus one. – The height of a red-black tree storing n items is O(log n).
7
4 3 5
12 15 14
(i)Insert 14 Case 2-2
7
4 3 5 12
14 15
(j)
7
4 3 5 12
14 15 18
(k)
7
4 3 5 12
14 15 18
(l)
7
4 3 5 12
14 15 18 16
(m) Case 2-2
7
4 3 5 12
14 16 15 18
δ
γ
β γ
Case 3-2
β
Case 2-2
δ
α
β
γ
δ
insertion
4 4
7
4
7 12
(a) (b)
7
4 12 4
7
12
(c) Case 3-2
15
(d)
(e) Case 1-2 +root must be black
7
7 12 15 3
4
4
12 15
(f)
(g)
7
4 3 5
12 15
(h) Insert 5
C A D B z y A new z C D B z
α β
α δ γ ε β
δ γ
ε
Problem:連續雙red
α β γ δ ε :Black height不變
C
B z A D y
new z B z A
C
D y
γ
β
α
δ
ε
γ
β
α
δ
ε
做法:改變parent, uncle, grandparent的color
14 left[z] ←nil[T]
15 right[z] ← nil[T]
16 color[z] ← RED 17 RB-INSERT-FIXUT(T,z)
RB-INSERT-FIXUP(T,z) 1 while color [p[z]] =RED
2
3 4 5 6 7 8 9 10 11 12
do if p[z]=left [p[p[z]]]
Case 1-2: z’s uncle y is red
new z
C y A D C D
y
A
α
β δ
β
ε δ
B z
B z
γ
γ
ε
Problem:連續雙red
α β γ δ ε :Black height不變 If c’s parent is red? Continue…
C y B D
new z C y
B
D
α
β
α
z A
γ
β
γ
z A
δ
ε
δ
ε
做法:改變parent, uncle, grandparent的color
Case 2-1: z’s uncle y is black and z is a right child
Case 3-1: z’s uncle y is black and z is a left child
//Case 1 //Case 1 //Case 1 //Case 1
//Case 2 //Case 2
//Case 3 //Case 3 //Case 3 //Case 3 //Case 4 //Case 4 //Case 4 //Case 4 //Case 4
16
17 18
19

w ←right [p[x]]
(n)
7
4 3 5 12
14 16 15 17 18
(o) Insert 17
Case 1-2
7
4 3 5 12
14 16 15 17 18
(p) Case 3-2
14
7 4 3 5 12 15
16 18 17
(q)
Insertion complexity
• The insertion of a key-element item in a red-black tree storing n items can be done in O(log n) time and at most O(log n) recolorings and one trinode restructuring (a restructure operation).
red-black tree
Lai Ah Fur
•Background: •AVL trees may require many restructure operations (rotations) to be performed after an element removal, •(2,4) trees may require many fusing or split operations to be performed after either an insertion or removal. •The red-black tree, does not have these drawbacks. It requires that only O(1) structural changes be made after an update in order to stay balanced.
RB-DELETE(T,z)
1 if left[z]=nil[z] or right[z]=nil[T]
2
3
then y ←z
else z ←TREE-SUCCESSOR(z)
4 if left[y] ≠ nil[T] 5 6 then x← left[y] else x ← right[y]
7 p[x] ← p [y] 8 if p[y]= nil[T] 9 10 11 12 13 if y ≠z 14 15 then key [z] ← key [y] copy y’s satellite data into z then root [T] ← x else if y=left [p[z]] then left [p[z]] ← x else right [p[z]] ← x
Property of A red-black tree
• A red-black tree is a binary search tree with nodes colored red and black in a way that satisfies the following properties:
16 if color [y] = BLACK 17 then RB-DELETE-FIXUP(T,x)
18 return y
RB-DELETE FIXUP(T,x) //y為真正被deleted之node, x是y的right or left child