DomBro Studio

AVL树和红黑树

2018/03/26

平衡树

标题中的AVL树和红黑树都是二叉查找树,二叉查找树不熟的可以看一下这篇博客
二叉搜索树的出现是为了解决线性访问时间太慢的问题,平均访问时间为O(logN)。但如果二叉搜索树以顺序的元素插入如 1,2,3,4,5,6 不难想象此时二叉树又会变成一个链式的线性结构,导致访问效率变慢。这是一个极端的例子,怎么破?

就引出了平衡树的概念,平衡树就是带有平衡条件的二叉查找树。根据平衡树的平衡条件,可以在树插入元素后如果树不符合平衡条件,则对树进行一个调整使树重新平衡。AVL树和红黑树(redblackTree)都是平衡树。

为什么要平衡

上面已经说出来了,平衡就是为了要保证树的 O(logN) 的访问速度。即,任何节点的深度不会过深。

AVL树

AVL树是带有平衡条件的二叉查找树。AVL树是最古老的平衡树。他保证树的深度必须是O(logN)。

AVL树平衡条件

一颗AVL树是其 每个节点的左子树和右子树的高度最多差1 的二叉查找树。(空树高度定义为-1)。

AVL树并不值得注意的是AVL树并不是在根节点处平衡的,如下图只是一颗坏的二叉树。

树的旋转

再进行插入操作时,我们需要更新通向根节点路径上哪些节点的所有平衡信息,而插入操作的隐含的困难在于,插入一个节点可能破坏AVL树的特性,变得不再平衡。例如,上方右侧非AVL树中,插入7后树变的不再平衡。事实上,这总可以通过对树进行简单修正来做到,我们称其为旋转。

再插入完成后,只有那些从插入点到根节的路径上的节点的平衡可能被改变,因为只有这些节点的子树发生变化。——《Java数据结构》

现在我们约定把出现不平衡的节点叫做α,由于任意节点最多有两个儿子,因此出现高度不平就需要α点的两颗子树高度差是2。容易看出,这种你不平衡可能出现在下面四种情况中。

  • 1.对α的左儿子的左子树进行一次插入,我们叫他左-左情况
  • 2.对α的左儿子的右子树进行一次插入,我们叫他左-右情况
  • 3.对α的右儿子的左子树进行一次插入,我们叫他右-左情况
  • 4.对α的右儿子的右子树进行一次插入,我们叫他右-右情况

四种情况中 1和4是对称的镜像情况,2和3是对称的镜像情况。

单旋转

第一种情况是插入发生在外边的情况(即左-左情况或左-右情况),遇到该情况通过对树的单旋转(即一次旋转使树平衡)完成调整。下面是发挥你想象例的时刻

如图分别演示了左-左和右-右单旋转过程,实际上旋转要做的无非就是把高的子树向上提一层,闭上双眼想一下这个动作,找到非平衡节点K2向较低的子树那一边用力下拉,这时K3就会被拽上来,而K3的较低子树也应该成为K2的左/右子树以满足二叉树的条件。我们 按照旋转的方向,左-左情况的旋转叫做右旋转,右-右情况的旋转叫做左旋转

#### 双旋转

下面说说比较麻烦的双旋转,双旋转的使用场景是左-右情况或右-左情况,顾名思义他需要转两下。

来看一种情况,下图属于左-右情况(右-左情况也一样),在K2处右旋转,显然树并未平衡。这是由于左旋和右旋只会将边上的子树上提。

和单旋转一样,我们的想办法把最高的子树向上提。上图中显然不能把K2当做根了,而把K3当做根有解决不了问题,那我们就只有把K1当做根,要想把K1当做根,可以预见K1就要是K3的父节点,这样K1就可以轻松的右旋。来试一下

看到了吧,所谓的双旋转就是两个单旋转组成的,它的过程是找到不平衡节点的内侧儿子,以内侧儿子节点为支点单旋转(方向右-左视情况和左-右情况而定),旋转后再以该不平衡节点为支点进行单旋转。总之你要记住的是,我们的目的是把树变得平衡呀!

调整的时机

