logo头像

待到风起时,扬帆济沧海

红黑树

红-黑树的概念

上一篇二叉搜索树,二叉搜索树对于某个节点而言,其左子树的节点关键值都小于该节点关键值,右子树的所有节点关键值都大于该节点关键值。二叉搜索树作为一种数据结构,其查找、插入和删除操作的时间复杂度都为O(logn),底数为2。但是我们说这个时间复杂度是在平衡的二叉搜索树上体现的,也就是如果插入的数据是随机的,则效率很高,但是如果插入的数据是有序的,比如从小到大的顺序【10,20,30,40,50】插入到二叉搜索树中:

从大到小就是全部在左边,这和链表没有任何区别了,这种情况下查找的时间复杂度为O(N),而不是O(logN)。当然这是在最不平衡的条件下,实际情况下,二叉搜索树的效率应该在O(N)和O(logN)之间,这取决于树的不平衡程度。

那么为了能够以较快的时间O(logN)来搜索一棵树,我们需要保证树总是平衡的(或者大部分是平衡的),也就是说每个节点的左子树节点个数和右子树节点个数尽量相等。红-黑树的就是这样的一棵平衡树,对一个要插入的数据项(删除也是),插入例程要检查会不会破坏树的特征,如果破坏了,程序就会进行纠正,根据需要改变树的结构,从而保持树的平衡。

红黑树的特征和规则

  • 节点都有颜色:在红-黑树中,每个节点的颜色或者是黑色或者是红色的。当然也可以是任意别的两种颜色,这里的颜色用于标记,我们可以在节点类Node中增加一个boolean型变量isRed,以此来表示颜色的信息。
  • 在插入和删除的过程中,要遵循保持这些颜色的不同排列规则。规则如下:
    1. 每个节点不是红色就是黑色;
    2. 根节点总是黑色;
    3. 每个叶子节点都是黑色的空节点(叶子是NIL节点,在红黑树中一般用黑的NIL节点表示叶节点,不包含值,只是标志该分支结束,有时候绘图中会直接省略。);
    4. 每个红色节点的两个子节点都是黑色。(从每个叶子到根节点的所有路径上不能有两个连续的红色节点)
    5. 从任一节点到其叶子节点的所有路径上都包含相同数目的黑节点。

前四都能理解其意思吧,所以只解释下第五点,比如60这个节点,到其所有叶子节点的路径都只包含1个黑色节点:40和90。

红-黑树的3种自我修正(改变节点颜色、左旋和右旋)

改变节点颜色

新插入的节点为15,一般新插入颜色都为红色,那么我们发现直接插入会违反规则3,改为黑色却发现违反规则4。这时候我们将其父节点颜色改为黑色,父节点的兄弟节点颜色也改为黑色。通常其祖父节点50颜色会由黑色变为红色,但是由于50是根节点,所以我们这里不能改变根节点颜色。

右旋

首先要说明的是节点本身是不会旋转的,旋转改变的是节点之间的关系,选择一个节点作为旋转的顶端,如果做一次右旋,这个顶端节点会向下和向右移动到它右子节点的位置,它的左子节点会上移到它原来的位置。右旋的顶端节点必须要有左子节点。

以图中红色节点为中心,中心节点为右子节点替代,而自己成为它的左子节点,同时节点b作为pivot的有子节点(至于为什么是右子节点,b原本就在pivot的右子树上,所以肯定大于pivot).

左旋

同左旋转,中心点顺时钟旋转,成为其原来左子节点的右子节点,原来左子节点的右子节点则成为原中心点的左子节点。

红黑树的插入

情况1:空树

直接插入,直接作为根节点,同时由于性质1的约束,通过变色op变为黑色即可。

情况2:插入节点父节为黑色

不违反任何性质,无需做任何修改。

情况3:插入节点的父节点为红色,父节点为父父节点的左孩子,父父节点的右孩子为黑色,插入节点为左孩子(或者父节点为父父节点的右孩子,父父节点的左孩子为黑色,插入节点为右孩子)。

这是一种插入节点和父节点在一个方向上的情况(例如父节点为左孩子,插入节点也为左孩子)和情形5相反

父节点 及 父父节点变色,再进行左/右旋转, 具体左还是右看你插入的节点的父节点是左子树还是右子树,图例为左子树。

此处 : 变色 - > 右旋转

情况4:插入节点父节点为红色,父父节点的左/右孩子为红色

先将父节点和父父节点右孩子变黑,父父节点变红,然后将父节点当做新插入的红色节点一样递归向上进行平衡红黑树性质操作。 若父节点为根节点直接变父节点为黑色即可.

此处 : 变色 -> 变色

情况5:插入节点的父节点为红色,父节点为父父节点的左孩子,父父节点的右孩子为黑色,插入节点为右孩子(或者父节点为父父节点的右孩子,父父节点的左孩子为黑色,插入节点为左孩子)

