自平衡二叉搜索树问题
节点代码
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
99public class Node <T extends Comparable<T>> implements Comparable<Node<T>>{
public Node(T value) {
this.value = value;
}
public T getValue() {
return value;
}
public void setValue(T value) {
this.value = value;
}
public Node<T> getParent() {
return parent;
}
public void setParent(Node<T> parent) {
if (this.parent != null) {
if (this.parent.left == this) {
this.parent.left = null;
}
if (this.parent.right == this) {
this.parent.right = null;
}
}
this.parent = parent;
}
public Node<T> getLeft() {
return left;
}
public void setLeft(Node<T> left) {
if (this.left != null) {
this.left.parent = null;
}
if (left != null) {
if (left.parent != null) {
if (left == left.parent.left) {
left.parent.left = null;
} else {
left.parent.right = null;
}
}
this.left = left;
this.left.parent = this;
} else {
this.left = null;
}
}
public Node<T> getRight() {
return right;
}
public void setRight(Node<T> right) {
if (this.right != null) {
this.right.parent = null;
}
if (right != null) {
if (right.parent != null) {
if (right == right.parent.left) {
right.parent.left = null;
} else {
right.parent.right = null;
}
}
this.right = right;
this.right.parent = this;
} else {
this.right = null;
}
}
public void setRightAssist(Node<T> right) {
this.right = right;
}
protected T value;
protected Node<T> parent;
protected Node<T> left;
protected Node<T> right;
public int compareTo(Node<T> node) {
if (node == null) {
return 1;
}
if (this.getValue() == null && node.getValue() == null) {
return 0;
}
if (this.getValue() == null) {
return -1;
}
return this.getValue().compareTo(node.getValue());
}
}搜索二叉树接口代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14public interface IBinarySearchTree<T extends Comparable<T>> {
boolean insert(T value);
boolean remove(T value);
boolean contain(T value);
boolean empty();
int size();
Node<T> find(T value);
int getLength();
int getLength(Node<T> node);
void DLREach(IForeachOperator<T> operator);
void LDREach(IForeachOperator<T> operator);
void LRDEach(IForeachOperator<T> operator);
void levelEach(IForeachOperator<T> operator);
}遍历辅助操作值的函数式接口
1
2
3
4
public interface IForeachOperator<T extends Comparable<T>> {
void operator(T value);
}普通的二叉搜索树代码
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
257import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
public class BinaryTree<T extends Comparable<T>> implements IBinarySearchTree<T> {
public boolean insert(T value) {
if (value == null || this.contain(value)) {
return false;
}
if (this.root == null) {
this.root = new Node<>(value);
this.size++;
return true;
}
Node<T> tmp = this.root;
while (tmp != null)
{
if (tmp.getValue().compareTo(value) > 0) {
if (tmp.getLeft() == null) {
tmp.setLeft(new Node<>(value));
this.size++;
return true;
} else {
tmp = tmp.getLeft();
}
} else {
if (tmp.getRight() == null) {
tmp.setRight(new Node<>(value));
this.size++;
return true;
} else {
tmp = tmp.getRight();
}
}
}
return false;
}
public boolean remove(T value) {
if (value == null || !this.contain(value)) {
return false;
}
if (this.size == 1) {
this.size = 0;
this.root = null;
return true;
}
Node<T> removeNode = this.find(value);
if (removeNode.getLeft() == null) {
if (removeNode.getParent() == null) {
this.root = removeNode.getRight();
} else {
if (removeNode == removeNode.getParent().getLeft()) {
removeNode.getParent().setLeft(removeNode.getRight());
} else {
removeNode.getParent().setRight(removeNode.getRight());
}
}
this.size--;
return true;
}
if (removeNode.getRight() == null) {
if (removeNode.getParent() == null) {
this.root = removeNode.getRight();
} else {
if (removeNode == removeNode.getParent().getLeft()) {
removeNode.getParent().setLeft(removeNode.getLeft());
} else {
removeNode.getParent().setRight(removeNode.getLeft());
}
}
this.size--;
return true;
}
Node<T> rightNodeMostLeft = removeNode.getRight();
while (rightNodeMostLeft.getLeft() != null) {
rightNodeMostLeft = rightNodeMostLeft.getLeft();
}
removeNode.setValue(rightNodeMostLeft.getValue());
if (rightNodeMostLeft == removeNode.getRight()) {
removeNode.setRight(rightNodeMostLeft.getRight());
} else {
rightNodeMostLeft.getParent().setLeft(rightNodeMostLeft.getRight());
}
this.size--;
return true;
}
public boolean contain(T value) {
if (value == null) {
return false;
}
Node<T> tmp = this.root;
while (tmp != null) {
if (tmp.getValue().compareTo(value) == 0) {
return true;
} else if (tmp.getValue().compareTo(value) > 0) {
tmp = tmp.getLeft();
} else {
tmp = tmp.getRight();
}
}
return false;
}
public boolean empty() {
return this.size == 0;
}
public int size() {
return this.size;
}
public Node<T> find(T value) {
if (value == null || !this.contain(value)) {
return null;
}
Node<T> tmp = this.root;
while (tmp != null) {
if (tmp.getValue().compareTo(value) == 0) {
return tmp;
} else if (tmp.getValue().compareTo(value) > 0) {
tmp = tmp.getLeft();
} else {
tmp = tmp.getRight();
}
}
return null;
}
public int getLength() {
return this.getLength(this.root);
}
public int getLength(Node<T> node) {
if (node == null) {
return 0;
}
if (node.getLeft() == null && node.getRight() == null) {
return 1;
}
return 1 + Math.max(this.getLength(node.getLeft()), this.getLength(node.getRight()));
}
public void DLREach(IForeachOperator<T> operator) {
if (!this.empty()) {
DLREach(operator, this.root);
}
}
private void DLREach(IForeachOperator<T> operator, Node<T> node) {
if (node != null) {
operator.operator(node.getValue());
DLREach(operator, node.getLeft());
DLREach(operator, node.getRight());
}
}
public void LDREach(IForeachOperator<T> operator) {
if (!this.empty()) {
Stack<Node<T>> stack = new Stack<>();
Node<T> node = this.root;
while (!stack.empty() || node != null) {
if (node != null) {
stack.push(node);
node = node.getLeft();
} else {
node = stack.pop();
operator.operator(node.getValue());
node = node.getRight();
}
}
}
}
public void LRDEach(IForeachOperator<T> operator) {
if (!this.empty()) {
Node<T> node = this.root;
while (node != null) {
Node<T> leftNodeMostRight = node.getLeft();
if (leftNodeMostRight != null) {
while (leftNodeMostRight.getRight() != null && leftNodeMostRight.getRight() != node) {
leftNodeMostRight = leftNodeMostRight.getRight();
}
if (leftNodeMostRight.getRight() == null) {
leftNodeMostRight.setRightAssist(node);
node = node.getLeft();
} else {
leftNodeMostRight.setRightAssist(null);
operatorEdge(operator, node.getLeft());
node = node.getRight();
}
} else {
node = node.getRight();
}
}
operatorEdge(operator, this.root);
}
}
private void operatorEdge(IForeachOperator<T> operator, Node<T> node) {
if (node != null) {
Node<T> tmp1 = node, tmp2 = null;
while (tmp1 != null) {
Node<T> tmp3 = tmp1.getRight();
tmp1.setRightAssist(tmp2);
tmp2 = tmp1;
tmp1 = tmp3;
}
tmp1 = tmp2;
while (tmp1 != null) {
operator.operator(tmp1.getValue());
tmp1 = tmp1.getRight();
}
while (tmp2 != null) {
Node<T> tmp3 = tmp2.getRight();
tmp2.setRightAssist(tmp1);
tmp1 = tmp2;
tmp2 = tmp3;
}
}
}
public void levelEach(IForeachOperator<T> operator) {
if (this.empty()) {
return;
}
Queue<Node<T>> queue = new LinkedList<>();
queue.add(this.root);
while (!queue.isEmpty()) {
Node<T> node = queue.poll();
operator.operator(node.getValue());
if (node.getLeft() != null) {
queue.add(node.getLeft());
}
if (node.getRight() != null) {
queue.add(node.getRight());
}
}
}
protected int size;
protected Node<T> root;
}自平衡二叉搜索树的抽象类代码
1
2
3
4
5
6
7public abstract class CanReBalanceBinarySearchTree<T extends Comparable<T>> extends BinaryTree<T> {
protected abstract void reBalance(Node<T> node);
protected abstract void LeftRotate(Node<T> node);
protected abstract void RightRotate(Node<T> node);
}AVLTree
定义:
- AVL树是二叉搜索树, 即AVL树的所有节点的左子树的值小于根节点的值小于右子树的值
- AVL树的所有节点的左右子树高度差不超过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
27public class AVLNode<T extends Comparable<T>> extends Node<T> {
public AVLNode(T value) {
super(value);
}
public int getLevel() {
return level;
}
public void setLevel(int level) {
this.level = level;
}
public boolean isBalance() {
int left = 0, right = 0;
if (super.left != null) {
left = ((AVLNode<T>)super.left).level;
}
if (super.right != null) {
right = ((AVLNode<T>)super.right).level;
}
return Math.abs(left - right) <= 1;
}
private int level;
}AVL树代码
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
168public class AVLTree<T extends Comparable<T>> extends CanReBalanceBinarySearchTree<T> {
public boolean insert(T value) {
if (super.contain(value)) {
return false;
}
AVLNode<T> insertNode = new AVLNode<>(value);
insertNode.setLevel(1);
if (super.empty()) {
super.root = insertNode;
super.size++;
return true;
} else {
AVLNode<T> node = (AVLNode<T>) super.root;
while (node != null) {
if (node.compareTo(insertNode) > 0) {
if (node.getLeft() == null) {
node.setLeft(insertNode);
break;
} else {
node = (AVLNode<T>) node.getLeft();
}
} else {
if (node.getRight() == null) {
node.setRight(insertNode);
break;
} else {
node = (AVLNode<T>) node.getRight();
}
}
}
AVLNode<T> tmp = insertNode;
while (tmp != null) {
resetLevel(tmp);
tmp = (AVLNode<T>) tmp.getParent();
}
reBalance(insertNode);
this.size++;
return true;
}
}
public boolean remove(T value) {
if (!super.contain(value) || super.empty()) {
return false;
}
if (super.size == 1) {
super.size = 0;
super.root = null;
return true;
}
AVLNode<T> removeNode = (AVLNode<T>) super.find(value);
AVLNode<T> parent = (AVLNode<T>) removeNode.getParent();
if (removeNode.getLeft() == null || removeNode.getRight() == null) {
if (removeNode.getLeft() == null){
if (parent == null) {
super.root = removeNode.getRight();
} else {
if (removeNode == parent.getLeft()) {
parent.setLeft(removeNode.getRight());
} else {
parent.setRight(removeNode.getRight());
}
}
} else {
if (parent == null) {
super.root = removeNode.getLeft();
} else {
if (removeNode == parent.getLeft()) {
parent.setLeft(removeNode.getLeft());
} else {
parent.setRight(removeNode.getLeft());
}
}
}
this.size--;
AVLNode<T> tmp = parent;
while (tmp != null) {
resetLevel(tmp);
tmp = (AVLNode<T>) tmp.getParent();
}
reBalance(parent);
return true;
}
AVLNode<T> rightNodeMostLeft = (AVLNode<T>) removeNode.getRight();
if (rightNodeMostLeft.getLeft() != null) {
rightNodeMostLeft = (AVLNode<T>) rightNodeMostLeft.getLeft();
}
removeNode.setValue(rightNodeMostLeft.getValue());
parent = (AVLNode<T>) rightNodeMostLeft.getParent();
if (rightNodeMostLeft == removeNode.getRight()) {
removeNode.setRight(rightNodeMostLeft.getRight());
} else {
parent.setLeft(rightNodeMostLeft.getRight());
}
this.size--;
reBalance(parent);
return false;
}
protected void reBalance(Node<T> node) {
while (node != null) {
AVLNode<T> parent= (AVLNode<T>) node.getParent();
if (!((AVLNode<T>)node).isBalance()) {
int left = node.getLeft() == null ? 0 : ((AVLNode<T>)node.getLeft()).getLevel();
int right = node.getRight() == null ? 0 : ((AVLNode<T>)node.getRight()).getLevel();
if (left > right) {
if (node.getLeft().getLeft() != null) {
RightRotate(node);
} else {
LeftRotate((AVLNode<T>) node.getLeft());
RightRotate(node);
}
} else {
if (node.getRight().getRight() != null) {
LeftRotate(node);
} else {
RightRotate((AVLNode<T>) node.getRight());
LeftRotate(node);
}
}
}
node = parent;
}
}
private void resetLevel(AVLNode<T> node) {
node.setLevel(Math.max(node.getLeft() == null ? 0 : ((AVLNode<T>)node.getLeft()).getLevel(), node.getRight() == null ? 0 : ((AVLNode<T>)node.getRight()).getLevel()) + 1);
}
private void reset(AVLNode<T> node, AVLNode<T> parent, boolean isLeft, AVLNode<T> child) {
resetLevel(node);
resetLevel(child);
if (isLeft) {
parent.setLeft(child);
} else {
parent.setRight(child);
}
parent = (AVLNode<T>) child.getParent();
while (parent != null) {
resetLevel(parent);
parent = (AVLNode<T>) parent.getParent();
}
}
protected void LeftRotate(Node<T> node) {
AVLNode<T> parent = (AVLNode<T>) node.getParent();
boolean isLeft = parent.getLeft() == node;
AVLNode<T> rightNode = (AVLNode<T>) node.getRight();
node.setRight(rightNode.getLeft());
rightNode.setLeft(node);
reset((AVLNode<T>) node, (AVLNode<T>) parent, isLeft, (AVLNode<T>) rightNode);
}
protected void RightRotate(Node<T> node) {
AVLNode<T> parent = (AVLNode<T>) node.getParent();
boolean isLeft = parent.getLeft() == node;
AVLNode<T> leftNode = (AVLNode<T>) node.getLeft();
node.setLeft(leftNode.getRight());
leftNode.setRight(node);
reset((AVLNode<T>) node, (AVLNode<T>) parent, isLeft, (AVLNode<T>) leftNode);
}
}
RBTree
定义:
- 红黑树是二叉搜索树, 即红黑树的所有节点的左子树的值小于根节点的值小于右子树的值
- 红黑树的所有节点的左右子树的高度差不超过一倍
- 每个节点都有红色和黑色两种颜色
- 根节点和叶子节点的颜色是黑色
- 每条路径上的黑色节点个数相同
- 红色节点的子节点不能是红色
代码:
节点代码
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
32public class RBNode<T extends Comparable<T>> extends Node<T> {
public RBNode(T value) {
super(value);
}
public RBNode<T> getGrandParent() {
return super.getParent() == null ? null : (RBNode<T>) super.getParent().getParent();
}
public RBNode<T> getUncle() {
if (super.getParent() == null || super.getParent().getParent() == null) {
return null;
}
if (super.getParent() == this.getGrandParent().getLeft()) {
return (RBNode<T>) this.getGrandParent().getRight();
} else {
return (RBNode<T>) this.getGrandParent().getLeft();
}
}
public boolean isRed() {
return red;
}
public void setRed(boolean red) {
this.red = red;
}
private boolean red;
}RB树代码
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
152public class RBTree<T extends Comparable<T>> extends CanReBalanceBinarySearchTree<T> {
public boolean insert(T value) {
if (super.contain(value)) {
return false;
}
RBNode<T> insertNode = new RBNode<>(value);
if (super.root == null) {
insertNode.setRed(false);
super.root = insertNode;
super.size++;
return true;
}
insertNode.setRed(true);
RBNode<T> node = (RBNode<T>) super.root;
while (node != null) {
if (node.compareTo(insertNode) > 0) {
if (node.getLeft() == null) {
node.setLeft(insertNode);
this.size++;
reBalance(insertNode);
return true;
} else {
node = (RBNode<T>) node.getLeft();
}
} else {
if (node.getRight() == null) {
node.setRight(insertNode);
this.size++;
reBalance(insertNode);
return true;
} else {
node = (RBNode<T>) node.getRight();
}
}
}
return false;
}
public boolean remove(T value) {
if (!super.contain(value)) {
return false;
}
if (super.size == 1) {
super.size = 0;
super.root = null;
return true;
}
RBNode<T> removeNode = (RBNode<T>) super.find(value);
RBNode<T> parent = (RBNode<T>) removeNode.getParent();
if (removeNode.getLeft() == null) {
if (parent == null) {
this.root = removeNode.getRight();
} else {
if (removeNode == parent.getLeft()) {
parent.setLeft(removeNode.getRight());
} else {
parent.setRight(removeNode.getRight());
}
}
} else if (removeNode.getRight() == null) {
if (parent == null) {
this.root = removeNode.getLeft();
} else {
if (removeNode == parent.getLeft()) {
parent.setLeft(removeNode.getLeft());
} else {
parent.setRight(removeNode.getLeft());
}
}
} else {
RBNode<T> rightNodeMostLeft = (RBNode<T>) removeNode.getRight();
while (rightNodeMostLeft.getLeft() != null) {
rightNodeMostLeft = (RBNode<T>) rightNodeMostLeft.getLeft();
}
removeNode.setValue(rightNodeMostLeft.getValue());
if (rightNodeMostLeft == removeNode.getRight()) {
removeNode.setRight(rightNodeMostLeft.getRight());
}
}
throw new RuntimeException();
}
protected void reBalance(Node<T> node) {
RBNode<T> operatorNode = (RBNode<T>) node;
while (operatorNode != null) {
if (operatorNode.getParent() == null) {
operatorNode.setRed(false);
return;
}
if (((RBNode<T>)operatorNode.getParent()).isRed()) {
RBNode<T> uncleNode = operatorNode.getUncle();
if (uncleNode != null && uncleNode.isRed()) {
((RBNode<T>)operatorNode.getParent()).setRed(false);
uncleNode.setRed(false);
operatorNode.getGrandParent().setRed(true);
operatorNode = operatorNode.getGrandParent();
} else {
if (operatorNode == operatorNode.getParent().getRight()) {
operatorNode = (RBNode<T>) operatorNode.getParent();
LeftRotate(operatorNode);
} else {
((RBNode<T>) operatorNode.getParent()).setRed(false);
operatorNode.getGrandParent().setRed(true);
RBNode<T> tmp = operatorNode.getUncle();
if (operatorNode.getGrandParent().getLeft() != null) {
RightRotate(operatorNode.getGrandParent());
operatorNode = tmp;
} else {
operatorNode = operatorNode.getGrandParent();
}
}
}
} else {
break;
}
}
}
protected void LeftRotate(Node<T> node) {
RBNode<T> parent = (RBNode<T>) node.getParent();
boolean isLeft = parent.getLeft() == node;
RBNode<T> rightNode = (RBNode<T>) node.getRight();
node.setRight(rightNode.getLeft());
rightNode.setLeft(node);
if (isLeft) {
parent.setLeft(rightNode);
} else {
parent.setRight(rightNode);
}
}
protected void RightRotate(Node<T> node) {
RBNode<T> parent = (RBNode<T>) node.getParent();
boolean isLeft = parent.getLeft() == node;
RBNode<T> leftNode = (RBNode<T>) node.getLeft();
node.setLeft(leftNode.getRight());
leftNode.setRight(node);
if (isLeft) {
parent.setLeft(leftNode);
} else {
parent.setRight(leftNode);
}
}
}
SBTree
定义:
- SB树是二叉搜索树, 即SB树的所有节点的左子树的值小于根节点的值小于右子树的值
- SB树要求每棵子树的节点数量不能多余其节点叔叔所在树的节点数量
补充:
- AVL树是最平衡的二叉搜索树
- AVL树因为在每次插入或者删除节点时, 都可能调整平衡, 代价太大
- 红黑树和SB树都是在阉割AVL树的平衡性来达到降低调整频率的
操作:
- 所有平衡二叉树的操作都是基于两种最基本的旋转的
- 左旋: 根节点变为右子节点的左子节点
1
2
3
4
5
6
7[A] [C]
/ \ / \
[B] [C] ------> [A] [G]
/ \ / \ / \
[D] [E] [F] [G] [B] [F]
/ \
[D] [E] - 右旋: 根节点变为左子节点的右子节点
1
2
3
4
5
6
7[A] [B]
/ \ / \
[B] [C] ------> [D] [A]
/ \ / \ / \
[D] [E] [F] [G] [E] [C]
/ \
[F] [G]
插入
- AVL树在插入新节点的时候, 都会记录该节点属于哪一层, 通过这个层数来确定左右子树的高度差.
- 红黑树都会拥有自己父节点的指针, 以便旋转和染色的时候方便回溯.
删除
- 删除时, 可以使用左子树的最右节点代替待删除节点
- 删除时, 可以使用右子树的最左节点代替待删除节点
- 本质上就是寻找中序遍历的待删除节点的前驱或后继来代替待删除节点