红黑树的实现(Java)

红黑树的实现(Java)

m阶B树的性质

image-20220330140625271

image-20220330140737916

image-20220330140715824

B树和二叉搜索树的关系

image-20220330141817463

红黑树性质

红黑树和4阶B树是等价的

image-20220330150157720

image-20220330151346821

红黑树实现

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
/**
* @author zwj
* @date 2022-03-30-14:59
*/
public class RedBlackTree<E> extends BalancedBinarySearchTree<E>{
private static final boolean RED = false;
private static final boolean BLACK = true;

public RedBlackTree() {
this(null);
}

public RedBlackTree(Comparator<E> comparator) {
super(comparator);
}

@Override
protected void afterAdd(Node<E> node) {
Node<E> parent = node.parent;

// 添加的是根节点 或者 上溢到达了根节点
if (parent == null) {
black(node);
return;
}

// 如果父节点是黑色,直接返回
if (isBlack(parent)) return;

// 叔父节点
Node<E> uncle = parent.sibling();
// 祖父节点
Node<E> grand = red(parent.parent);
if (isRed(uncle)) { // 叔父节点是红色【B树节点上溢】
black(parent);
black(uncle);
// 把祖父节点当做是新添加的节点
afterAdd(grand);
return;
}

// 叔父节点不是红色
if (parent.isLeftChild()) { // L
if (node.isLeftChild()) { // LL
black(parent);
} else { // LR
black(node);
rotateLeft(parent);
}
rotateRight(grand);
} else { // R
if (node.isLeftChild()) { // RL
black(node);
rotateRight(parent);
} else { // RR
black(parent);
}
rotateLeft(grand);
}
}

@Override
protected void afterRemove(Node<E> node) {
// 如果删除的节点是红色
// 或者 用以取代删除节点的子节点是红色
if (isRed(node)) {
black(node);
return;
}

Node<E> parent = node.parent;
// 删除的是根节点
if (parent == null) return;

// 删除的是黑色叶子节点【下溢】
// 判断被删除的node是左还是右
boolean left = parent.left == null || node.isLeftChild();
Node<E> sibling = left ? parent.right : parent.left;
if (left) { // 被删除的节点在左边,兄弟节点在右边
if (isRed(sibling)) { // 兄弟节点是红色
black(sibling);
red(parent);
rotateLeft(parent);
// 更换兄弟
sibling = parent.right;
}

// 兄弟节点必然是黑色
if (isBlack(sibling.left) && isBlack(sibling.right)) {
// 兄弟节点没有1个红色子节点,父节点要向下跟兄弟节点合并
boolean parentBlack = isBlack(parent);
black(parent);
red(sibling);
if (parentBlack) {
afterRemove(parent);
}
} else { // 兄弟节点至少有1个红色子节点,向兄弟节点借元素
// 兄弟节点的左边是黑色,兄弟要先旋转
if (isBlack(sibling.right)) {
rotateRight(sibling);
sibling = parent.right;
}

color(sibling, colorOf(parent));
black(sibling.right);
black(parent);
rotateLeft(parent);
}
} else { // 被删除的节点在右边,兄弟节点在左边
if (isRed(sibling)) { // 兄弟节点是红色
black(sibling);
red(parent);
rotateRight(parent);
// 更换兄弟
sibling = parent.left;
}

// 兄弟节点必然是黑色
if (isBlack(sibling.left) && isBlack(sibling.right)) {
// 兄弟节点没有1个红色子节点,父节点要向下跟兄弟节点合并
boolean parentBlack = isBlack(parent);
black(parent);
red(sibling);
if (parentBlack) {
afterRemove(parent);
}
} else { // 兄弟节点至少有1个红色子节点,向兄弟节点借元素
// 兄弟节点的左边是黑色,兄弟要先旋转
if (isBlack(sibling.left)) {
rotateLeft(sibling);
sibling = parent.left;
}

color(sibling, colorOf(parent));
black(sibling.left);
black(parent);
rotateRight(parent);
}
}
}

private Node<E> color(Node<E> node, boolean color) {
if (node == null) return node;
((RBNode<E>)node).color = color;
return node;
}

private Node<E> red(Node<E> node) {
return color(node, RED);
}

private Node<E> black(Node<E> node) {
return color(node, BLACK);
}

private boolean colorOf(Node<E> node) {
return node == null ? BLACK : ((RBNode<E>)node).color;
}

private boolean isBlack(Node<E> node) {
return colorOf(node) == BLACK;
}

private boolean isRed(Node<E> node) {
return colorOf(node) == RED;
}

@Override
protected Node<E> createNode(E element, Node<E> parent) {
return new RBNode<>(element, parent);
}

private static class RBNode<E> extends Node<E> {
boolean color = RED;
public RBNode(E element, Node<E> parent) {
super(element, parent);
}

@Override
public String toString() {
String str = "";
if (color == RED) {
str = "R_";
}
return str + element.toString();
}
}
}