和情形3类比是一种反向情况,这种情况进行两次旋转,
先左/右旋转,旋转后变成了情形3,接着按情形3变换即可。

此处 :左旋转 -> 变色 -> 右旋转

总结

完整源码

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
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
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
package tree

import "fmt"

type RBNode struct {
Color bool //颜色
Value int //数据
Parent *RBNode //父节点
Left *RBNode //左子节点
Right *RBNode //右子节点
}

const (
// RED 红树设为true
RED = true
// BLACK 黑树设为false
BLACK = false
)

type RBtree struct {
Root *RBNode
}

/**
循环查找
*/
func (this *RBtree) Find(data int) *RBNode {
current := this.Root
for current != nil {
if data == current.Value {
return current
}
if data < current.Value {
current = current.Left
} else {
current = current.Right
}
}
return nil
}

/**
递归查找
*/
func (this *RBtree) Search(current *RBNode, data int) *RBNode {
if current == nil {
return current
}
if current.Value > data {
this.Search(current.Left, data)
} else if current.Value < data {
this.Search(current.Right, data)
} else {
return current
}
return nil
}

/**
前序遍历
*/
func (this *RBtree) PreOrder(current *RBNode) {
if current != nil {
fmt.Printf("%d,", current.Value)
this.PreOrder(current.Left)
this.PreOrder(current.Right)
}
}

/**
查找最小节点
*/
func (this *RBtree) FindMin(current *RBNode) *RBNode {
if current == nil {
return nil
}
for current.Left != nil {
current = current.Left
}
return current
}

/**
查找最小节点
*/
func (this *RBtree) FindMax(current *RBNode) *RBNode {
if current == nil {
return nil
}
for current.Right != nil {
current = current.Right
}
return current
}

/*
找结点(x)的后继结点。即,查找"红黑树中数据值大于该结点"的"最小结点"。
*/
func (this *RBtree) successor(x *RBNode) *RBNode {
// 如果x存在右孩子,则"x的后继结点"为 "以其右孩子为根的子树的最小结点"。
if x.Right != nil {
return this.FindMin(x.Right)
}
// 如果x没有右孩子。则x有以下两种可能:
// (01) x是"一个左孩子",则"x的后继结点"为 "它的父结点"。
// (02) x是"一个右孩子",则查找"x的最低的父结点,并且该父结点要具有左孩子",找到的这个"最低的父结点"就是"x的后继结点"。
y := x.Parent
for y != nil && x == y.Right {
x = y
y = y.Parent
}
return y
}

/*
* 找结点(x)的前驱结点。即,查找"红黑树中数据值小于该结点"的"最大结点"。
*/
func (this *RBtree) predecessor(x *RBNode) *RBNode {
// 如果x存在左孩子,则"x的前驱结点"为 "以其左孩子为根的子树的最大结点"。
if x.Left != nil {
return this.FindMax(x.Left)
}
// 如果x没有左孩子。则x有以下两种可能:
// (01) x是"一个右孩子",则"x的前驱结点"为 "它的父结点"。
// (01) x是"一个左孩子",则查找"x的最低的父结点,并且该父结点要具有右孩子",找到的这个"最低的父结点"就是"x的前驱结点"。
y := x.Parent
for y != nil && x == y.Left {
x = y
y = y.Parent
}
return y
}

/*************对红黑树节点x进行左旋操作 ******************/
/*
* 对红黑树的节点(x)进行左旋转
*
* 左旋示意图(对节点x进行左旋):
* px px
* / /
* x y
* / \ --(左旋)-. / \ #
* lx y x ry
* / \ / \
* ly ry lx ly
* 左旋做了三件事:
* 1. 将y的左子节点赋给x的右子节点,并将x赋给y左子节点的父节点(y左子节点非空时)
* 2. 将x的父节点p(非空时)赋给y的父节点,同时更新p的子节点为y(左或右)
* 3. 将y的左子节点设为x,将x的父节点设为y
https://www.cnblogs.com/skywang12345/p/3624343.html#a3
*/
func (this *RBtree) LeftRotate(x *RBNode) {
if x.Right == nil {
return
}
// 设置x的右孩子为y
y := x.Right
// 将 “y的左孩子” 设为 “x的右孩子”;
// 如果y的左孩子非空,将 “x” 设为 “y的左孩子的父亲”
x.Right = y.Left
if y.Left != nil {
y.Left.Parent = x
}
// 将 “x的父亲” 设为 “y的父亲”
y.Parent = x.Parent

if x.Parent == nil {
this.Root = y // 如果 “x的父亲” 是空节点,则将y设为根节点
} else {
if x == x.Parent.Left { //如果x是左子节点
x.Parent.Left = y // 如果 x是它父节点的左孩子,则将y设为“x的父节点的左孩子”
} else {
x.Parent.Right = y // 如果 x是它父节点的左孩子,则将y设为“x的父节点的左孩子”
}
}
// 将 “x” 设为 “y的左孩子”
y.Left = x
// 将 “x的父节点” 设为 “y”
x.Parent = y
}

