前言
网上有非常多的关于红黑树理论的描述，本文的重点将不在于此，但是会在文中给出优秀文章的链接。对红黑树不了解的建议先阅读文章再看实现。本红黑树实现不支持多线程环境。因为删除操作灰常复杂，所以后续更新。源码在文末可以查看。
参考链接
https://www.geeksforgeeks.org/red-black-tree-set-3-delete-2/
https://www.geeksforgeeks.org/red-black-tree-set-2-insert/
http://www.codebytes.in/2014/10/red-black-tree-java-implementation.html
https://blog.csdn.net/eson_15/article/details/51144079
数据结构
定义的红黑树的节点如下：
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
| private static class Node<T>{
static final int RED = 0;
static final int BLACK = 1;
T value;
int color = RED;
Node<T> leftChild;
Node<T> rightChild;
Node<T> parent;
Node(T value) {
this.value = value;
}
boolean isRoot() {
return this.parent == null;
}
boolean isLeaf() {
return this.leftChild == null && this.rightChild == null;
}
boolean isLeftChild() {
return this.parent != null && this.parent.leftChild == this;
}
boolean isRightChild() {
return this.parent != null && this.parent.rightChild == this;
}
Node<T> getUncle() {
if(this.parent == null || this.parent.parent == null) return null;
if(this.parent.isLeftChild()) {
return this.parent.parent.rightChild;
} else {
return this.parent.parent.leftChild;
}
}
Node<T> getSibling() {
if(this.parent == null) return null;
return this.parent.leftChild == this ? this.parent.rightChild : this.parent.leftChild;
}
boolean isRed() {
return this.color == RED;
}
boolean isBlack() {
return this.color == BLACK;
}
}
|
该Node作为RedBlackTree的一个内部类存在。除了和普通的TreeNode相同给的左子节点和右子节点的引用，还额外引用了父节点，方便我们回溯。除此以外还封装了一些方法，比如获得自己的祖父节点，叔叔节点以及兄弟节点等。
旋转操作
因为额外持有了父节点，所以在执行旋转操作的时候需要额外注意空指针以及不恰当的赋值带来的循环引用。左旋和右旋的代码如下：
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
| private void rotateLeft(Node<T> node) {
if(node == null || node.rightChild == null) return;
Node<T> parent = node.parent;
Node<T> rightChild = node.rightChild;
if(rightChild.leftChild != null) {
node.rightChild = rightChild.leftChild;
node.rightChild.parent = node;
} else {
node.rightChild = null;
}
rightChild.leftChild = node;
node.parent = rightChild;
if(parent != null) {
rightChild.parent = parent;
if(node == parent.leftChild) {
parent.leftChild = rightChild;
} else {
parent.rightChild = rightChild;
}
} else {
rightChild.parent = null;
root = rightChild;
}
}
private void rotateRight(Node<T> node) {
if(node == null || node.leftChild == null) return;
Node<T> parent = node.parent;
Node<T> leftChild = node.leftChild;
if(leftChild.rightChild != null) {
node.leftChild = leftChild.rightChild;
node.leftChild.parent = node;
} else {
node.leftChild = null;
}
leftChild.rightChild = node;
node.parent = leftChild;
if(parent != null) {
leftChild.parent = parent;
if(node == parent.leftChild) {
parent.leftChild = leftChild;
} else {
parent.rightChild = leftChild;
}
} else {
leftChild.parent = null;
root = leftChild;
}
}
|
##插入##
我们知道，在红黑树中插入一个节点相当于在一个二叉搜索树中插入一个节点。因此该节点一定是作为叶节点而插入的。二者唯一的不同在于，默认插入的节点为红色，我们需要重新调整树结构从而确保红黑树重新达到平衡。
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
| @Override
public void insert(T t) {
Node<T> newNode = new Node<T>(t);
if(root == null) {
root = newNode;
root.color = Node.BLACK;
size++;
} else {
Node<T> tmp = root;
while(tmp != null) {
if(tmp.value.equals(t)) {
newNode = tmp;
break;
} else if(tmp.value.compareTo(t) < 0) {
if(tmp.rightChild == null) {
tmp.rightChild = newNode;
newNode.parent = tmp;
size++;
break;
} else {
tmp = tmp.rightChild;
}
} else {
if(tmp.leftChild == null) {
tmp.leftChild = newNode;
newNode.parent = tmp;
size++;
break;
} else {
tmp = tmp.leftChild;
}
}
}
}
adjust(newNode);
}
private void adjust(Node<T> node) {
if(node.isRoot()) {
node.color = Node.BLACK;
return;
} else if(node.parent.isRed()) {
//肯定存在祖父节点，因为根节点必须为黑色
Node<T> parent = node.parent;
Node<T> grandParent = node.parent.parent;
Node<T> uncle = node.getUncle();
if(uncle!=null && uncle.isRed()) {
parent.color = Node.BLACK;
uncle.color = Node.BLACK;
grandParent.color = Node.RED;
adjust(grandParent);
} else {
if(node.isLeftChild() && node.parent.isLeftChild()) {
parent.color = Node.BLACK;
grandParent.color = Node.RED;
rotateRight(grandParent);
} else if(node.isRightChild() && node.parent.isRightChild()) {
parent.color = Node.BLACK;
grandParent.color = Node.RED;
rotateLeft(grandParent);
} else if(node.isLeftChild() && node.parent.isRightChild()) {
node.color = Node.BLACK;
grandParent.color = Node.RED;
rotateRight(parent);
rotateLeft(grandParent);
} else {
node.color = Node.BLACK;
grandParent.color = Node.RED;
rotateLeft(parent);
rotateRight(grandParent);
}
}
}
}
|
源码
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
| public interface RedBlackTreeADT<T extends Comparable<T>> {
boolean contains(T t);
void insert(T t);
void delete(T t);
int size();
}
public class RedBlackTree<T extends Comparable<T>> implements RedBlackTreeADT<T>{
private int size;
private Node<T> root;
private static class Node<T>{
static final int RED = 0;
static final int BLACK = 1;
T value;
int color = RED;
Node<T> leftChild;
Node<T> rightChild;
Node<T> parent;
Node(T value) {
this.value = value;
}
boolean isRoot() {
return this.parent == null;
}
boolean isLeaf() {
return this.leftChild == null && this.rightChild == null;
}
boolean isLeftChild() {
return this.parent != null && this.parent.leftChild == this;
}
boolean isRightChild() {
return this.parent != null && this.parent.rightChild == this;
}
Node<T> getUncle() {
if(this.parent == null || this.parent.parent == null) return null;
if(this.parent.isLeftChild()) {
return this.parent.parent.rightChild;
} else {
return this.parent.parent.leftChild;
}
}
Node<T> getSibling() {
if(this.parent == null) return null;
return this.parent.leftChild == this ? this.parent.rightChild : this.parent.leftChild;
}
boolean isRed() {
return this.color == RED;
}
boolean isBlack() {
return this.color == BLACK;
}
}
@Override
public boolean contains(T t) {
Node<T> tmp = root;
while(tmp != null) {
int cmp = tmp.value.compareTo(t);
if(cmp == 0) {
return true;
} else if (cmp < 0) {
tmp = tmp.rightChild;
} else {
tmp = tmp.leftChild;
}
}
return false;
}
@Override
public void insert(T t) {
Node<T> newNode = new Node<T>(t);
if(root == null) {
root = newNode;
root.color = Node.BLACK;
size++;
} else {
Node<T> tmp = root;
while(tmp != null) {
if(tmp.value.equals(t)) {
newNode = tmp;
break;
} else if(tmp.value.compareTo(t) < 0) {
if(tmp.rightChild == null) {
tmp.rightChild = newNode;
newNode.parent = tmp;
size++;
break;
} else {
tmp = tmp.rightChild;
}
} else {
if(tmp.leftChild == null) {
tmp.leftChild = newNode;
newNode.parent = tmp;
size++;
break;
} else {
tmp = tmp.leftChild;
}
}
}
}
adjust(newNode);
}
private void adjust(Node<T> node) {
if(node.isRoot()) {
node.color = Node.BLACK;
return;
} else if(node.parent.isRed()) {
Node<T> parent = node.parent;
Node<T> grandParent = node.parent.parent;
Node<T> uncle = node.getUncle();
if(uncle!=null && uncle.isRed()) {
parent.color = Node.BLACK;
uncle.color = Node.BLACK;
grandParent.color = Node.RED;
adjust(grandParent);
} else {
if(node.isLeftChild() && node.parent.isLeftChild()) {
parent.color = Node.BLACK;
grandParent.color = Node.RED;
rotateRight(grandParent);
} else if(node.isRightChild() && node.parent.isRightChild()) {
parent.color = Node.BLACK;
grandParent.color = Node.RED;
rotateLeft(grandParent);
} else if(node.isLeftChild() && node.parent.isRightChild()) {
node.color = Node.BLACK;
grandParent.color = Node.RED;
rotateRight(parent);
rotateLeft(grandParent);
} else {
node.color = Node.BLACK;
grandParent.color = Node.RED;
rotateLeft(parent);
rotateRight(grandParent);
}
}
}
}
private void rotateLeft(Node<T> node) {
if(node == null || node.rightChild == null) return;
Node<T> parent = node.parent;
Node<T> rightChild = node.rightChild;
if(rightChild.leftChild != null) {
node.rightChild = rightChild.leftChild;
node.rightChild.parent = node;
} else {
node.rightChild = null;
}
rightChild.leftChild = node;
node.parent = rightChild;
if(parent != null) {
rightChild.parent = parent;
if(node == parent.leftChild) {
parent.leftChild = rightChild;
} else {
parent.rightChild = rightChild;
}
} else {
rightChild.parent = null;
root = rightChild;
}
}
private void rotateRight(Node<T> node) {
if(node == null || node.leftChild == null) return;
Node<T> parent = node.parent;
Node<T> leftChild = node.leftChild;
if(leftChild.rightChild != null) {
node.leftChild = leftChild.rightChild;
node.leftChild.parent = node;
} else {
node.leftChild = null;
}
leftChild.rightChild = node;
node.parent = leftChild;
if(parent != null) {
leftChild.parent = parent;
if(node == parent.leftChild) {
parent.leftChild = leftChild;
} else {
parent.rightChild = leftChild;
}
} else {
leftChild.parent = null;
root = leftChild;
}
}
@Override
public int size() {
return size;
}
public void printTree() {
this.printTree(this.root);
}
private void printTree(Node<T> root) {
if(root == null) {
System.out.print("nil(BLACK)");
return;
}
printTree(root.leftChild);
System.out.print(root.value + "(" + (root.color==Node.RED ? "RED" : "BLACK") + ")");
printTree(root.rightChild);
}
@Override
public void delete(T t) {
}
}
|
有任何问题，欢迎指出！