说完旋转以后,AVL树的精髓部分已经说完了,实际上所说的旋转就是对平衡树的调整。可以研究一AVL树的调整时机。事实上你会发现在每次insert后都要调整(一个很重要的特点),原因就是上面引用《Java数据结构》的那句话,每次插入都有可能改变树的平衡性,所以AVL树的插入方法比二叉查找树在最后要多一个balance平衡方法。那删除一个节点呢?由于二叉树查找的删除本身就是一个比插入复杂的事(要考虑三种情况),删除一个节点有可能会引起树得不平衡,你可能会担心。实际上,为保证删除一个节点后AVL树依旧平衡,在二叉查找树的删除方法最后加上平衡函数是可行的!因为我们的平衡函数是从根节点开始判断的,也就是站在整颗AVL树的平衡性!

AVL节点

由于AVL树需要比较子树之间的高度,所以AVL节点会有一个记录节点高度的height域,空节点的高度是-1,父节点的高度是较高儿子节点高度加一。

代码

在代码中我们会计算节点子树的高度差,这个高度差不能大于一,若大于一就需要调整平衡。

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
/**
* AVL树的简单实现
*/
public class BinaryAvlTree<AnyType extends Comparable<? super AnyType>> {

//AVL节点
private static class AvlNode<AnyType>{

public AvlNode(AnyType element, AvlNode<AnyType> left, AvlNode<AnyType> right) {
this.element = element;
this.left = left;
this.right = right;
this.height = 0;
}

public AvlNode(AnyType element){
this(element,null,null);
}

AnyType element;
AvlNode<AnyType> left;
AvlNode<AnyType> right;
//节点的高度,默认初始化时根节点跟读为0
int height;
}

//根节点引用
public AvlNode<AnyType> root;
//平衡的高度差(指节点左右子树高度差)
private static final int ALLOWED_IMBALANCE = 1;

public BinaryAvlTree() {
root = null;
}

public AvlNode<AnyType> insert(AnyType x){
//插入从根节点插入
return insert(x,root);
}

//返回节点的高度
private int high(AvlNode<AnyType> t){
return (t == null) ? -1:t.height;
}

public AvlNode<AnyType> insert(AnyType x,AvlNode<AnyType> t){
//插入节点步骤
//1.首次插入从根节点插入
//2.插入后调用平衡函数
if (t == null){
t = new AvlNode<AnyType>(x);
}
//与根节点比较大小,若小递归从根节点左子树插入,若大递归从根节点右子树插入
int compareResult = x.compareTo(t.element);
if (compareResult < 0 ){
t.left = insert(x,t.left);
}else if (compareResult > 0){
t.right = insert(x,t.right);
}else{

}
//调用平衡函数
return balance(t);
}

//平衡方法
private AvlNode<AnyType> balance(AvlNode<AnyType> t) {
if (t == null){
return t;
}
if (high(t.left)-high(t.right) > ALLOWED_IMBALANCE){
//如果左子树高于右子树判断是左-左还是左-右 ;左-左 情况(向结点左儿子的左子树插入点使得树不平衡),进行左侧单旋转
if (high(t.left.left)>=high(t.left.right)){
t = rotateWithLeftChild(t);
}else {
//左-右 情况(向结点左儿子的右子树插入使得树不平衡),进行右侧单旋转
t = doubleWithLeftChild(t);
}
}
//下面代码判段右-左与右-右的情况,与上面代码属于镜像关系
else if (high(t.right)-high(t.left) > ALLOWED_IMBALANCE){
//右-右情况 进行右侧单旋转
if (high(t.right.right)>=high(t.right.left)){
t = rotateWithRightChild(t);
//右-左 情况进行右侧双旋转
}else {
t = doubleWithRightChild(t);
}
}
//t的高度为左右较高子树加一
t.height = Math.max(high(t.left),high(t.right))+1;
return t;
}
//右-左双旋转
private AvlNode<AnyType> doubleWithRightChild(AvlNode<AnyType> k3) {
//右侧双旋转与左侧双旋转城镜像关系
/**
* 右侧双旋转步骤;即右-左情况
* 1.对k3的右子节点做左侧单旋转操作,
* 2.在对k3节点做右侧单旋转
*/
rotateWithLeftChild(k3.right);
return rotateWithRightChild(k3);
}

//右-右单旋转
private AvlNode<AnyType> rotateWithRightChild(AvlNode<AnyType> k2) {
//与左侧单旋转是镜像关系
/**
* 1.k1为k2的右儿子节点,k1的左孩子作为k2的右孩子
* 2.k2作为k1的左孩子
*/
AvlNode<AnyType> k1 = k2.right;
k2.right = k1.left;
k1.left = k2;
k1.height = Math.max(k2.height,high(k1.right))+1;
k2.height = Math.max(high(k2.left),high(k2.right))+1;
return k1;
}

//左-右双旋转
private AvlNode<AnyType> doubleWithLeftChild(AvlNode<AnyType> k3) {
/**
* 左侧双旋转步骤:左侧双旋转是对应左-右情况的策略所以要先对左儿子的右子树进行右侧单旋转,在对该节点进行左侧单旋转
* 1.对k3节点左k1儿子的右子树右侧单旋转
* 2.对节点k3进行左侧单旋转
*/
rotateWithRightChild(k3.left);
return rotateWithLeftChild(k3);

}

//左-左单旋转
private AvlNode<AnyType> rotateWithLeftChild(AvlNode<AnyType> k2) {
/**
* 左侧单旋转步骤:k1不平衡节nk2的左孩子
* 1.将 k1的右孩子变为k2的左孩子
* 2.将节点k2变为其左k1的右孩子 即 k1 处在原不平衡节点的 k2 位置。
* 3.重新计算k1 k2 的高度
* 4.返回k1
*/
AvlNode<AnyType> k1 = k2.left;
k2.left = k1.right;
k1.right = k2;
k1.height = Math.max(high(k1.left),k2.height)+1;
k2.height = Math.max(high(k2.left),high(k2.right))+1;
return k1;
}

//删除操作
public AvlNode<AnyType> remove(AnyType x,AvlNode<AnyType> t){
if (t == null){
return t;
}
int compareResult = x.compareTo(t.element);
if (compareResult < 0){
t.left = remove(x,t.left);
}else if(compareResult > 0){
t.right = remove(x,t.right);
}else {
if (t.left != null && t.right != null){
t.element = findMin(t.right).element;
t.right = remove(t.element,t.right);
}else {
t = (t.left == null) ? t.left:t.right;
}
}
return balance(t);

}

/**
* 从根节点查找最小节点
* 由于二叉搜索树根节点左侧均比根节点小,
*
*/
private AvlNode<AnyType> findMin(AvlNode<AnyType> t){
if (t != null){
while (t.left != null){
t = t.left;
}
}
return t;
}

//与查找最小值类似
private AvlNode<AnyType> findMax(AvlNode<AnyType> t){
if (t != null){
while (t.right != null){
t = t.right;
}
}
return t;
}
}

