定义：红黑树是Avl树的一个变种，它也是在二叉树的基础上添加平衡条件，只是它对平衡条件的定义不像AVl树那样直接，而是转化成对节点颜色规则的描述：
- 对于任意节点，要么是红色，要么是黑色；
- 根节点是黑色的；
- 如果一个节点是红色的，那么它的子节点必须是黑色的（即不能有两个连续的红色节点）；
- 任意节点到其下面各个空结点（后面称为nil节点，并约定其颜色为黑色）的路径上都包含相同数目的黑色节点（称为黑高）；
通过对任何一条从根到空节点的路径上各个结点的颜色进行约束，红黑树可以确保没有一条路径会比其他路径长出2倍，因而红黑树是近似平衡的。
1. 分析实现
为了便于处理实现时的边界条件，使用两个标记节点header和nil来充当哨兵，它们与树中的普通节点有相同的属性，颜色设为黑色。将header的值设为负无穷，因此它的右子节点就是真正的根，这样在进行遍历时便header作为起点。nil的值可以为任意值，将它作为所有空节点的统一引用，即让所有树叶的左右子节点都指向nil，那么在遍历时就可以将nil视为终点。
红黑树也是一颗查找二叉树，所以它的基本操作与查找二叉树一致，区别也在于插入和删除后的平衡恢复。只是实现平衡时的目标就是满足它对颜色规则的定义，至于树的平衡与否已经由规则本身去保证。
1.1. 插入
与二叉查找树一样，插入节点其实就是添加一个树叶，主要问题是在添加结束时可能要做一些调整来保证红黑树的规则不被破坏。
不过，根据规则4，可以知道，在插入之前任意节点到其下面各个nil的路径上都包含相同数目的黑节点数，所以如果能保证在节点插入前后父节点parent或者祖父节点grand到其下面nil的路径上的黑节点数不变，那么就可以保证整体红黑树不会破坏规则，这样就可以将平衡操作时需要考虑的范围缩小到grand。
由于插入红色节点不会影响路径上的黑节点数，因此就先将待插入的节点涂成红色，如果parent是黑色，那么插入直接完成。如果parent是红色，那么再分情况进行讨论。 先分析一下插入之前的可能情形，根据规则3，如果parent是红色，那么可以断定grand以及parent的另一个子节点一定是黑色。而且因为插入的是树叶节点在之前一定是nil，那么parent的另一个子节点必然也是nil。 再看parent的兄弟节点，如果它是黑色的，那么它一定也是nil节点；如果它是红色的，那么它的两个子节点一定都是nil节点。
所以，如果parent是红色，那么只有如下4种可能，而待插入节点的位置就是图中parent下面的两个nil之一。其中1和2，3和4分别是对称的两种情况，区别在于parent与grand的大小关系，因此可以进一步概括为parent的兄弟节点uncle是黑色还是红色的两种情况。
1.parent红色，uncle黑色（以情况1为例，即parent小于grand）
如果current小于parent，那么插入之后，可以将parent和grand的颜色互换，然后grand右旋，这样便保持原来以grand为根的子树的黑高不变，也就保证了整棵树不被破坏
如果current大于parent，则可以先将parent左旋，然后将current视为parent与上面进行相同操作即可
2.parent红色，uncle红色（以情况3为例）
这时旋转已经解决不了问题，不过可以通过颜色翻转来达到目标，即将grand与其左右子节点的颜色进行互换
但是，翻转会使grand变成红色，这时如果曾祖父也是红色，那么将违反了规则3 。因此可能需要朝着树根的方向进行逐层分析，直到不再有两个相连的红色节点或者到达树根为止，但这显然会很麻烦。事实上，由于颜色翻转的等价性，可以在查找插入节点位置的过程中，通过颜色翻转来避免掉uncle为红色的情况，即将颜色翻转的事情提前做了。
在自上而下的查找过程中，如果看到一个节点X的两个子节点都为红色，可以使X变成红色，子节点变成黑色（如果X是根，则可以在翻转之后再将其置为黑色），结果依然满足红黑树的规则。
只有当X的parent为红色时，才会破坏红黑树的规则。不过这时可以断定X的兄弟节点，X的grand，以及X的uncle都是黑色的（如果X的parent和uncle都为红色，那么一定会在自上而下的查找和翻转过程中被过滤掉）。那么可以将X视为current与上面进行相同的处理，如下所示：
然后，将X视为之前的current，对parent和grand进行换色和旋转
完成之后，继续重新向下遍历。由于X的孙子节点之前一定为黑色，而X的儿子节点在翻转之后也为黑色，因此在调整之后，可以保证接下来将有连续两层不会出现红节点。
https://github.com/shanhm1991/Echo/blob/master/src/main/java/io/github/echo/structure/tree/RBTreeSet.java1
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
| public boolean add(E e) {
nil.element = e;
RBNode<E> current = header;
RBNode<E> parent = header;
while(compare(e, current) != 0){
parent = current;
if(compare(e, current) < 0){
current = getLeft(current);
}else{
current = getRight(current);
}
if(getLeft(current).red && getRight(current).red){
current = handleReorient(current);
}
}
if(current != nil){
current.element = e;
return true;
}
current = new RBNode<>(e, nil, nil);
size++;
current.parent = parent;
if(compare(e, parent) < 0){
parent.left = current;
}else{
parent.right = current;
}
handleReorient(current);
return true;
}
private RBNode<E> handleReorient(RBNode<E> current) {
current.red = true;
getLeft(current).red = false;
getRight(current).red = false;
RBNode<E> subRoot = current;
RBNode<E> parent = current.parent;
if(parent.red){
RBNode<E> grand = parent.parent;
grand.red = true;
if(compare(current.element, grand) != compare(current.element, parent)) {
if(compare(current.element, parent) > 0){
rotateLeft(parent);
}else{
rotateRight(parent);
}
}
if(compare(current.element, grand) < 0){
subRoot = getLeft(grand);
subRoot.red = false;
rotateRight(grand);
}else{
subRoot = getRight(grand);
subRoot.red = false;
rotateLeft(grand);
}
}
getRight(header).red = false;
return subRoot;
}
|
总结节点插入问题：首先根据二叉树的性质，可以确定插入节点是添加树叶，其次对于红黑树，插入红色节点不会影响路径上的黑节点数，因此，先将插入节点设成红色。这时只要再考虑其parent是红色还是黑色，如果是黑色问题直接解决，如果是红色，再看uncle是红色还是黑色。如果uncle是黑色，可以通过变色旋转解决；如果是红色，那么通过颜色翻转也能达到目的，但这会使grand变成红色，需要进一步考虑曾祖父的颜色问题，向上递归解决。于是考虑在一开始向下的遍历过程中，提前翻转颜色来避免掉parent和unlce同时为红色的情况。因此，最终在插入节点时，实际需要考虑旋转调整的情形只有一种，即parent为红色，uncle为黑色。
1.2. 删除
对于节点删除，大概思路也是先将问题转化成删除树叶来简化问题，如果是红色树叶，直接删除，如果是黑色树叶，则再分情形进行讨论
根据二叉树的性质，在删除节点时可以转化为对前驱或后继节点的删除，不过在红黑树中，为了保证节点的颜色规则，替换时将只进行值的替换。另外，根据红黑树的定义，可以推论：如果一个树叶没有兄弟节点，那么它一定为红色，或者说如果一个树叶为黑色，则它必然有兄弟节点。而且，对于任意节点，其后继节点最多存在一个红色右子节点，前驱节点最多存在一个红色左子节点。
讨论删除黑色树叶的情形，由于黑色树叶必然会存在兄弟节点（树根除外），因此在下面的讨论中总是假设要删除的黑色树叶在左边（右边则对称处理），这时可以根据其brother和parent的颜色来将删除情形分为3种：
1.parent红色，brother黑色
由于current是树叶，可以断定brother不会再有黑色子节点，至多只能有一层红色子节点，下面针对brother有无左子节点进行讨论（brother有无右子节点并无影响，因此忽略）
1.1 brother没有左子节点：直接parent左旋
1.2 brother有左子节点：brother右旋，parent变黑色并左旋
2.parent黑色，brother红色
同样由于current是树叶，可以断定brother的必然有两个黑色子节点left和right，且下面至多只能有一层红色子节点，下面根据brother左儿子的子节点情况进行讨论（右儿子的子节点情况并无影响，因此忽略）
2.1 left没有子节点：brother与left换色，parent左旋
2.2 left有右子节点：将left右子节点涂成黑色，然后brother右旋，再将parent左旋
2.3 left没有右子节点，有左子节点：将left的左子节点涂成黑色，并且left右旋，这样将情形转化成2.2，然后brother右旋，parent左旋。
3.parent为黑色，brother为黑色
同样由于current是树叶，可以断定brother下面至多只能有一层红色的儿子节点
3.1 brother没有子节点：此时通过parent为根的子树自身已经解决不了问题，想法是将brother变成红色来降低parent子树的黑高，然后将parent子树视为current进行处理，下面再详细讨论
3.2 brother有右子节点：将brother的右儿子变成黑色，parent左旋
3.3 brother没有右子节点，但有左子节点：将brother的左儿子变成黑色，然后brother右旋，parent左旋。
上面一共将删除了黑色树叶分成了8种情形，除了3.1，其它都可以在parent子树内部解决问题。
为了进一步讨论3.1的情形，需要扩展下思维：可以将current是树叶这个前提去掉，然后将current视为根为黑色的子树。假设这时删除的黑色树叶落在current子树下面，并且遇到了情形3.1，那么可以看成将current子树整体的黑高降1，然后再根据brother子树和parent的情况来进行处理。如果依然解决不了问题， 再将parent树视为新的子树，再将祖父节点视为新的parent，这样逐层向上分析，直到能够在新的子树内解决问题或者到达树根为止。
下面画图进行说明，不过这里有一个假设：
在删除之前current子树的黑高一定大于1，那么brother子树的黑高必然也大于1，也就是说brother到nil的路径上必然还有黑色节点。为了方便说明问题，图中用x标出树根，并用a,b,c,d,e,f,g,h标出树根下面的一些相对位置（可以将这些位置看成nil，只是图中做了省略，没有画出current和brother到这些nil的完整路径）。所有调整的目标都是保证，如果current子树的黑高降1，那么通过调整，保证x到a,b,c,d,e,f,g,h这些位置的相对黑高不变。
对于1.1，如果current子树黑高降1，那么将parent左旋，则x到a,b,c,d的相对黑高保持不变
对于1.2，如果current子树黑高降1，那么将brother右旋，并将parent变黑色和左旋，即保证x到a,b,c,d,e的相对黑高保持不变
对于2.1，如果current子树黑高降1，那么将brother与left换色，然后parent左旋，即保证x到a,b,c,d,e,f的相对黑高保持不变
对于2.2，如果current子树黑高降1，那么将left的右子节点涂成黑色，然后brother右旋，parent左旋，即可以保证x到a,b,c,e,f,g,h的相对黑高保持不变
对于2.3，如果current子树黑高降1，那么将left左子节点涂成黑色，并将left右旋，这样将情形转化成2.2
对于3.1，如果current子树黑高降1，那么依然只能降低brother的黑高，使x到a,b,c,d,e,f的相对黑高同时降1，然后将parent视为新的current子树继续向树根追溯
对于3.2，如果current子树黑高降1，那么将right涂成黑色，然后parent左旋，即可以保证x到a,b,c,e,f的相对黑高保持不变
对于3.3，如果current子树黑高降1，那么将left涂成黑色，然后brother右旋，parent左旋，即保证x到a,b,c,e,f的相对黑高保持不变
https://github.com/shanhm1991/Echo/blob/master/src/main/java/io/github/echo/structure/tree/RBTreeSet.java1
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
134
135
136
137
138
139
140
141
| public boolean remove(Object o) {
E e = (E)o;
nil.element = e;
RBNode<E> parent = header;
RBNode<E> current = header;
while(compare(e, current) != 0){
parent = current;
if(compare(e, current) < 0){
current = getLeft(current);
}else{
current = getRight(current);
}
}
if(current == nil){
return true;
}
size--;
RBNode<E> node = current;
if(current.right != nil){
parent = current;
current = getRight(current);
while(current.left != nil){
parent = current;
current = getLeft(current);
}
node.element = current.element;
if(current.right != nil){
parent = current;
current = getRight(current);
parent.element = current.element;
parent.right = nil;
return true;
}
}else if(current.left != nil){
parent = current;
current = getLeft(node);
while(current.right != nil){
parent = current;
current = getRight(current);
}
node.element = current.element;
if(current.left != nil){
parent = current;
current = getLeft(current);
parent.element = current.element;
parent.left = nil;
return true;
}
}
if(!current.red){
fixRemove(current);
}
if(current == parent.left){
parent.left = nil;
}else{
parent.right = nil;
}
return true;
}
private void fixRemove(RBNode<E> current){
RBNode<E> parent = current.parent;
if(parent == header){
return;
}
if(current == parent.left){
RBNode<E> brother = getRight(parent);
if(parent.red){
if(getLeft(brother).red){
parent.red = false;
rotateRight(brother);
}
}else if(brother.red){
if(!getLeft(brother.left).red && !getRight(brother.left).red){
brother.red = false;
getLeft(brother).red = true;
}else if(getRight(brother.left).red){
getRight(brother.left).red = false;
rotateRight(brother);
}else{
getLeft(brother.left).red = false;
rotateRight(getLeft(brother));
rotateRight(brother);
}
}else{
if(!getLeft(brother).red && !getRight(brother).red){
brother.red = true;
fixRemove(parent);
return;
}else if(getRight(brother).red){
getRight(brother).red = false;
}else{
getLeft(brother).red = false;
rotateRight(brother);
}
}
rotateLeft(parent);
}else{
RBNode<E> brother = getLeft(parent);
if(parent.red){
if(getRight(brother).red){
parent.red = false;
rotateLeft(brother);
}
}else if(brother.red){
if(!getLeft(brother.right).red && !getRight(brother.right).red){
brother.red = false;
getRight(brother).red = true;
}else if(getLeft(brother.right).red){
getLeft(brother.right).red = false;
rotateLeft(brother);
}else{
getRight(brother.right).red = false;
rotateLeft(getRight(brother));
rotateLeft(brother);
}
}else{
if(!getLeft(brother).red && !getRight(brother).red){
brother.red = true;
fixRemove(parent);
return;
}else if(getLeft(brother).red){
getLeft(brother).red = false;
}else{
getRight(brother).red = false;
rotateLeft(brother);
}
}
rotateRight(parent);
}
}
|
总结节点删除问题：首先将问题转化为对树叶的删除，如果树叶是红色则直接删除，如果是黑色，则根据兄弟节点和父节点的颜色情况来对情形进行分类。想法是尽量在子树中解决，如果实在解决不了，就降低子树的高度，并将子树视为整体然后向树根进行追溯，直到问题解决。上面的分析中，对于删除黑色树叶的删除，分成了8种情形，其中3.1需要向树根追溯，直到转化成其它7种情形或到树根为止才能解决。另外2.3也可以转化成2.2解决，因此，对于黑色树叶的删除，实际上最后直接解决的情形可以归结有6种。
2. MultiTreeMap
继续之前的MultiBinaryTreeMap，实现一个可以处理重复key的TreeMap
https://github.com/shanhm1991/Echo/blob/master/src/main/java/io/github/echo/structure/tree/RBTreeMultiMap.java1
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
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
| public class RBTreeMultiMap<K extends Comparable<? super K>, V> extends MultiBinaryTreeMap<K, V> {
public RBTreeMultiMap() {
}
public RBTreeMultiMap(boolean deduplication, boolean asc){
super(deduplication, asc);
}
@Override
protected void init() {
nil = new RBNode<K, V>(null, null, false, null, null);
nil.left = nil;
nil.right = nil;
header = new RBNode<K, V>(null, null, false, nil, nil);
header.next = nil;
nil.prev = header;
}
public V put(K key, V value){
nil.key = key;
RBNode<K, V> current = (RBNode<K, V>)header;
RBNode<K, V> parent = (RBNode<K, V>)header;
while(compare(key, current) != 0){
parent = current;
if(compare(key, current) < 0){
current = getLeft(current);
}else{
current = getRight(current);
}
if(getLeft(current).isRed && getRight(current).isRed){
current = handleReorient(current);
}
}
if(current != nil){
if(deduplication){
V old = current.value;
current.key = key;
current.value = value;
return old;
}else{
while((current = getNext(current)).isRepeat);
V old = current.prev.value;
linkIn(new RBNode<>(key, value, true, nil, nil), current, false);
return old;
}
}
current = new RBNode<>(key, value, false, nil, nil);
current.parent = parent;
if(compare(key, parent) < 0){
parent.left = current;
linkIn(current, parent, false);
}else{
parent.right = current;
while((parent = getNext(parent)).isRepeat);
linkIn(current, parent, false);
}
handleReorient(current);
return null;
}
private RBNode<K, V> handleReorient(RBNode<K, V> current) {
getLeft(current).isRed = false;
getRight(current).isRed = false;
current.isRed = true;
RBNode<K, V> subRoot = current;
RBNode<K, V> parent = getParent(current);
if(parent.isRed){
RBNode<K, V> grand = getParent(parent);
grand.isRed = true;
if(compare(current.getKey(), grand) != compare(current.getKey(), parent)) {
if(compare(current.getKey(), parent) > 0){
rotateLeft(parent);
}else{
rotateRight(parent);
}
}
if(compare(current.getKey(), grand) < 0){
subRoot = getLeft(grand);
subRoot.isRed = false;
rotateRight(grand);
}else{
subRoot = getRight(grand);
subRoot.isRed = false;
rotateLeft(grand);
}
}
getRight(header).isRed = false;
return subRoot;
}
private void rotateRight(Node<K, V> node) {
Node<K, V> parent = node.parent;
Node<K, V> left = node.left;
Node<K, V> leftRight = left.right;
left.right = node;
node.parent = left;
node.left = leftRight;
leftRight.parent = node;
left.parent = parent;
if(parent.right == node){
parent.right = left;
}else{
parent.left = left;
}
}
private void rotateLeft(Node<K, V> node) {
Node<K, V> parent = node.parent;
Node<K, V> right = node.right;
Node<K, V> rightLeft = right.left;
right.left = node;
node.parent = right;
node.right = rightLeft;
rightLeft.parent = node;
right.parent = parent;
if(parent.right == node){
parent.right = right;
}else{
parent.left = right;
}
}
private int compare(K key, Entry<K, V> node) {
if(node == header){
return 1;
}else{
return key.compareTo(node.getKey());
}
}
private RBNode<K, V> getParent(Node<K, V> node){
return (RBNode<K, V>)node.parent;
}
private RBNode<K, V> getNext(Node<K, V> node){
return (RBNode<K, V>)node.next;
}
private RBNode<K, V> getLeft(Node<K, V> node){
return (RBNode<K, V>)node.left;
}
private RBNode<K, V> getRight(Node<K, V> node){
return (RBNode<K, V>)node.right;
}
@Override
protected void remove(Node<K, V> node){
RBNode<K, V> rbnode = (RBNode<K, V>)node;
RBNode<K, V> current = rbnode;
RBNode<K, V> parent = getParent(current);
if(current.right != nil){
current = getRight(current);
while(current.left != nil){
parent = current;
current = getLeft(current);
}
locationExchange(rbnode, current);
if(rbnode.right != nil){
parent = rbnode;
rbnode = getRight(rbnode);
locationExchange(parent, rbnode);
rbnode.right = nil;
return;
}
}else if(current.left != nil){
current = getLeft(current);
while(current.right != nil){
parent = current;
current = getRight(current);
}
locationExchange(rbnode, current);
if(rbnode.left != nil){
parent = rbnode;
rbnode = getLeft(rbnode);
locationExchange(parent, rbnode);
rbnode.left = nil;
return;
}
}
if(!rbnode.isRed){
fixRemove(rbnode);
}else if(rbnode == parent.left){
parent.left = nil;
}else{
parent.right = nil;
}
}
private void locationExchange(RBNode<K, V> node, RBNode<K, V> current){
RBNode<K, V> parent = getParent(node);
RBNode<K, V> left = getLeft(node);
RBNode<K, V> right = getRight(node);
boolean isRed = node.isRed;
replaceChild(current.parent, current, node);
node.left = current.left;
node.left.parent = node;
node.right = current.right;
node.right.parent = node;
node.isRed = current.isRed;
replaceChild(parent, node, current);
current.left = left;
left.parent = current;
current.right = right;
right.parent = current;
current.isRed = isRed;
}
private void fixRemove(RBNode<K, V> node){
RBNode<K, V> parent = getParent(node);
if(parent == header){
return;
}
if(node == parent.left){
parent.left = nil;
RBNode<K, V> brother = getRight(parent);
if(parent.isRed){
if(getLeft(brother).isRed){
parent.isRed = false;
rotateRight(brother);
}
}else if(brother.isRed){
if(!getLeft(brother.left).isRed && !getRight(brother.left).isRed){
brother.isRed = false;
getLeft(brother).isRed = true;
}else if(getRight(brother.left).isRed){
getRight(brother.left).isRed = false;
rotateRight(brother);
}else{
getLeft(brother.left).isRed = false;
rotateRight(brother.left);
rotateRight(brother);
}
}else{
if(!getLeft(brother).isRed && !getRight(brother).isRed){
brother.isRed = true;
fixRemove(parent);
return;
}else if(getRight(brother).isRed){
getRight(brother).isRed = false;
}else{
getLeft(brother).isRed = false;
rotateRight(brother);
}
}
rotateLeft(parent);
}else{
parent.right = nil;
RBNode<K, V> brother = getLeft(parent);
if(parent.isRed){
if(getRight(brother).isRed){
parent.isRed = false;
rotateLeft(brother);
}
}else if(brother.isRed){
if(!getLeft(brother.right).isRed && !getRight(brother.right).isRed){
brother.isRed = false;
getRight(brother).isRed = true;
}else if(getLeft(brother.right).isRed){
getLeft(brother.right).isRed = false;
rotateLeft(brother);
}else{
getRight(brother.right).isRed = false;
rotateLeft(brother.right);
rotateLeft(brother);
}
}else{
if(!getLeft(brother).isRed && !getRight(brother).isRed){
brother.isRed = true;
fixRemove(parent);
return;
}else if(getLeft(brother).isRed){
getLeft(brother).isRed = false;
}else{
getRight(brother).isRed = false;
rotateLeft(brother);
}
}
rotateRight(parent);
}
}
static class RBNode<K, V> extends Node<K, V> {
boolean isRed;
public RBNode(K key, V value) {
super(key, value);
}
RBNode(K key, V value, boolean isRepeat, Node<K, V> left, Node<K, V> right) {
super(key, value, isRepeat, left, right);
}
@Override
public String toString() {
String str = super.toString();
return isRed ? str + "(red)" : str;
}
}
}
|
3. 红黑树的高度
根据规则4，任意节点到其下面各个空节点的黑高相等。那么，记根为x的红黑树的黑高为 $H$，那么红黑树中至少包含 $2^H - 1$ 个黑色节点。
根据规则3，在高度为 $H$ 的红黑树中，任何一条路径至多有一半的红色节点，即至少有一半的黑色节点，也就是说黑高至少为 $H/2$。
那么，如果红黑树的节点数为 $N$，则有：$N \geq 2^{H/2} - 1$，即 $H <= 2\log_{2} {(n+1)}$
如果与Avl树比较，显然Avl的平衡性更好，因此搜索效率也更高一些，但是为了达到更高的平衡性，其在插入删除所需要付出的开销也就更高。如果就单次调整而言，最多也只需要4次旋转即可恢复平衡，但是定位到旋转节点的这个过程就要看运气了，如果刚好根节点的左右子树不平衡，那么则需要从树叶节点逐层检查到根节点 ，当树的高度或节点数达到一定规模后，这个概率还是比较高的，而红黑树的调整则绝大部分情况下都可以在当前节点所在的子树中完成。
参考：
- 《算法导论》
- 《数据结构与算法分析》