数据结构系列之2-3-4树的插入、查找、删除和遍历完整版源代码实现与分析（dart语言实现）
本文属于原创，转载请注明来源。
在上一篇博文中，详细介绍了2-3树的操作（具体地址：https://www.cnblogs.com/outerspace/p/10861488.html），那么对于更多教科书上更为普遍的2-3-4树，在这里也给出 树的定义、节点的定义、插入、查找、删除和遍历等操作的源代码实现。
SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。关于2-3-4树的文字定义，网上很多，可自行百度，这里不再重复论述。但看了很多博文，关于插入等操作的实现较多，基本上没有实现删除操作的。因此本博文给出完整版的2-3-4树的插入、删除、查找及遍历等源代码。
另，2-3-4树代码的实现，与2-3树非常类似，故关于代码的分析，请参考2-3树（https://www.cnblogs.com/outerspace/p/10861488.html）的介绍，这里仅给出简要说明。
如果节点允许的最大元素数量超过3个，非叶子节点最大孩子数量超过4个，就成了多叉树，后续有机会分享一下一个关于8叉树的实现。
本代码由dart语言实现，关于dart，一门类似Java、JavaScript的语言，也是现在比较流行的flutter的后台语言，有兴趣的同学可以去dart官网了解：
https://dart.dev
闲话少说，上代码。
1 // 树的定义 2-3-4树
2 class QuaternaryTree<E extends Comparable<E>> { 3 QuaterNode<E> _root; 4 int _elementsCount; 5
6 factory QuaternaryTree.of(Iterable<Comparable<E>> elements) { 7 var tree = QuaternaryTree<E>(); 8 for (var e in elements) tree.insert(e); 9 return tree; 10 } 11
12 QuaternaryTree() : _elementsCount = 0; 13
14 int get elementsCount => _elementsCount; 15 QuaterNode<E> get root => _root; 16
17 // 计算树高
18 int get height { 19 var h = 0, c = root; 20 while (c != null) { 21 h++; 22 c = c.isNotLeaf ? c.branches[0] : null; 23 } 24 return h; 25 } 26
27 bool get isEmpty => _root == null; 28
29 bool contains(E value) => find(value) != null; 30
31 // 查找树中是否存在某个值 32 // 若找到，返回包含此值的树节点，否则返回null
33 QuaterNode<E> find(E value) { 34 var c = root; 35 while (c != null) { 36 var i = 0; 37 while (i < c.size && c.items[i].compareTo(value) < 0) i++; 38 if (i < c.size && c.items[i] == value) break; 39 c = c.isNotLeaf ? c.branches[i] : null; 40 } 41 return c; 42 } 43
44 // 插入新的值，如果值已经存在，则不做任何操作 45 // 插入始终在叶子节点进行
46 void insert(E value) { 47 var c = root, i = 0; 48 while (c != null) { 49 i = 0; 50 while (i < c.size && c.items[i].compareTo(value) < 0) i++; 51 if (i < c.size && c.items[i] == value) return; 52 if (c.isLeaf) break; 53 c = c.branches[i]; 54 } 55 if (c != null) { 56 c.items.insert(i, value); 57
58 // 判断插入后是否需要修复
59 if (c.isOverflow) _fixAfterIns(c); 60 } else { 61 _root = QuaterNode([value]); 62 } 63 _elementsCount++; 64 } 65
66 // 删除指定值
67 bool delete(E value) { 68 // 首先查找该值
69 var d = find(value); 70 // 若不存在，直接返回
71 if (d == null) return false; 72
73 // 查找该值在节点中的索引顺序
74 var i = d.find(value); 75
76 // 如果节点不是叶子节点，则用后继节点的值替代该值 77 // 这样删除操作将转移为删除叶子节点的值
78 if (d.isNotLeaf) { 79 var s = _successor(d.branches[i + 1]); 80 d.items[i] = s.items[0]; 81 d = s; 82 i = 0; 83 } 84 d.items.removeAt(i); 85 _elementsCount--; 86
87 // 根据2-3-4树的定义，节点不能为空，因此判断删除后是否需要修复
88 if (d.items.isEmpty) _fixAfterDel(d); 89 return true; 90 } 91
92 // 遍历树
93 void traverse(void func(List<E> items)) { 94 if (!isEmpty) _traverse(_root, func); 95 } 96
97 // 插入修复 98 // 注意，插入修复时，采用节点分裂的形式进行修复； 99 // 分裂出来的新的父节点需要被上层节点吸收（如果存在上层节点的话）
100 void _fixAfterIns(QuaterNode<E> c) { 101 while (c != null && c.isOverflow) { 102 var t = _split(c); 103 c = t.parent != null ? _absorb(t) : null; 104 } 105 } 106
107 // 节点分裂，由于分裂->吸收，可能会递归分裂； 108 // 因此需要注意根节点的更新判断以及子节点的处理；
109 QuaterNode<E> _split(QuaterNode<E> c) { 110 var mid = c.size ~/ 2, 111 l = QuaterNode._internal(c.items.sublist(0, mid)), 112 nc = QuaterNode._internal(c.items.sublist(mid, mid + 1)), 113 r = QuaterNode._internal(c.items.sublist(mid + 1)); 114 nc.branches.addAll([l, r]); 115 l.parent = r.parent = nc; 116
117 nc.parent = c.parent; 118 if (c.parent != null) { 119 var i = 0; 120 while (c.parent.branches[i] != c) i++; 121 c.parent.branches[i] = nc; 122 } else { 123 _root = nc; 124 } 125 if (c.isNotLeaf) { 126 l.branches 127 ..addAll(c.branches.getRange(0, mid + 1)) 128 ..forEach((b) => b.parent = l); 129 r.branches 130 ..addAll(c.branches.getRange(mid + 1, c.branches.length)) 131 ..forEach((b) => b.parent = r); 132 } 133 return nc; 134 } 135
136 // 上层节点吸收新分裂出来的节点，以保持树的平衡
137 QuaterNode<E> _absorb(QuaterNode<E> c) { 138 var i = 0, p = c.parent; 139 while (p.branches[i] != c) i++; 140 p.items.insertAll(i, c.items); 141 p.branches.replaceRange(i, i + 1, c.branches); 142 c.branches.forEach((b) => b.parent = p); 143 return p; 144 } 145
146 // 查找后继节点
147 QuaterNode<E> _successor(QuaterNode<E> p) { 148 while (p.isNotLeaf) p = p.branches[0]; 149 return p; 150 } 151
152 // 删除修复
153 void _fixAfterDel(QuaterNode<E> d) { 154 if (d == root) { 155 _root = null; 156 } else { 157 var ct = 0; 158 while (d.size < (1 << ct + 1) - 1 && d.parent != null) { 159 // 塌缩父节点
160 _collapse(d.parent); 161 d = d.parent; 162 ct++; 163 } 164
165 // 如果塌缩到了树的根，则树高减1 166 // if (d.size < (1 << ct + 1) - 1) ct--;
167 if (d == root) ct--; 168
169 // 修剪多余的值
170 var rest = _prune(d, (1 << ct + 1) - 1); 171
172 // 重新展开
173 _expand(d, ct); 174
175 // 将刚才修剪掉的多余的值重新插入树
176 for (var e in rest) insert(e); 177 } 178 } 179
180 // 树的塌缩函数，注意递归塌缩
181 void _collapse(QuaterNode<E> p) { 182 if (p.isLeaf) return; 183 for (var i = p.branches.length - 1; i >= 0; i--) { 184 _collapse(p.branches[i]); 185 p.items.insertAll(i, p.branches[i].items); 186 } 187 p.branches.clear(); 188 } 189
190 // 修剪，保留满足展开为满二叉树的最小数量的值
191 List<E> _prune(QuaterNode<E> d, int least) { 192 var t = d.size ~/ least, rest = <E>[]; 193 if (t < 2) { 194 rest.addAll(d.items.getRange(least, d.size)); 195 d.items.removeRange(least, d.size); 196 } else { 197 // 跳跃修剪，以保证二次插入时分裂的次数较少
198 var list = <E>[]; 199 for (var i = 0; i < d.size; i++) { 200 if (i % t == 0 && list.length < least) 201 list.add(d.items[i]); 202 else
203 rest.add(d.items[i]); 204 } 205 d.items = list; 206 } 207 _elementsCount -= rest.length; 208 return rest; 209 } 210
211 // 递归展开修剪后的节点，ct代表展开的层数或高度
212 void _expand(QuaterNode<E> p, int ct) { 213 if (ct == 0) return; 214 p = _split(p); 215 for (var b in p.branches) _expand(b, ct - 1); 216 } 217
218 void _traverse(QuaterNode<E> r, void f(List<E> items)) { 219 f(r.items); 220 for (var b in r.branches) _traverse(b, f); 221 } 222 } 223
224 class QuaterNode<E extends Comparable<E>> { 225 static final int capacity = 3; 226 List<E> items; 227 List<QuaterNode<E>> branches; 228 QuaterNode<E> parent; 229
230 factory QuaterNode(List<E> elements) { 231 if (elements.length > capacity) throw StateError('too many elements.'); 232 return QuaterNode._internal(elements); 233 } 234
235 QuaterNode._internal(List<E> elements) 236 : items = [], 237 branches = [] { 238 items.addAll(elements); 239 } 240
241 int get size => items.length; 242 bool get isOverflow => size > capacity; 243 bool get isLeaf => branches.isEmpty; 244 bool get isNotLeaf => !isLeaf; 245
246 bool contains(E value) => items.contains(value); 247 int find(E value) => items.indexOf(value); 248
249 String toString() => items.toString(); 250 }
-end-
更多精彩
