blob: 1cca36cfbaf7f3690812fd969d21906c05d32623 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
|
# 2-4 Trees
* is a rooted tree with the following properties:
* height: all leaves have the same depth
* degree: every internal node has 2, 3 or 4 children.
lemma:
> A 2-4 tree with n leaves has height at most log n.
# Red-Black Trees
* A binary search tree with logarithmic height.
1. tree with `n` values has a height of most 2logn
1. The `add(x)` and `remove(x)` operations on a red-black tree run in `O(logn)` worst case time.
1. The amortized number of rotations performed during an `add(x)` or `remove(x)` operation is constant.
Each node, `u`, has a colour which is either `red` or `black`.
* red: is represented by the value 0.
* black: is represented by the value 1.
A red-black tree implements the SSet interface and supports
operations `add(x)`, `remove(x)`, and `find(x)` in O(logn) worst-case time
per operation.
```java
class Node<T> extends BSTNode<Node<T>, T> {
byte colour;
void flipRight(Node<T> u) {
swapColours(u, u.left);
rotateRight(u);
}
void flipLeft(Node<T> u) {
swapColours(u, u.right);
rotateLeft(u);
}
boolean add(T x) {
Node<T> u = newNode(x);
u.colour = red;
boolean added = add(u);
if (added)
addFixup(u);
return added;
}
void addFixup(Node<T> u) {
while (u.colour == red) {
if (u == r) {
u.colour = black;
return;
}
Node<T> w = u.parent;
if (w.left.colour == black) {
flipLeft(w);
u = w;
w = u.parent;
}
if (w.colour == black)
return;
Node<T> g = w.parent;
if (g.right.colour == black) {
flipRight(g);
return;
} else {
pushBlack(g);
u.x = w.x;
u = w.right;
}
}
splice(w);
u.colour += w.colour;
u.parent = w.parent;
removeFixup(u);
return true;
}
void removeFixup(Node<T> u) {
while (u.colour > black) {
if (u == r) {
u.colour = black;
} else if (u.parent.left.colour == red) {
u = removeFixupCase1(u);
} else if (u == u.parent.left) {
u = removeFixupCase2(u);
} else {
u = removeFixupCase3(u);
}
}
if (u != r) {
Node<T> w = u.parent;
if (w.right.colour == red && w.left.colour == black) {
flipLeft(w);
}
}
}
Node<T> removeFixupCase3(Node<T> u) {
Node<T> w = u.parent;
Node<T> v = w.left;
pullBlack(w);
flipRight(w);
Node<T> q = w.left;
if (q.colour == red) {
rotateRight(w);
flipLeft(v);
pushBlack(q);
return q;
} else {
if (v.left.colour == red) {
pushBlack(v);
return v;
} else {
flipLeft(v);
return w;
}
}
}
}
```
The following properties are satisfied before and after any operation:
* black-height: there are the same # of black nodes on every root to the leaf path. (sum of colours on any root to leaf path is the same.)
* no-red-edge: No two red nodes are adjacent. (except the root, `u.colour + u.parent.colour >= 1`)
The root is black.
|