/*************对红黑树节点y进行右旋操作 ******************/
/*
* 右旋示意图:对节点y进行右旋
* p p
* / /
* y x
* / \ / \
* x ry -----> lx y
* / \ / \
* lx rx rx ry
* 右旋做了三件事:
* 1. 将x的右子节点赋给y的左子节点,并将y赋给x右子节点的父节点(x右子节点非空时)
* 2. 将y的父节点p(非空时)赋给x的父节点,同时更新p的子节点为x(左或右)
* 3. 将x的右子节点设为y,将y的父节点设为x
*/
func (this *RBtree) RightRotate(y *RBNode) {
// 设置x是当前节点的左孩子。
x := y.Left
// 将 “x的右孩子” 设为 “y的左孩子”;
// 如果"x的右孩子"不为空的话,将 “y” 设为 “x的右孩子的父亲”
y.Left = x.Right
if x.Right != nil {
x.Right.Parent = y
}
// 将 “y的父亲” 设为 “x的父亲”
x.Parent = y.Parent
if y.Parent == nil {
this.Root = x // 如果 “y的父亲” 是空节点,则将x设为根节点
} else {
if y == y.Parent.Left { //如果y是左子节点
y.Parent.Left = x // 如果 y是它父节点的右孩子,则将x设为“y的父节点的右孩子”
} else {
y.Parent.Right = x // (y是它父节点的左孩子) 将x设为“x的父节点的左孩子”
}
}
// 将 “y” 设为 “x的右孩子”
x.Right = y
// 将 “y的父节点” 设为 “x”
y.Parent = x
}

/**
节点插入
*/
func (this *RBtree) Insert(data int) {
var y *RBNode
x := this.Root
addNode := &RBNode{Color: BLACK, Value: data}
for x != nil {
y = x
if data < x.Value {
x = x.Left
} else {
x = x.Right
}
}
addNode.Parent = y
if y != nil {
if data < y.Value {
y.Left = addNode
} else {
y.Right = addNode
}
} else {
this.Root = addNode
}
// 2. 设置节点的颜色为红色
addNode.Color = RED
// 3. 将它重新修正为一颗二叉查找树
this.InsertFixUp(addNode)
}

/**
红黑树修正
*/
func (this *RBtree) InsertFixUp(node *RBNode) {
var parent *RBNode
var gparent *RBNode
// 若“父节点存在,并且父节点的颜色是红色”
for parent = node.Parent; parent != nil && parent.Color == RED; {
gparent = parent.Parent
if parent == gparent.Left { //若“父节点”是“祖父节点的左孩子”
// Case 1条件:叔叔节点是红色
uncle := gparent.Right
if uncle != nil && uncle.Color == RED {
uncle.Color = BLACK
parent.Color = BLACK
gparent.Color = RED
node = gparent
continue
}
// Case 2条件:叔叔是黑色,且当前节点是右孩子
if parent.Right == node {
var tmp *RBNode
this.LeftRotate(parent)
tmp = parent
parent = node
node = tmp
}
// Case 3条件:叔叔是黑色,且当前节点是左孩子。
parent.Color = BLACK
gparent.Color = RED
this.RightRotate(gparent)
} else { //若“z的父节点”是“z的祖父节点的右孩子”
// Case 1条件:叔叔节点是红色
uncle := gparent.Left
if uncle != nil && uncle.Color == RED {
uncle.Color = BLACK
parent.Color = BLACK
gparent.Color = RED
node = gparent
continue
}
// Case 2条件:叔叔是黑色,且当前节点是左孩子
if parent.Left == node {
var tmp *RBNode
this.RightRotate(parent)
tmp = parent
parent = node
node = tmp
}
// Case 3条件:叔叔是黑色,且当前节点是右孩子。
parent.Color = BLACK
gparent.Color = RED
this.LeftRotate(gparent)
}
}
// 将根节点设为黑色
this.Root.Color = BLACK
}