总的来说AVL树可以有效的解决二叉查找树出现线性存储查找效率低的状况。那AVL树就没有缺点了吗?当然不是AVL树每次插入都需要再次平衡,我们用的还是递归…这就影响了AVL树插入的速率。

红黑树

上面说到AVL树频繁平衡操作的影响了插入速率。之所以频繁的平衡是因为AVL树的平衡条件太单一了,没啥内涵。这就引出了今天的第二主角红黑树。那么红黑树是什么树呢?红黑树是AVL树的流行变种,最坏的操作情形下花费O(logN)的时间,他的插入和删除速度都很快。

红黑树特点

红黑树是具有下列着色性质的二叉查找树(四规则):

  • 1.每一颗节点或者是红色,或者是黑色。
  • 2.根节点是黑色的。
  • 3.如果一个节点是红色的,他的子节点必须是黑色的。
  • 4.从一个节点到null引用的每一条路径必须包含相同数目的黑色节点。

着色法则的一个结论是,红黑树的高度最多是2log(N+1),因此保证查找操作是一种对树操作。

默认没有儿子的节点连接的都是null

插入节点

根据上面红黑树四规定,可以确定插入的节点颜色一定是红色。这不是偶然的,因为如果新插入节点是黑色在,那势必会违背规则四。但如果插入红色节点只有半几率违反规则三,就算违反了也更容易修改。但是就算是插入红色新节点也还是会有可能破坏平衡性的。

红黑树的节点

根据红黑树的着色特点,要有一个boolean值表示颜色。另外红黑树插入过程中需要获得其父亲节点进行颜色的判断,所以还要有一个父节点的引用。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
private static class RedBlackNode<AnyType>{
AnyType element;
RedBlackNode<AnyType> left;
RedBlackNode<AnyType> right;
RedBlackNode<AnyType> parent;
boolean color;

public RedBlackNode(AnyType element, RedBlackNode<AnyType> left,
RedBlackNode<AnyType> right,RedBlackNode<AnyType> parent,boolean color) {
this.element = element;
this.left = left;
this.right = right;
this.parent = parent;
this.color = color;
}
}

平衡性修正

