数据结构系列之2-3树的插入、查找、删除和遍历完整版代码实现（dart语言实现）
弄懂了二叉树以后，再来看2-3树。网上、书上看了一堆文章和讲解，大部分是概念，很少有代码实现，尤其是删除操作的代码实现。当然，因为2-3树的特性，插入和删除都是比较复杂的，因此经过思考，独创了删除时分支收缩、重新展开的算法，保证了删除后树的平衡和完整。该算法相比网上的实现相比，相对比较简洁；并且，重要的是，该删除算法可以推广至2-3-4树，甚至是多叉树。
SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。
————声明：原创，转载请说明来源————
一、2-3树的定义
2-3树是最简单的B-树（或-树）结构，其每个非叶节点都有两个或三个子女，而且所有叶都在统一层上。2-3树不是二叉树，其节点可拥有3个孩子。不过，2-3树与满二叉树相似。若某棵2-3树不包含3-节点，则看上去像满二叉树，其所有内部节点都可有两个孩子，所有的叶子都在同一级别。另一方面，2-3树的一个内部节点确实有3个孩子，故比相同高度的满二叉树的节点更多。高为h的2-3树包含的节点数大于等于高度为h的满二叉树的节点数，即至少有2^h-1个节点。换一个角度分析，包含n的节点的2-3树的高度不大于[log2(n+1)](即包含n个节点的二叉树的最小高度)。
下图显示高度为3的2-3树。包含两个孩子的节点称为2-节点，二叉树中的节点都是2-节点；包含三个孩子的节点称为3-节点。
（图片来自网络）
先来看2-3树的节点的定义：
1 class TerNode<E extends Comparable<E>> { 2 static final int capacity = 2; 3 List<E> items; 4 List<TerNode<E>> branches; 5 TerNode<E> parent; 6
7 factory TerNode(List<E> elements) { 8 if (elements.length > capacity) throw StateError('too many elements.'); 9 return TerNode._internal(elements); 10 } 11
12 TerNode._internal(List<E> elements) 13 : items = [], 14 branches = [] { 15 items.addAll(elements); 16 } 17
18 int get size => items.length; 19 bool get isOverflow => size > capacity; 20 bool get isLeaf => branches.isEmpty; 21 bool get isNotLeaf => !isLeaf; 22
23 bool contains(E value) => items.contains(value); 24 int find(E value) => items.indexOf(value); 25
26 String toString() => items.toString(); 27 }
2-3树的定义：
1 class TernaryTree<E extends Comparable<E>> { 2 TerNode<E> _root; 3 int _elementsCount; 4
5 factory TernaryTree.of(Iterable<Comparable<E>> elements) { 6 var tree = TernaryTree<E>(); 7 for (var e in elements) tree.insert(e); 8 return tree; 9 } 10
11 TernaryTree() : _elementsCount = 0; 12
13 // ...
14
15 }
二、插入算法
首先，2-3树的插入，都是在叶子上完成的。首先定位查找I的操作的叶子，然后将新的元素插入至对应节点。插入后，需要判断是否需要修复，如果当前节点的元素个数大于2，则需要分裂；该节点分裂为三个节点，左、右元素为两个新的叶子节点，中间元素成为新的父节点；然后判断是否需要吸收新的父节点；递归向上，直至满足条件或直至根节点。
插入操作代码如下：
1 void insert(E value) { 2 var c = root, i = 0; 3 while (c != null) { 4 i = 0; 5 while (i < c.size && c.items[i].compareTo(value) < 0) i++; 6 if (i < c.size && c.items[i] == value) return; 7 if (c.isLeaf) break; 8 c = c.branches[i]; 9 } 10 if (c != null) { 11 c.items.insert(i, value); 12 if (c.isOverflow) _fixAfterIns(c); 13 } else { 14 _root = TerNode([value]); 15 } 16 _elementsCount++; 17 }
注意 该行代码，判断是否需要修复：
1 if (c.isOverflow) _fixAfterIns(c);
如果需要修复，则进行节点分裂、吸收，递归至根节点或不再溢出的节点为止，修复代码如下：
1 void _fixAfterIns(TerNode<E> c) { 2 while (c != null && c.isOverflow) { 3 var t = _split(c); 4 c = t.parent != null ? _absorb(t) : null; 5 } 6 } 7
8 TerNode<E> _split(TerNode<E> c) { 9 var mid = c.size ~/ 2, 10 l = TerNode._internal(c.items.sublist(0, mid)), 11 nc = TerNode._internal(c.items.sublist(mid, mid + 1)), 12 r = TerNode._internal(c.items.sublist(mid + 1)); 13 nc.branches.addAll([l, r]); 14 l.parent = r.parent = nc; 15
16 nc.parent = c.parent; 17 if (c.parent != null) { 18 var i = 0; 19 while (c.parent.branches[i] != c) i++; 20 c.parent.branches[i] = nc; 21 } else { 22 _root = nc; 23 } 24 if (c.isNotLeaf) { 25 l.branches 26 ..addAll(c.branches.getRange(0, mid + 1)) 27 ..forEach((b) => b.parent = l); 28 r.branches 29 ..addAll(c.branches.getRange(mid + 1, c.branches.length)) 30 ..forEach((b) => b.parent = r); 31 } 32 return nc; 33 } 34
35 TerNode<E> _absorb(TerNode<E> c) { 36 var i = 0, p = c.parent; 37 while (p.branches[i] != c) i++; 38 p.items.insertAll(i, c.items); 39 p.branches.replaceRange(i, i + 1, c.branches); 40 c.branches.forEach((b) => b.parent = p); 41 return p; 42 }
三、查找算法
查找实现比较简单，因为插入操作时，其实已经先进行了查找。代码如下：
1 TerNode<E> find(E value) { 2 var c = root; 3 while (c != null) { 4 var i = 0; 5 while (i < c.size && c.items[i].compareTo(value) < 0) i++; 6 if (i < c.size && c.items[i] == value) break; 7 c = c.isNotLeaf ? c.branches[i] : null; 8 } 9 return c; 10 }
四、删除算法
删除算法是最复杂的。
首先，为了降低复杂度，我们采用类似二叉树或红黑树一样的算法，如果待删除的元素存在且为非叶子节点的话，则用后继的叶子节点的值替代要删除的节点元素。此时则将删除问题转移到了叶子节点上，这样避免了孩子分支的处理。
其次，删除元素。删除后，判断是否需要修复。如果节点删除后不为空，则不需要；否则就需要修复。修复的核心思路是，将该节点的所有兄弟节点全部收缩至父节点，并记录收缩的次数；然后判断父节点的元素数量是否足够展开为一颗最小的平衡二叉树，如果不够，继续递归向上收缩，直至够了为止，或者到达根节点。如果倒达了根节点，则将树的高度减 1 ，进行展开。
如何判断一个节点的元素数量，满足展开为一颗最小的平衡二叉树？其实有个最简单的算法，一颗平衡二叉树的高度和元素个数，有如下规律：
高度为 1： 元素个数为 1 ，2^1 - 1 ；
高度为 2：元素个数为 3 ，2^2 - 1 ；
……
高度为 h: 元素个数为 2^h -1 ；
父节点收缩后重新展开，需要将多余的节点元素修剪掉，这些多余的节点元素，后续在插入到这棵树上即可。
删除代码如下：
1 bool delete(E value) { 2 var d = find(value); 3 if (d == null) return false; 4 var i = d.find(value); 5 if (d.isNotLeaf) { 6 var s = _successor(d.branches[i + 1]); 7 d.items[i] = s.items[0]; 8 d = s; 9 i = 0; 10 } 11 d.items.removeAt(i); 12 _elementsCount--; 13 if (d.items.isEmpty) _fixAfterDel(d); 14 return true; 15 }
查找后继节点代码如下：
1 TerNode<E> _successor(TerNode<E> p) { 2 while (p.isNotLeaf) p = p.branches[0]; 3 return p; 4 }
修复代码如下：
1 void _fixAfterDel(TerNode<E> d) { 2 if (d == root) { 3 _root = null; 4 } else { 5 var ct = 0; 6 while (d.size < (1 << ct + 1) - 1 && d.parent != null) { 7 _collapse(d.parent); 8 d = d.parent; 9 ct++; 10 } 11 // if (d.size < (1 << ct + 1) - 1) ct--;
12 if (d == root) ct--; 13 var rest = _prune(d, (1 << ct + 1) - 1); 14 _expand(d, ct); 15 for (var e in rest) insert(e); 16 } 17 }
父节点塌缩孩子分支的代码如下，这里要注意，因为在修复时是递归向上塌缩的，因此，塌缩时需要递归塌缩父节点的所有分支，注意父节点p的元素、分支的处理：
1 void _collapse(TerNode<E> p) { 2 if (p.isLeaf) return; 3 for (var i = p.branches.length - 1; i >= 0; i--) { 4 _collapse(p.branches[i]); 5 p.items.insertAll(i, p.branches[i].items); 6 } 7 p.branches.clear(); 8 }
塌缩后，在重新展开之前，需要修剪掉多余的元素。因为修剪掉的元素后续还是要插入到树中的，因此，保留的元素要尽量的居中，以避免重新插入时产生过多的分裂动作。代码如下：
1 List<E> _prune(TerNode<E> d, int least) { 2 var t = d.size ~/ least, rest = <E>[]; 3 if (t < 2) { 4 rest.addAll(d.items.getRange(least, d.size)); 5 d.items.removeRange(least, d.size); 6 } else { 7 var list = <E>[]; 8 for (var i = 0; i < d.size; i++) { 9 if (i % t == 0 && list.length < least) 10 list.add(d.items[i]); 11 else
12 rest.add(d.items[i]); 13 } 14 d.items = list; 15 } 16 _elementsCount -= rest.length; 17 return rest; 18 }
重新展开的代码如下，其实就是节点的递归向下分裂：
1 void _expand(TerNode<E> p, int ct) { 2 if (ct == 0) return; 3 p = _split(p); 4 for (var b in p.branches) _expand(b, ct - 1); 5 }
删除操作至此完成。
最后，给一个判断树的高度的代码：
1 int get height { 2 var h = 0, c = root; 3 while (c != null) { 4 h++; 5 c = c.isNotLeaf ? c.branches[0] : null; 6 } 7 return h; 8 }
那么这些操作，是否每一步的插入或删除完成后，树仍然满足是一颗2-3树呢？测试验证代码如下：
List<E> a可以随机生成一个千万级的数组进行测试。如果要观看每一步的输出，把 print 前的注释拿掉即可。经过上亿次的验证，以上代码正确。
注意，dart 验证时，如果为非debug模式，则需要在terminal中加入 --enable-asserts参数，以打开assert开关。
1 void ternaryTest<E extends Comparable<E>>(List<E> a) { 2 var tree = TernaryTree.of(a); 3 // print('check result: ${check(tree)}');
4 check(tree); 5 // print('-------------------'); 6 // print('a.lenght: ${a.length}, tree.elementsCount: ${tree.elementsCount}'); 7 // print('root: ${tree.root} height: ${tree.height}'); 8 // stdin.readLineSync(); 9 // print('-------------------'); 10 // print('start to $i times ternary deleting test...');
11 for (var e in a) { 12 // print('-------------------'); 13 // print('delete: $e');
14 tree.delete(e); 15 // print('-------------------'); 16 // print('tree.elementsCount: ${tree.elementsCount}'); 17 // print('new root: ${tree.root} height: ${tree.height}'); 18 // print('check result: ${check(tree)}');
19 check(tree); 20 } 21 } 22
23 bool check(TernaryTree tree) { 24 if (!tree.isEmpty) assert(tree.height == _walk(tree.root)); 25 return true; 26 } 27
28 int _walk(TerNode r) { 29 assert(!r.isOverflow); 30 for (var i = 0; i + 1 < r.size; i++) 31 assert(r.items[i].compareTo(r.items[i + 1]) < 0); 32
33 if (r.isLeaf) return 1; 34 assert(r.size + 1 == r.branches.length); 35 var heights = <int>[]; 36 for (var b in r.branches) heights.add(_walk(b)); 37 for (var h in heights) assert(h == heights.first); 38 return heights.first + 1; 39 }
本来准备结束了，发现忘了给遍历函数了：
1 void traverse(void func(List<E> items)) { 2 if (!isEmpty) _traverse(_root, func); 3 }
1 void _traverse(TerNode<E> r, void f(List<E> items)) { 2 f(r.items); 3 for (var b in r.branches) _traverse(b, f); 4 }
