红黑树插入与删除完整代码（dart语言实现）
之前分析了红黑树的删除，这里附上红黑树的完整版代码，包括查找、插入、删除等。删除后修复实现了两种算法，均比之前的更为简洁。一种是我自己的实现，代码非常简洁，行数更少；一种是Linux、Java等源码版本的实现，实现的略为复杂，但效率更高。两种算法经过测试，在百万级的数据上效率不分伯仲；1000万的数据中，我自己的实现比Linux内核版本的运行时间多2秒左右。
红黑树的插入相对简单，本文中的代码实现与Linux源码版本也略有差异，效率差别不大。
SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。其他方法，如查找、遍历等，比较简单，不多做解释。遍历支持前序、中序、后序遍历。
在研究红黑树的过程中，为了彻底弄懂插入与删除，画了无数的图，以删除修复为例，根据父亲节点、兄弟节点、兄弟节点的左右子节点的空、红、黑的情况，穷举了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 }
更多精彩