红-黑树主要通过三种方式对平衡进行修正,改变节点颜色、左旋和右旋。这看起来有点抽象。其中左旋和右旋在AVL树的旋转小节已经解释过了,唯一的区别不是红黑树只靠着旋转就可以达到平衡的,其他原理都是一样的。

  • 变色

    变色其实也很好理解,由于违背了规则三,所以自然的就将节点颜色改变一下。比如插入节点的父节点也是红色,就将父节点的颜色变为黑色(当然情况可能会更加复杂一点)。

  • 旋转

上面说了左旋右旋的原理和AVL树中的旋转是一样的,只不过由于多了parent的引用。代码会有点变化。

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
//以t为支点右旋操作
private void rightRotate(RedBlackNode<AnyType> t) {
RedBlackNode<AnyType> leftNode = t.left;
t.left = leftNode.right;
if (leftNode.right != null){
leftNode.right.parent = t;
}

leftNode.parent = t.parent;
if (t.parent == null){
this.root = leftNode;
}else {
if (t == t.parent.right){
t.parent.right = leftNode;
}else {
t.parent.left = leftNode;

}
}
leftNode.right = t;
t.parent = leftNode;
}

//以t为支点左旋操作
private void leftRotate(RedBlackNode<AnyType> t) {
RedBlackNode<AnyType> rightNode = t.right;
t.right = rightNode.left;
if (rightNode.left != null){
rightNode.left.parent = t;
}
rightNode.parent = t.parent;
//如果 parent 没有父节点说明 parent 是根节点
if (t.parent == null){
this.root = rightNode;
}else {
//判断parent是左子树还是右子树
if (t == t.parent.left){
t.parent.left = rightNode;
}else {
t.parent.right = rightNode;
}
}

rightNode.left = t;
t.parent = rightNode;

}

节点的插入

和AVL树一样,再插入新结点后如果树出现了不平衡,还是要对树进行一个平衡调整。所谓修正也就是分情况讨论合适变色,何时左旋何时右旋。

如果是第一次插入,由于原树为空,只会违反规则二,所以只要把根节点涂黑即可;如果插入节点的父节点是黑色的,那不违反任何规则,什么也不做;但是若遇到下列三种情况,就一当要进行修正了:

1.插入节点的父节点何其叔叔节点均为红色
2.插入节点的父节点是红色,叔叔节点是黑色且插入节点是其父节点的右子节点
3.插入节点的父节点是红色,叔叔节点是黑色且插入节点是其父节点的左子节点

情况一:将当前节点的父节点和叔叔节点涂黑,将祖父节点涂红。将当新节点(即当前节点)指向其祖父节点。此时情况变为情况二(插入节点的父节点是红色,叔叔节点是黑色,且插入节点是父节点的左孩子)。

情况二:以当前节点的父节点作为新的节点,以新的节点作为支点做左旋操作。此时情况变为情况三(插入节点的父节点是红色,叔叔是黑色节点且插入节点是父节点右节点)。

情况三:将当前节点的父节点涂黑,将其祖父节点涂红,在祖父节点为支点左右旋操作。
最后把根节点涂黑,整个红黑树恢复平衡。

ps:这里的图我实在画不动了们可以看一下这个博主写的红黑树,很全面很细致是我见过总结最到位的,包教包会

下图是调整的流程图(自己画的)

  • 代码
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
//插入后重新调整为红黑树
private void insertFixUp(RedBlackNode<AnyType> t) {
//父节点,祖父节点
RedBlackNode<AnyType> parent ,grand;
//1.需要调整条件,父节点存在,且父节点颜色为红
while ((parent = getParent(t)) != null && parent.color == RED){
//获取祖父节点
grand = getParent(parent);
//2.如果父节点是祖父节点的左儿子
if (parent == grand.left){
//获取叔叔节点
RedBlackNode<AnyType> uncle = grand.right;
//情况一:叔叔节点也是红色
if(uncle != null && uncle.color == RED){
//将父节点和叔叔节点涂黑
parent.color = BLACK;
uncle.color = BLACK;
grand.color = RED;
//将当前节点位置放到祖父节点
t = grand;
continue;
}
//情况二:叔叔节点是黑色,且当前节点是右子节点
if (t == parent.right){
//从父节点处左旋
leftRotate(parent);
//以当前父节点和自己调换,作为新节点,为右旋做准备
RedBlackNode<AnyType> temp = parent;
parent = t;
t = temp;
}

//情况三:叔叔节点是黑色,且当前节点是左子节点
//将当前节点的父节点涂黑,将其祖父涂红
parent.color = BLACK;
grand.color = RED;
rightRotate(grand);
//与上面对称
}else {
//3.如果父节点是祖父节点的右子节点,与上面完全相反,本质一样
RedBlackNode<AnyType> uncle = grand.left;
//情况一:叔叔节点也是红色
if (uncle != null && uncle.color == RED){
parent.color = BLACK;
uncle.color = BLACK;
grand.color = RED;
t = grand;
continue;
}

//情况二:叔叔节点是黑色的,且当前节点是左子节点
if (t == parent.left){
rightRotate(parent);
RedBlackNode<AnyType> temp = parent;
parent = t;
t = temp;
}

//情况三:叔叔节点是黑色,且当前节点是右子节点
parent.color = BLACK;
grand.color = RED;
leftRotate(grand);

}
}
this.root.color = BLACK;

}

