Red-Black TreesAgain
rank(x) = # black pointers on path from x to an external node. Same as #black nodes (excluding x) from x to an external node. rank(external node) = 0.
An Example
3
10
2 1 1
1 3
2
7 40
1 1
5
2 30 1
20
1 1
35
45
1 60 0
0 0 0 0 0
0 0 0
25
0 0
Properties Of rank(x) 3
10
2 1 1
1 3
2
7 40
1 1
5
2 30 1
20
45
1
1
25
35
1 60
0
0 0
0
0
0 0
rank(x) = 0 for x an external node. rank(x) = 1 for x parent of external node.
Properties Of rank(x) 3
10
2 1 1
1 3
2
7 40
1 1
5
2 30 1
20
45
1
1
25
35
1 60
0
0 0
0
0
0 0
p(x) exists => rank(x) <= rank(p(x)) <= rank(x) + 1. g(x) exists => rank(x) < rank(g(x)).
Red-Black Tree
A binary search tree is a red-black tree iff integer ranks can be assigned to its nodes so as to satisfy the stated 4 properties of rank.
Relationship Between 3rank() And Color
10
2 1 1
1 3
2
7 40
1 1
5
2 30 1
20
45
1
1
25
35
1 60
0
0 0
0
0
0 0
(p(x),x) is a red pointer iff rank(x) = rank(p(x)). (p(x),x) is a black pointer iff rank(x) = rank(p(x)) 1.
Relationship Between rank() And Color
Root is black. Other nodes:
Red iff pointer from parent is red. Black iff pointer from parent is black.
Relationship Between 3rank() And Color
10
2 1 1
1 3
2
7 40
1 1
5
2 30 1
20
45
1
1
25
35
1 60
0
0 0
0
0
0 0
Given rank(root) and node/pointer colors, remaining ranks may be computed on way down.
rank(root) & tree height
3
10
2 1 1
1 3
2
7 40
1 1
5
2 30 1
20
45
1
1
25
35
1 60
0
0 0
0
0
0 0
Height <= 2 * rank(root).
rank(root) & tree height
3
10
2 1 1
1 3
2
7 40
1 1
5
2 30 1
20
45
1
1
25
35
1 60
0
0 0
0
0
0 0
No external nodes at levels 1, 2, , rank(root).
rank(root) & tree height
No external nodes at levels 1, 2, , rank(root).
So, #nodes >= S1 <= i <= rank(root) 2i -1 = 2 rank(root) 1. So, rank(root) <= log2(n+1).
So, height(root) <= 2log2(n+1).
Join(S,m,B)
Input
Dictionary S of pairs with small keys. Dictionary B of pairs with big keys. An additional pair m. All keys in S are smaller than [Link]. All keys in B are bigger than [Link].
Output
A dictionary that contains all pairs in S and B plus the pair m. Dictionaries S and B may be destroyed.
Join Binary Search Trees
m
O(1) time.
Join Red-black Trees
When rank(S) = rank(B), use binary search tree method.
m
rank(root) = rank(S) + 1 = rank(B) + 1.
rank(S) > rank(B)
Follow right child pointers from root of S to first node x whose rank equals rank(B).
p(x) S a x b
p(x) m x a b B
rank(S) > rank(B)
If there are now 2 consecutive red pointers/nodes, perform bottom-up rebalancing beginning at m. O(rank(S) rank(B)).
p(x) p(x) m
S
a
x
x b a b
rank(S) < rank(B)
Follow left child pointers from root of B to first node x whose rank equals rank(S). Similar to case when rank(S) > rank(B).
Split(k)
Inverse of join. Obtain
S dictionary of pairs with key < k. B dictionary of pairs with key > k. m pair with key = k (if present).
Split A Binary Search Tree
A S B
a
C
B
b D E d m f g
Split A Binary Search Tree
S B
B
C b D E d m f g a
Split A Binary Search Tree
S B B b
A
C a D E d m f g
Split A Binary Search Tree
S B B C c d m f g b
A
a D E
Split A Binary Search Tree
S B B C c E D b
A
a
e
f
m g
Split A Binary Search Tree
S B B C c e m f g E D b
A
a
Split A Binary Search Tree
S B B C c e m E f D b
A
a
Split A Red-Black Tree
Previous strategy does not split a red-black tree into two red-black trees. Must do a search for m followed by a traceback to the root. During the traceback use the join operation to construct S and B.
Split A Red-Black Tree
A
S=f
B
B=g
a
C
b D
c
E
d m
e
f
Split A Red-Black Tree
A
S=f
B
B=g
a
C
b D
c
E
Split A Red-Black Tree
A
S=f
B
B=g
a
C
S = join(e, E, S)
b
c
E
D d
Split A Red-Black Tree
A
S=f
B
B =g
a
C
S = join(e, E, S)
b
B = join(B, D, d)
D d
Split A Red-Black Tree
A
S=f
B
B =g
a
C
S = join(e, E, S)
b
B = join(B, D, d) S = join(c, C, S)
Split A Red-Black Tree
A
S=f
B
b
B =g
S = join(e, E, S)
B = join(B, D, d) S = join(c, C, S) B = join(B, B, b)
Split A Red-Black Tree
A
S=f
B =g
S = join(e, E, S)
B = join(B, D, d) S = join(c, C, S) B = join(B, B, b)
S = join(a, A, S)
Complexity Of Split
O(log n)