func (this *RBtree) Delete(data int) bool {
//要删除的节点
node := this.Search(this.Root, data)
if node == nil {
return false
}
var child, parent *RBNode
var color bool
// 被删除节点的"左右孩子都不为空"的情况。
if node.Left != nil && node.Right != nil {
// 被删节点的后继节点。(称为"取代节点") 用它来取代"被删节点"的位置,然后再将"被删节点"去掉。
replace := node
//获取后继节点
replace = replace.Right
for replace.Left != nil {
replace = replace.Left
}
// "node节点"不是根节点(只有根节点不存在父节点)
if node.Parent != nil {
if node.Parent.Left == node {
node.Parent.Left = replace
} else {
node.Parent.Right = replace
}
} else {
// "node节点"是根节点,更新根节点。
this.Root = replace
}
// child是"取代节点"的右孩子,也是需要"调整的节点"。"取代节点"肯定不存在左孩子!因为它是一个后继节点。
child = replace.Right
parent = replace.Parent
color = replace.Color
// "被删除节点"是"它的后继节点的父节点"
if parent == node {
parent = replace
} else {
if child != nil {
child.Parent = parent
}
parent.Left = child
replace.Right = node.Right
node.Right.Parent = replace
}
replace.Parent = node.Parent
replace.Color = node.Color
replace.Left = node.Left
node.Left.Parent = replace
if color == BLACK {
this.deleteFix(child, parent)
}
node = nil
return true
}
if node.Left != nil {
child = node.Left
} else {
child = node.Right
}
parent = node.Parent
color = node.Color
if child != nil {
child.Parent = parent
}
//"node节点"不是根节点
if parent != nil {
if parent.Left == node {
parent.Left = child
} else {
parent.Right = child
}
} else {
this.Root = child
}
if color == BLACK {
this.deleteFix(child, parent)
}
node = nil
return true

}

/*
* 红黑树删除修正函数
*
* 在从红黑树中删除插入节点之后(红黑树失去平衡),再调用该函数;
* 目的是将它重新塑造成一颗红黑树。
*
* 参数说明:
* node 待修正的节点
*/
func (this *RBtree) deleteFix(node *RBNode, parent *RBNode) {
var other *RBNode
for (node == nil || node.Color == BLACK) && node != this.Root {
if parent.Left == node {
other = parent.Right
if other.Color == RED {
// Case 1: x的兄弟w是红色的
other.Color = BLACK
parent.Color = RED
this.LeftRotate(parent)
other = parent.Right
}
if (other.Left == nil || other.Left.Color == BLACK) && (other.Right == nil || other.Right.Color == BLACK) {
// Case 2: x的兄弟w是黑色,且w的俩个孩子也都是黑色的
other.Color = RED
node = parent
parent = node.Parent
} else {
if other.Right == nil && other.Right.Color == BLACK {
// Case 3: x的兄弟w是黑色的,并且w的左孩子是红色,右孩子为黑色。
other.Left.Color = BLACK
other.Color = RED
this.RightRotate(other)
other = parent.Right
}
// Case 4: x的兄弟w是黑色的;并且w的右孩子是红色的,左孩子任意颜色。
other.Color = parent.Color
parent.Color = BLACK
other.Right.Color = BLACK
this.LeftRotate(parent)
node = this.Root
break
}

} else {
other = parent.Left
if other.Color == RED {
// Case 1: x的兄弟w是红色的
other.Color = BLACK
parent.Color = RED
this.RightRotate(parent)
other = parent.Left
}
if (other.Left == nil || other.Left.Color == BLACK) && (other.Right == nil || other.Right.Color == BLACK) {
// Case 2: x的兄弟w是黑色,且w的俩个孩子也都是黑色的
other.Color = RED
node = parent
parent = node.Parent
} else {
if other.Left == nil || other.Left.Color == BLACK {
// Case 3: x的兄弟w是黑色的,并且w的左孩子是红色,右孩子为黑色。
other.Right.Color = BLACK
other.Color = RED
this.LeftRotate(other)
other = parent.Left
}
// Case 4: x的兄弟w是黑色的;并且w的右孩子是红色的,左孩子任意颜色。
other.Color = parent.Color
parent.Color = BLACK
other.Left.Color = BLACK
this.RightRotate(parent)
node = this.Root
break
}

} //===if-else end
} // for end
if node != nil {
node.Color = BLACK
}
}

func (this *RBtree) Print() {
if this.Root == nil {
fmt.Println("RBTree is empty")
return
}
this.printTree(this.Root, this.Root.Value, 0)

}

/*
* 打印"红黑树"
*
* key -- 节点的键值
* direction -- 0,表示该节点是根节点;
* -1,表示该节点是它的父结点的左孩子;
* 1,表示该节点是它的父结点的右孩子。
*/
func (this *RBtree) printTree(tree *RBNode, data int, direction int) {
if tree != nil {
if direction == 0 { // tree是根节点
fmt.Printf("%2d(B) is root\n", tree.Value)
} else {
var color, post string
if tree.Color == RED {
color = "R"
} else {
color = "B"
}
if direction == 1 {
post = "right"
} else {
post = "left"
}
fmt.Printf("%2d(%s) is %2d's %6s child\n", tree.Value, color, data, post)
}
this.printTree(tree.Left, tree.Value, -1)
this.printTree(tree.Right, tree.Value, 1)
}
}

评论系统未开启,无法评论!