节点的删除

上面探讨完了红-黑树的插入操作,接下来讨论删除。红黑树的删除分成两部分走

第一步删除节点

第一步就把红黑树当成二叉树进行删除。二叉树的删除要考虑三种情况:
1.如果待删除节点没有子节点,那么直接删掉即可
2.如果待删除节点只有一个子节点,那么直接删除,并用其子节点去顶替他。
3.如果待删除节点有两个子节点,找出他的后继节点,处理后继节点和被删除节点父节点的关系,最后处理后继节点子节点和被删除节点子节点的关系。

后继节点:删除一个节点后用来代替该删除位置的节点,当删除节点有两个子节点时,后继节点是删除节右子树中最小的节点。

第二步删除调整

删除调整的内容有些抽象,并且非常复杂。

在第一步删除节点后,可能会违背红黑树的特性需要修复包括下面两个因素:

1.删除黑色节点导致违背规则4。
2.删除节点的儿子和父亲相连时,都是红色违背规则3。

所以就需要通过旋转和变色来修正红黑树。删除修复的总体思想是从兄弟节点借调黑色节点使树保持局部平衡,如果局部平衡达到了,就看整体的树是否平衡,如果不平衡纠结着向上调整。

  • 真正要删除的节点

当删除一节点时,如果该节点有左右儿子节点,我们会找到被删除节点的后继节点来替代他,所以这个要删除的节点并不会引起红黑树不平衡,引起不平衡的是那个真正被删除的后继节点。所以如果我们把要删除的节点叫做”将要删除的节点”,那”真正要删除的节点”实际上则是他的后继。这个概念是很好理解的。我们判断的删除节点需要修复的两个关键因素是根据这个”真正要删除的节点的”。

如果要删除的节点不存在后继即只有一个或没有子节点,那这个要删除的节点就是真正要删除的节点

  • 删除修复的四种情况(不含镜像对称)

约定:空的节点是黑色,当前节指 真正被删除节点 的子节点

1.当前节点是黑色的,且兄弟节点是红色的(那么父节点和兄弟节点的子节点肯定是黑色的)
2.当前节点是黑色的,且兄弟节点是黑色的,且兄弟节点的两个子节点是黑色的
3.当前节点四黑色的,且兄弟节点是黑色的,且兄弟节点的左子节点是红色的,右子节点是黑色的
4.当前节点是黑色的,且兄弟节点是黑色的,且兄弟节点的右子节点是红色的,左子节点任意颜色

情况一:将父节点涂红,然后将当前节点父节点作为作为支撑左旋,于是当前节点的兄弟变为黑色。此时可能变为情况二三四的任意一种。
情况二:将兄弟节点涂红,将当前节点指向其父节点,将其父节点指向当前节点的祖父节点。
情况三:当前节点的兄弟节点涂红,把兄弟节点的左子节点涂黑,然后以兄弟节点作为支点左右旋操作。然后兄弟节点就变成黑色,且兄弟节点右子节点变成红色。
情况四:把兄弟节点涂成父节点的颜色,再把父节点涂黑,把兄弟节点的右子节点涂黑,然后以当前节点的父节点为支点做左旋操作。

