Fork me on GitHub

浅谈红黑树

红黑树,满足二分搜索树的性质,与AVL一样,在二分搜索树的基础上,添加了一些特性保证自己不会退化为链表,也就是保证自己是一棵平衡二叉树。

红黑树具有以下五个性质:

  1. 每个节点或者是红色的,或者是黑色的
  2. 根节点是黑色的
  3. 每个叶子结点(最后的空节点)是黑色的
  4. 如果一个节点是红色的,那么他的孩子节点都是黑色的
  5. 从任意一个节点到叶子节点,经过的黑色节点是一样的

在具体讲红黑树之前,我们来谈谈另一种平衡的树结构:2-3树

事实上,红黑树与2-3树是等价的。

2-3树:

  1. 满足二分搜索树的基本性质
  2. 节点可以存放一个元素或者两个元素
  3. 每个节点或者有两个孩子或者有三个孩子
  4. 2-3是一颗绝对平衡的树

可以通过下图来理解上述的性质:

图解2-3树保持绝对平衡的原理:



而红黑树的发明人Rudolf Bayer在算法四这本书说明了红黑树与2-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
import java.util.ArrayList;

public class RBTree<K extends Comparable<K>, V> {

private static final boolean RED = true;
private static final boolean BLACK = false;

private class Node{
public K key;
public V value;
public Node left, right;
public boolean color;

public Node(K key, V value){
this.key = key;
this.value = value;
left = null;
right = null;
color = RED;
}
}

private Node root;
private int size;

public RBTree(){
root = null;
size = 0;
}

public int getSize(){
return size;
}

public boolean isEmpty(){
return size == 0;
}

// 判断节点node的颜色
private boolean isRed(Node node){
if(node == null)
return BLACK;
return node.color;
}

// node x
// / \ 左旋转 / \
// T1 x ---------> node T3
// / \ / \
// T2 T3 T1 T2
private Node leftRotate(Node node){

Node x = node.right;

// 左旋转
node.right = x.left;
x.left = node;

x.color = node.color;
node.color = RED;

return x;
}

// node x
// / \ 右旋转 / \
// x T2 -------> y node
// / \ / \
// y T1 T1 T2
private Node rightRotate(Node node){

Node x = node.left;

// 右旋转
node.left = x.right;
x.right = node;

x.color = node.color;
node.color = RED;

return x;
}

// 颜色翻转
private void flipColors(Node node){

node.color = RED;
node.left.color = BLACK;
node.right.color = BLACK;
}

// 向红黑树中添加新的元素(key, value)
public void add(K key, V value){
root = add(root, key, value);
root.color = BLACK; // 最终根节点为黑色节点
}

// 向以node为根的红黑树中插入元素(key, value),递归算法
// 返回插入新节点后红黑树的根
private Node add(Node node, K key, V value){

if(node == null){
size ++;
return new Node(key, value); // 默认插入红色节点
}

if(key.compareTo(node.key) < 0)
node.left = add(node.left, key, value);
else if(key.compareTo(node.key) > 0)
node.right = add(node.right, key, value);
else // key.compareTo(node.key) == 0
node.value = value;

if (isRed(node.right) && !isRed(node.left))
node = leftRotate(node);

if (isRed(node.left) && isRed(node.left.left))
node = rightRotate(node);

if (isRed(node.left) && isRed(node.right))
flipColors(node);

return node;
}

// 返回以node为根节点的二分搜索树中,key所在的节点
private Node getNode(Node node, K key){

if(node == null)
return null;

if(key.equals(node.key))
return node;
else if(key.compareTo(node.key) < 0)
return getNode(node.left, key);
else // if(key.compareTo(node.key) > 0)
return getNode(node.right, key);
}

public boolean contains(K key){
return getNode(root, key) != null;
}

public V get(K key){

Node node = getNode(root, key);
return node == null ? null : node.value;
}

public void set(K key, V newValue){
Node node = getNode(root, key);
if(node == null)
throw new IllegalArgumentException(key + " doesn't exist!");

node.value = newValue;
}

// 返回以node为根的二分搜索树的最小值所在的节点
private Node minimum(Node node){
if(node.left == null)
return node;
return minimum(node.left);
}

// 删除掉以node为根的二分搜索树中的最小节点
// 返回删除节点后新的二分搜索树的根
private Node removeMin(Node node){

if(node.left == null){
Node rightNode = node.right;
node.right = null;
size --;
return rightNode;
}

node.left = removeMin(node.left);
return node;
}

// 从二分搜索树中删除键为key的节点
public V remove(K key){

Node node = getNode(root, key);
if(node != null){
root = remove(root, key);
return node.value;
}
return null;
}

private Node remove(Node node, K key){

if( node == null )
return null;

if( key.compareTo(node.key) < 0 ){
node.left = remove(node.left , key);
return node;
}
else if(key.compareTo(node.key) > 0 ){
node.right = remove(node.right, key);
return node;
}
else{ // key.compareTo(node.key) == 0

// 待删除节点左子树为空的情况
if(node.left == null){
Node rightNode = node.right;
node.right = null;
size --;
return rightNode;
}

// 待删除节点右子树为空的情况
if(node.right == null){
Node leftNode = node.left;
node.left = null;
size --;
return leftNode;
}

// 待删除节点左右子树均不为空的情况

// 找到比待删除节点大的最小节点, 即待删除节点右子树的最小节点
// 用这个节点顶替待删除节点的位置
Node successor = minimum(node.right);
successor.right = removeMin(node.right);
successor.left = node.left;

node.left = node.right = null;

return successor;
}
}

public static void main(String[] args){

System.out.println("Pride and Prejudice");

ArrayList<String> words = new ArrayList<>();
if(FileOperation.readFile("pride-and-prejudice.txt", words)) {
System.out.println("Total words: " + words.size());

RBTree<String, Integer> map = new RBTree<>();
for (String word : words) {
if (map.contains(word))
map.set(word, map.get(word) + 1);
else
map.add(word, 1);
}

System.out.println("Total different words: " + map.getSize());
System.out.println("Frequency of PRIDE: " + map.get("pride"));
System.out.println("Frequency of PREJUDICE: " + map.get("prejudice"));
}

System.out.println();
}
}

钱聪 wechat
欢迎交流学习。
么么!