什么是2-3树

前言

前面的文章我们已经学习了二叉搜索树和平衡二叉搜索树AVL树，今天我们再来了解一种新的平衡树2–3树，2–3树由约翰·霍普克洛夫特于1970年发明，在计算机科学中，2–3树是一种树型数据结构，内部节点（存在子节点的节点）要么有2个孩子和1个数据元素，要么有3个孩子和2个数据元素，叶子节点没有孩子，并且有1个或2个数据元素，2-3树的平均时间复杂度为O（logN），空间复杂度为O（N），注意严格的说2-3树的性能是在O（log3N）和O（log2N）之间的，因为大O复杂度表示通常会忽略系数项。

前面的文章提到过的二叉树，每个节点的孩子个数最多的是2个，并且每个节点只有一个值，而2-3树的节点的孩子个数只能是2个或者3个，这是一种多路树的结构，类似的结构还有2-3-4树，B+树等，多路树的存在除了支持树的平衡外，还可以降低树的高度，从而让搜索，插入，删除的性能有所提升，但与此对应的是程序的编码会变得更加复杂，这也是2-3树或者2-3-4树，在开源框架或日常开发中并不如AVL树和红黑树使用频繁的原因，但B+树除外，因为B+树是特殊优化后的多路查找树，是专门为数据库结合磁盘文件系统定制的。

2-3树的性质

（1）每个节点可以拥有2个或者3个孩子节点，当父节点的值只有一个时，节点的孩子个数有2个，当父节点的值有2个时，节点的孩子个数有3个。

（2）所有的叶子节点都处于同一高度

如图：

（3）父节点是一个值的时候，左孩子的值小于父节点，右孩子的值大于父节点，父节点是2个值，比如记为S , L的时候，孩子节点有3个，分别是左，中，右，左边小于父节点S的值，中间的值大于S，小于L，右边节点的值大于L，如下图：

2-3树 VS 二叉搜索树

同样的一组数据，在2-3树和二叉搜索树里面的对比如下：

可以看到2-3树的节点分布非常均匀，且叶子节点的高度一致，并且如果这里即使是AVL树，那么树的高度也比2-3树高，而高度的降低则可以提升增删改的效率。

2-3树的插入

为了保持平衡性，2-3树的插入如果破坏了平衡性，那么树本身会产生分裂和合并，然后调整结构以维持平衡性，这一点和AVL树为了保持平衡而产生的节点旋转的作用一样，2-3树的插入分裂有几种情况如下：（1）情况一：叶子节点的插入调整，规律是叶子的中间值上升，然后左右值分裂，如下图：

（2）情况二：非叶子节点的调整，大体上与叶子节点的调整一致，不同的是，非叶子节点的孩子节点的值也需要重新分裂，如下图：

（3）情况三：必要的时候为了维持平衡性，会新产生一个root节点，如下图：

2-3树的删除

2-3树节点的删除也会破坏平衡性，同样树本身也会产生分裂和合并，如下：

节点的删除，与二叉搜索树的删除类似，不同的是2-3树会寻找中序的后继节点来替换要删除的节点的值，然后再删除替换的值：

结果如下：

与插入类似，删除的过程中root节点的值可能会被调整到新的节点，而原root节点就会变成空节点，从而需要删除，如下：

删除的过程，也是非常复杂的，涉及到节点的分裂，合并，重分布，删除等操作，这里不再详细描述。

关于2-3-4树

2-3-4树与2-3树类似，只不过当父节点的值是3的时候，节点的孩子个数可以有4个，如下：

2-3-4树可以再次降低的树的高度，但是对应的编码会更加复杂，尤其是在插入和删除之后，所以常常会被容易实现和理解的红黑树代替，这里不再过多介绍。感兴趣的朋友可以自行查询资料学习。

总结

本篇文章，主要介绍了2-3树相关的知识，2-3树，2-3-4树以及B树都不是二叉树，但与二叉树的大致特点是类似的，它们是一种平衡的多路查找树，节点的孩子个数可以允许多于2个，虽然高度降低了，但编码相对复杂，尤其是考虑维护树的平衡性的操作，带来的好处就是可以提升查询的性能，算是各有利弊，在工程项目中通常会权衡选择。