我们可以看出,如果是从情况一开始发生的,可能情况二、三、四的一种:如果是情况二,就不可能再出现三和四;如果是情况三,必然会导致情况四的出现;如果二和三都不是,那必然是四。当然咯,实际中可能不一定会从情况一发生,这要看具体情况了

  • 代码
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
/**
* 红黑树删除调整方法
* @param node 真正删除节点的子节点表示待修正的节点,即带修正的节点
* @param parent
*/
private void removeFix(RedBlackNode<AnyType> node, RedBlackNode<AnyType> parent) {
RedBlackNode<AnyType> other = null;

while ((node == null || node.color == BLACK) && (node != this.root)) {
//当node是左子节点
if (parent.left == node) {
//兄弟节点
other = parent.right;
//情况一:node的兄弟节点other是红色
if (other != null && other.color == RED) {
other.color = BLACK;
parent.color = RED;
leftRotate(parent);
other = parent.right;
}
//情况二:node的兄弟节点other是黑色的且other的两个子节点也都是黑色
if ((other.left == null || other.left.color == BLACK)
&& (other.right == null || other.right.color == BLACK)) {
other.color = RED;
node = parent;
parent = getParent(node);
} else {
//情况三:node的兄弟节点other是黑色,且other的左子节点是红色,右子节点是黑色
if (other.right == null || other.right.color == BLACK) {
other.left.color = BLACK;
other.color = RED;
rightRotate(other);
other = parent.right;
}

//情况四:node的兄弟节点other是黑色的,且other的右子节点是红色,左子节点任意颜色
boolean parentColor = parent.color;
other.color = parentColor;
parent.color = BLACK;
other.right.color = BLACK;
leftRotate(parent);
node = this.root;
break;
//与上面对称
}
} else {
other = parent.left;
if (other.color == RED){
other.color = BLACK;
parent.color = RED;
rightRotate(parent);
other = parent.left;
}

if ((other.left == null || other.left.color == BLACK) &&
(other.right == null) || other.right.color == BLACK){
other.color = RED;
node = parent;
parent = node.parent;
}else {
if (other.left == null || other.left.color == BLACK){
other.right.color = BLACK;
other.color = RED;
leftRotate(other);
other = parent.left;
}
//情况四:node的兄弟节点other是黑色的,且other的右子节点是红色,左子节点任意颜色
boolean parentColor = parent.color;
other.color = parentColor;
parent.color = BLACK;
other.right.color = BLACK;
leftRotate(parent);
node = this.root;
break;
}
}
}
if (node != null){
node.color = BLACK;
}

}

ps:
红黑树的删除操作是非常难得,即使我看懂了第一遍,第二遍还是会有地方不通。多画几遍图吧,删除这里我也崩溃了两天。(T T !) 同样可以看一下这篇文章 包教包会

#### 红黑树代码

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
package cn.dombro.datastructures.tree;

