之前分析了红黑树的删除，这里附上红黑树的完整版代码，包括查找、插入、删除等。删除后修复实现了两种算法，均比之前的更为简洁。一种是我自己的实现，代码非常简洁，行数更少；一种是Linux、Java等源码版本的实现，实现的略为复杂，但效率更高。两种算法经过测试，在百万级的数据上效率不分伯仲；1000万的数据中，我自己的实现比Linux内核版本的运行时间多2秒左右。
红黑树的插入相对简单，本文中的代码实现与Linux源码版本也略有差异，效率差别不大。
其他方法，如查找、遍历等，比较简单，不多做解释。遍历支持前序、中序、后序遍历。
在研究红黑树的过程中，为了彻底弄懂插入与删除，画了无数的图，以删除修复为例，根据父亲节点、兄弟节点、兄弟节点的左右子节点的空、红、黑的情况，穷举了36中情况，再进行归纳合并。而弄明白以后，发现是如此的简单；实现了多种写法，最后总结为两种最简洁的实现，并进行性能测试。还写了检查一棵树是否是红黑树的代码，将在下篇博客中发布。
至此，二叉树和红黑树研究完毕。代码如下：
1 import 'tree_node.dart';
2 import 'tree_exception.dart';
3 import 'traverse_order.dart';
4
5 class RBTree<E extends Comparable<E>> {
6 RBTNode<E> _root;
7 int _nodeNumbers;
8
9 RBTree() : _nodeNumbers = 0;
10
11 factory RBTree.from(Iterable<Comparable<E>> elements) {
12 var tree = RBTree<E>();
13 for (var e in elements) tree.insert(e);
14 return tree;
15 }
16
17 bool get isEmpty => _root == null;
18 int get nodeNumbers => _nodeNumbers;
19 RBTNode<E> get root => _root;
20
21 void clear() {
22 _root = null;
23 _nodeNumbers = 0;
24 }
25
26 bool contains(E value) => find(value) != null;
27
28 bool delete(E value) => _delete(value, _fixAfterDelete);
29
30 // the implement in Linux core.
31 bool quickDelete(E value) => _delete(value, _fixAfterDelete2);
32
33 RBTNode<E> find(E value) {
34 var current = _root;
35 while (current != null) {
36 var c = value.compareTo(current.value);
37 if (c == 0) break;
38 current = c < 0 ? current.left : current.right;
39 }
40 return current;
41 }
42
43 void insert(E value) {
44 var inserted = RBTNode<E>(value);
45 _insert(inserted);
46 _fixAfterInsert(inserted);
47 }
48
49 E get max {
50 if (isEmpty) throw TreeEmptyException();
51 var maxNode = _root;
52 while (maxNode.right != null) maxNode = maxNode.right;
53 return maxNode.value;
54 }
55
56 E get min {
57 if (isEmpty) throw TreeEmptyException();
58 return _minNode(_root).value;
59 }
60
61 void traverse(void f(E e), [TraverseOrder order = TraverseOrder.inOrder]) =>
62 _traverse(_root, order, f);
63
64 void _insert(RBTNode<E> inserted) {
65 RBTNode<E> p, c = _root;
66 while (c != null) {
67 p = c;
68 c = inserted.value.compareTo(c.value) <= 0 ? c.left : c.right;
69 }
70
71 if (p == null) {
72 _root = inserted;
73 } else if (inserted.value.compareTo(p.value) <= 0) {
74 p.left = inserted;
75 } else {
76 p.right = inserted;
77 }
78 inserted.parent = p;
79 _nodeNumbers++;
80 }
81
82 void _fixAfterInsert(RBTNode<E> node) {
83 while (_hasRedFather(node) && _hasRedUncle(node)) {
84 var g = _gparent(node);
85 g.left.paintBlack();
86 g.right.paintBlack();
87 g.paintRed();
88 node = g;
89 }
90
91 if (_hasRedFather(node)) {
92 var g = _gparent(node);
93 if (node.parent == g.left) {
94 if (node == node.parent.right) {
95 _rotateLeft(node.parent);
96 node = node.left;
97 }
98 _rotateRight(g);
99 } else {
100 if (node == node.parent.left) {
101 _rotateRight(node.parent);
102 node = node.right;
103 }
104 _rotateLeft(g);
105 }
106 node.parent.paintBlack();
107 g.paintRed();
108 }
109 _root.paintBlack();
110 }
111
112 bool _hasRedFather(RBTNode<E> node) =>
113 node.parent != null && node.parent.isRed;
114
115 bool _hasRedUncle(RBTNode<E> node) {
116 var gparent = _gparent(node);
117 var uncle = node.parent == gparent.left ? gparent.right : gparent.left;
118 return uncle != null && uncle.isRed;
119 }
120
121 RBTNode _gparent(RBTNode<E> node) => node.parent.parent;
122
123 bool _delete(E value, void _fix(RBTNode<E> p, bool isLeft)) {
124 var d = find(value);
125 if (d == null) return false;
126
127 if (d.left != null && d.right != null) {
128 var s = _successor(d);
129 d.value = s.value;
130 d = s;
131 }
132 var rp = d.left ?? d.right;
133 rp?.parent = d.parent;
134 if (d.parent == null)
135 _root = rp;
136 else if (d == d.parent.left)
137 d.parent.left = rp;
138 else
139 d.parent.right = rp;
140
141 if (rp != null)
142 rp.paintBlack();
143 else if (d.isBlack && d.parent != null)
144 _fix(d.parent, d.parent.left == null);
145
146 _nodeNumbers--;
147 return true;
148 }
149
150 RBTNode<E> _successor(RBTNode<E> d) =>
151 d.right != null ? _minNode(d.right) : d.left;
152
153 void _fixAfterDelete(RBTNode<E> p, bool isLeft) {
154 var c = isLeft ? p.right : p.left;
155 if (isLeft) {
156 if (c.isRed) {
157 p.paintRed();
158 c.paintBlack();
159 _rotateLeft(p);
160 c = p.right;
161 }
162 if (c.left != null && c.left.isRed) {
163 c.left.paint(p.color);
164 if (p.isRed) p.paintBlack();
165 _rotateRight(c);
166 _rotateLeft(p);
167 } else {
168 _rotateLeft(p);
169 if (p.isBlack) {
170 p.paintRed();
171 if (c.parent != null) _fixAfterDelete(c.parent, c == c.parent.left);
172 }
173 }
174 } else {
175 if (c.isRed) {
176 p.paintRed();
177 c.paintBlack();
178 _rotateRight(p);
179 c = p.left;
180 }
181 if (c.right != null && c.right.isRed) {
182 c.right.paint(p.color);
183 if (p.isRed) p.paintBlack();
184 _rotateLeft(c);
185 _rotateRight(p);
186 } else {
187 _rotateRight(p);
188 if (p.isBlack) {
189 p.paintRed();
190 if (c.parent != null) _fixAfterDelete(c.parent, c == c.parent.left);
191 }
192 }
193 }
194 }
195
196 // the implement in Linux core.
197 void _fixAfterDelete2(RBTNode<E> p, bool isLeft) {
198 var c = isLeft ? p.right : p.left;
199 if (isLeft) {
200 if (c.isRed) {
201 p.paintRed();
202 c.paintBlack();
203 _rotateLeft(p);
204 c = p.right;
205 }
206 if ((c.left != null && c.left.isRed) ||
207 (c.right != null && c.right.isRed)) {
208 if (c.right == null || c.right.isBlack) {
209 _rotateRight(c);
210 c = p.right;
211 }
212 c.paint(p.color);
213 p.paintBlack();
214 c.right.paintBlack();
215 _rotateLeft(p);
216 } else {
217 c.paintRed();
218 if (p.isRed)
219 p.paintBlack();
220 else if (p.parent != null)
221 _fixAfterDelete2(p.parent, p == p.parent.left);
222 }
223 } else {
224 if (c.isRed) {
225 p.paintRed();
226 c.paintBlack();
227 _rotateRight(p);
228 c = p.left;
229 }
230 if ((c.left != null && c.left.isRed) ||
231 (c.right != null && c.right.isRed)) {
232 if (c.left == null || c.left.isBlack) {
233 _rotateLeft(c);
234 c = p.left;
235 }
236 c.paint(p.color);
237 p.paintBlack();
238 c.left.paintBlack();
239 _rotateRight(p);
240 } else {
241 c.paintRed();
242 if (p.isRed)
243 p.paintBlack();
244 else if (p.parent != null)
245 _fixAfterDelete2(p.parent, p == p.parent.left);
246 }
247 }
248 }
249
250 void _rotateLeft(RBTNode<E> node) {
251 var r = node.right, p = node.parent;
252 r.parent = p;
253 if (p == null)
254 _root = r;
255 else if (p.left == node)
256 p.left = r;
257 else
258 p.right = r;
259
260 node.right = r.left;
261 r.left?.parent = node;
262 r.left = node;
263 node.parent = r;
264 }
265
266 void _rotateRight(RBTNode<E> node) {
267 var l = node.left, p = node.parent;
268 l.parent = p;
269 if (p == null)
270 _root = l;
271 else if (p.left == node)
272 p.left = l;
273 else
274 p.right = l;
275
276 node.left = l.right;
277 l.right?.parent = node;
278 l.right = node;
279 node.parent = l;
280 }
281
282 RBTNode<E> _minNode(RBTNode<E> r) => r.left == null ? r : _minNode(r.left);
283
284 void _traverse(RBTNode<E> s, TraverseOrder order, void f(E e)) {
285 if (s == null) return;
286 switch (order) {
287 case TraverseOrder.inOrder:
288 _traverse(s.left, order, f);
289 f(s.value);
290 _traverse(s.right, order, f);
291 break;
292 case TraverseOrder.preOrder:
293 f(s.value);
294 _traverse(s.left, order, f);
295 _traverse(s.right, order, f);
296 break;
297 case TraverseOrder.postOrder:
298 _traverse(s.left, order, f);
299 _traverse(s.right, order, f);
300 f(s.value);
301 break;
302 default:
303 break;
304 }
305 }
306 }
请发表评论