红黑树

红黑树

  1. 大名鼎鼎的红黑树
    红黑树(Red Black Tree) 是一种自平衡二叉查找树,是在计算机科学中用到的一种数据结构,典型的用途是实现关联数组。红黑树和AVL树类似,都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡,从而获得较高的查找性能。
    它虽然是复杂的,但它的最坏情况运行时间也是非常良好的,并且在实践中是高效的: 它可以在O(log n)时间内做查找,插入和删除,这里的n 是树中元素的数目。
  2. 红黑树的五条基本性质
    性质1. 节点是红色或黑色。
    性质2. 根节点是黑色。
    性质3 每个叶节点(NIL节点,空节点)是黑色的。
    性质4 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
    性质5. 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
    另一条性质是对于红黑树,任何不平衡都会在三次旋转内解决(优化过后的红黑树可以实现)
  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
package AVLTree;

import SetBasicsAndBSTSet.FileOperation;

import java.util.ArrayList;

/**
* @ Description:AVL树的实现
* @ Date: Created in 15:27 23/07/2018
* @ Author: Anthony_Duan
*/
public class AVLTree<K extends Comparable<K>, V> {

private class Node {
public K key;
public V value;
public Node left, right;
public int height;

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

private Node root;
private int size;

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

public int getSize() {
return size;
}

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

// 判断该二叉树是否是一棵二分搜索树
public boolean isBST() {

ArrayList<K> keys = new ArrayList<>();
inOrder(root, keys);
for (int i = 1; i < keys.size(); i++) {
if (keys.get(i - 1).compareTo(keys.get(i)) > 0) {
return false;
}
}
return true;
}

//中序遍历
private void inOrder(Node node, ArrayList<K> keys) {

if (node == null) {
return;
}

inOrder(node.left, keys);
keys.add(node.key);
inOrder(node.right, keys);
}

// 判断该二叉树是否是一棵平衡二叉树
public boolean isBalanced() {
return isBalanced(root);
}

// 判断以Node为根的二叉树是否是一棵平衡二叉树,递归算法
private boolean isBalanced(Node node) {

if (node == null) {
return true;
}

int balanceFactor = getBalanceFactor(node);
if (Math.abs(balanceFactor) > 1) {
return false;
}
return isBalanced(node.left) && isBalanced(node.right);
}

// 获得节点node的高度
private int getHeight(Node node) {
if (node == null) {
return 0;
}
return node.height;
}

// 获得节点node的平衡因子
private int getBalanceFactor(Node node) {
if (node == null) {
return 0;
}
return getHeight(node.left) - getHeight(node.right);
}

// 对节点y进行向右旋转操作,返回旋转后新的根节点x
// y x
// / \ / \
// x T4 向右旋转 (y) z y
// / \ - - - - - - - -> / \ / \
// z T3 T1 T2 T3 T4
// / \
// T1 T2
private Node rightRotate(Node y) {
Node x = y.left;
Node T3 = x.right;

// 向右旋转过程
x.right = y;
y.left = T3;

// 更新height
y.height = Math.max(getHeight(y.left), getHeight(y.right)) + 1;
x.height = Math.max(getHeight(x.left), getHeight(x.right)) + 1;

return x;
}

// 对节点y进行向左旋转操作,返回旋转后新的根节点x
// y x
// / \ / \
// T1 x 向左旋转 (y) y z
// / \ - - - - - - - -> / \ / \
// T2 z T1 T2 T3 T4
// / \
// T3 T4
private Node leftRotate(Node y) {
Node x = y.right;
Node T2 = x.left;

// 向左旋转过程
x.left = y;
y.right = T2;

// 更新height
y.height = Math.max(getHeight(y.left), getHeight(y.right)) + 1;
x.height = Math.max(getHeight(x.left), getHeight(x.right)) + 1;

return x;
}

// 向二分搜索树中添加新的元素(key, value)
public void add(K key, V value) {
root = add(root, key, value);
}

// 向以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;
}

// 更新height
node.height = 1 + Math.max(getHeight(node.left), getHeight(node.right));

// 计算平衡因子
int balanceFactor = getBalanceFactor(node);

// 平衡维护
// LL
if (balanceFactor > 1 && getBalanceFactor(node.left) >= 0) {
return rightRotate(node);
}

// RR
if (balanceFactor < -1 && getBalanceFactor(node.right) <= 0) {
return leftRotate(node);
}

// LR
if (balanceFactor > 1 && getBalanceFactor(node.left) < 0) {
node.left = leftRotate(node.left);
return rightRotate(node);
}

// RL
if (balanceFactor < -1 && getBalanceFactor(node.right) > 0) {
node.right = rightRotate(node.right);
return leftRotate(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);
}

// 从二分搜索树中删除键为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;
}

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

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

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

// 待删除节点左右子树均不为空的情况
else {
// 找到比待删除节点大的最小节点, 即待删除节点右子树的最小节点
// 用这个节点顶替待删除节点的位置
Node successor = minimum(node.right);
//successor.right = removeMin(node.right);
successor.right = remove(node.right, successor.key);
successor.left = node.left;

node.left = node.right = null;

// return successor;
retNode = successor;
}
}

if (retNode == null) {
return null;
}

// 更新height
retNode.height = 1 + Math.max(getHeight(retNode.left), getHeight(retNode.right));

// 计算平衡因子
int balanceFactor = getBalanceFactor(retNode);

// 平衡维护
// LL
if (balanceFactor > 1 && getBalanceFactor(retNode.left) >= 0) {
return rightRotate(retNode);
}

// RR
if (balanceFactor < -1 && getBalanceFactor(retNode.right) <= 0) {
return leftRotate(retNode);
}

// LR
if (balanceFactor > 1 && getBalanceFactor(retNode.left) < 0) {
retNode.left = leftRotate(retNode.left);
return rightRotate(retNode);
}

// RL
if (balanceFactor < -1 && getBalanceFactor(retNode.right) > 0) {
retNode.right = rightRotate(retNode.right);
return leftRotate(retNode);
}

return retNode;
}

public static void main(String[] args) {

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

ArrayList<String> words = new ArrayList<>();
if (FileOperation.readFile("/Users/duanjiaxing/IdeaProjects/Data-Structure/data-structure/src/AVLTree/pride-and-prejudice.txt", words)) {
System.out.println("Total words: " + words.size());

AVLTree<String, Integer> map = new AVLTree<String, Integer>();
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("is BST : " + map.isBST());
System.out.println("is Balanced : " + map.isBalanced());

for (String word : words) {
map.remove(word);
if (!map.isBST() || !map.isBalanced()) {
throw new RuntimeException();
}
}
}

System.out.println();
}
}
-------------End Of This ArticleThank You For Reading-------------