/**
* 红黑树简单例子
*/
public class RedBlackTree<AnyType extends Comparable<? super AnyType>> {

private static class RedBlackNode<AnyType>{
AnyType element;
RedBlackNode<AnyType> left;
RedBlackNode<AnyType> right;
RedBlackNode<AnyType> parent;
boolean color;

public RedBlackNode(AnyType element, RedBlackNode<AnyType> left, RedBlackNode<AnyType> right, RedBlackNode<AnyType> parent,boolean color) {
this.element = element;
this.left = left;
this.right = right;
this.parent = parent;
this.color = color;
}
}

private RedBlackNode<AnyType> root;

private static final boolean RED = false;

private static final boolean BLACK = true;

//插入红黑树操作
public void insert(AnyType x){
//插入新节点的颜色都为红色
RedBlackNode<AnyType> node = new RedBlackNode<AnyType>(x,null,null,null,RED);
if (node != null)
insert(root);
}

public void insert(RedBlackNode<AnyType> t){
//从根节点插入
RedBlackNode<AnyType> parent = null;
RedBlackNode<AnyType> node = this.root;
//找到插入位置
while (node != null){
parent = node;
int comparableResult = t.element.compareTo(node.element);
if (comparableResult < 0){
node = node.left;
}else if (comparableResult > 0){
node = node.right;
}
}
//找到插入的父亲结点
t.parent = parent;
//判断 t 插在左还是插在右
if (parent != null){
int comparableResult = t.element.compareTo(parent.element);
if (comparableResult < 0){
parent.left = t;
}else {
parent.right = t;
}
}else {
this.root = t;
}

insertFixUp(t);
}

//插入后重新调整为红黑树
private void insertFixUp(RedBlackNode<AnyType> t) {
//父节点,祖父节点
RedBlackNode<AnyType> parent ,grand;
//1.需要调整条件,父节点存在,且父节点颜色为红
while ((parent = getParent(t)) != null && parent.color == RED){
//获取祖父节点
grand = getParent(parent);
//2.如果父节点是祖父节点的左儿子
if (parent == grand.left){
//获取叔叔节点
RedBlackNode<AnyType> uncle = grand.right;
//情况一:叔叔节点也是红色
if(uncle != null && uncle.color == RED){
//将父节点和叔叔节点涂黑
parent.color = BLACK;
uncle.color = BLACK;
grand.color = RED;
//将当前节点位置放到祖父节点
t = grand;
continue;
}
//情况二:叔叔节点是黑色,且当前节点是右子节点
if (t == parent.right){
//从父节点处左旋
leftRotate(parent);
//以当前父节点和自己调换,作为新节点,为右旋做准备
RedBlackNode<AnyType> temp = parent;
parent = t;
t = temp;
}

//情况三:叔叔节点是黑色,且当前节点是左子节点
//将当前节点的父节点涂黑,将其祖父涂红
parent.color = BLACK;
grand.color = RED;
rightRotate(grand);
//与上面对称
}else {
//3.如果父节点是祖父节点的右子节点,与上面完全相反,本质一样
RedBlackNode<AnyType> uncle = grand.left;
//情况一:叔叔节点也是红色
if (uncle != null && uncle.color == RED){
parent.color = BLACK;
uncle.color = BLACK;
grand.color = RED;
t = grand;
continue;
}

//情况二:叔叔节点是黑色的,且当前节点是左子节点
if (t == parent.left){
rightRotate(parent);
RedBlackNode<AnyType> temp = parent;
parent = t;
t = temp;
}

//情况三:叔叔节点是黑色,且当前节点是右子节点
parent.color = BLACK;
grand.color = RED;
leftRotate(grand);

}
}
this.root.color = BLACK;

}

public void remove(AnyType x){
RedBlackNode<AnyType> node = search(x);
remove(node);
}

//t删除节点
private void remove(RedBlackNode<AnyType> t){
//child是最终被删除节点的替代孩子,parent是最终被删除节点的父亲
RedBlackNode<AnyType> child ,parent;
boolean color;
//被删除节点左右孩子都不为空
if ((t.left != null) && (t.right != null)){
//被真正删除节点的后继节点
RedBlackNode<AnyType> replace = t;
replace = replace.right;
//找到其右子树中最小节点
replace = findMin(replace);
if (getParent(t) != null){
//用后继节点代替要删除的节点
if (t == getParent(t).left){
getParent(t).left = replace;
}else {
getParent(t).right = replace;
}
}else {
//否则删除的节点时根节点,直接为根节点赋值,只有根节点没有父节点
this.root = replace;
}
//后继节点肯定不存在左子节点,child为后继节点的右孩子
child = replace.right;
parent = getParent(replace);
color = replace.color;
//若后继结点是要删除节点的儿子,则直接代替
if (parent == t){
parent = replace;
}else {
//如果replace存在右孩子
if (child != null) {
//此处真正删除了replace
child.parent = parent;
parent.left = child;
replace.right = t.right;
t.right.parent = replace;
}
replace.parent = t.parent;
//保持原来颜色
replace.color = t.color;
replace.left = t.left;
t.left.parent = replace;
//如果后继节点(真正要删除的节点)的颜色是黑色,重新调整红黑树
if (color == BLACK) {
removeFix(child, parent);
}
t = null;
return;
}
} //被删除

//如果被删除的节点只有一个儿子
if (t.left != null){
child = t.left;
}else {
child = t.right;
}
parent = t.parent;
color = t.color;
//如果唯一的孩子不为空
if (child != null){
child.parent = parent;
}
//如果要删除的节点不是根节点
if (parent!=null){
if (parent.left == t){
parent.left = child;
}else {
parent.right = child;
}
}else {
this.root = child;
}
//如果删除节点的颜色是黑色,则要调用平衡方法
if (color = BLACK){
removeFix(child,parent);
}
t = null;
}

/**
* 红黑树删除调整方法
* @param node 后继子节点的子节点,即带修正的节点
* @param parent
*/
private void removeFix(RedBlackNode<AnyType> node, RedBlackNode<AnyType> parent) {
RedBlackNode<AnyType> other = null;

while ((node == null || node.color == BLACK) && (node != this.root)) {
//当node是左子节点
if (parent.left == node) {
//兄弟节点
other = parent.right;
//情况一:node的兄弟节点other是红色
if (other != null && other.color == RED) {
other.color = BLACK;
parent.color = RED;
leftRotate(parent);
other = parent.right;
}
//情况二:node的兄弟节点other是黑色的且other的两个子节点也都是黑色
if ((other.left == null || other.left.color == BLACK)
&& (other.right == null || other.right.color == BLACK)) {
other.color = RED;
node = parent;
parent = getParent(node);
} else {
//情况三:node的兄弟节点other是黑色,且other的左子节点是红色,右子节点是黑色
if (other.right == null || other.right.color == BLACK) {
other.left.color = BLACK;
other.color = RED;
rightRotate(other);
other = parent.right;
}

//情况四:node的兄弟节点other是黑色的,且other的右子节点是红色,左子节点任意颜色
boolean parentColor = parent.color;
other.color = parentColor;
parent.color = BLACK;
other.right.color = BLACK;
leftRotate(parent);
node = this.root;
break;
//与上面对称
}
} else {
other = parent.left;
if (other.color == RED){
other.color = BLACK;
parent.color = RED;
rightRotate(parent);
other = parent.left;
}

if ((other.left == null || other.left.color == BLACK) &&
(other.right == null) || other.right.color == BLACK){
other.color = RED;
node = parent;
parent = node.parent;
}else {
if (other.left == null || other.left.color == BLACK){
other.right.color = BLACK;
other.color = RED;
leftRotate(other);
other = parent.left;
}
//情况四:node的兄弟节点other是黑色的,且other的右子节点是红色,左子节点任意颜色
boolean parentColor = parent.color;
other.color = parentColor;
parent.color = BLACK;
other.right.color = BLACK;
leftRotate(parent);
node = this.root;
break;
}
}
}
if (node != null){
node.color = BLACK;
}

}


public RedBlackNode<AnyType> search(AnyType x){
return search(x,root);
}

private RedBlackNode<AnyType> search(AnyType x,RedBlackNode<AnyType> t){
while (t != null){
int comparableResult = x.compareTo(t.element);
if (comparableResult < 0 ){
t = t.left;
}else if (comparableResult > 0){
t = t.right;
}else {
return t;
}
}
return t;
}

//以t为支点右旋操作
private void rightRotate(RedBlackNode<AnyType> t) {
RedBlackNode<AnyType> leftNode = t.left;
t.left = leftNode.right;
if (leftNode.right != null){
leftNode.right.parent = t;
}

leftNode.parent = t.parent;
if (t.parent == null){
this.root = leftNode;
}else {
if (t == t.parent.right){
t.parent.right = leftNode;
}else {
t.parent.left = leftNode;

}
}
leftNode.right = t;
t.parent = leftNode;
}

//以t为支点左旋操作
private void leftRotate(RedBlackNode<AnyType> t) {
RedBlackNode<AnyType> rightNode = t.right;
t.right = rightNode.left;
if (rightNode.left != null){
rightNode.left.parent = t;
}
rightNode.parent = t.parent;
//如果 parent 没有父节点说明 parent 是根节点
if (t.parent == null){
this.root = rightNode;
}else {
//判断parent是左子树还是右子树
if (t == t.parent.left){
t.parent.left = rightNode;
}else {
t.parent.right = rightNode;
}
}

rightNode.left = t;
t.parent = rightNode;

}



public RedBlackNode<AnyType> getParent(RedBlackNode<AnyType> t){
return (t != null)? t.parent :null;
}



public RedBlackNode<AnyType> findMin(RedBlackNode<AnyType> t){

if (t == null){
while (t.left != null){
t = t.left;
}
}
return t;
}

public RedBlackNode<AnyType> findMax(RedBlackNode<AnyType> t){
if (t != null){
while (t.right != null){
t = t.right;
}
}
return t;
}
}
参考

eson_15 的 csdn

CATALOG
  1. 1. 平衡树
  2. 2. 为什么要平衡
  3. 3. AVL树
    1. 3.1. AVL树平衡条件
    2. 3.2. 树的旋转
    3. 3.3. 单旋转
    4. 3.4. 调整的时机
    5. 3.5. AVL节点
    6. 3.6. 代码
  4. 4. 红黑树
    1. 4.1. 红黑树特点
    2. 4.2. 插入节点
  5. 5. 红黑树的节点
    1. 5.1. 平衡性修正
    2. 5.2. 节点的插入
  6. 6. 节点的删除
    1. 6.1. 第一步删除节点
    2. 6.2. 第二步删除调整
      1. 6.2.0.1. 参考