在插入和删除结点时，要保证插入结点后不能使叶子结点之间的深度之差大于1，这样就能保证整棵树的深度最小，这就是AVL树解决BST搜索性能降低的策略。

但由于每次插入或删除结点后，都可能会破坏AVL的平衡，而要动态保证AVL的平衡需要很多螺旋操作，这些操作会影响整个数据结构的性能，除非是在树的结构变化特别少的情形下，否则AVL树平衡带来的搜索性能提升有可能还不足为了平衡树所带来的性能损耗。

那有没有绝对平衡的一种树呢？没有高度差也不会有平衡因子，没有平衡因子就不会调整旋转操作。2-3树正是一种绝对平衡的树，任意结点到它所有的叶子结点的深度都是相等的。

因此，引入了2-3树来提升效率。2-3树本质也是一种平衡搜索树，但2-3树已经不是一棵二叉树了，因为2-3树允许存在3这种结点，3-结点中可以存放两个元素(数据项)，并且可以有三个子结点。

【1】概述

① 2-结点

父结点结点含有一个元素(数据项)和两个子树（左右子树），左子树所有元素的值均小于它父结点，右子树所有元素的值均大于它父结点。

如下所示，均可以称之为2结点。

② 3-结点

父结点结点含有两个元素(数据项)和三个子树（左中右子树），左子树所有元素的值均小于它父结点，中子树所有元素的值都位于父结点两个元素之间，右子树所有元素的值均大于它父结点

③ 2-3树

为了满足任意结点到它所有的叶子结点的深度都是相等的特性，我们再构建子结点8和10，如下所示其就是一棵2-3树。

2-3树虽然不是二叉树但是其与满二叉树相似。高为h的2-3树包含的结点数大于等于高度为h的满二叉树的结点数，即至少有2^h-1个结点

④ 特性总结

一颗2-3树或为一颗空树，或有以下结点组成：

• 2-结点，含有一个元素和两个子树（左右子树），左子树所有元素的值均小于它父结点，右子树所有元素的值均大于它父结点；

• 3-结点，还有两个元素和三个子树（左中右子树），左子树所有元素的值均小于它父结点，中子树所有元素的值都位于父结点两个元素之间，右子树所有元素的值均大于它父结点；

• 子树也是空树、2-结点或者3-结点；

• 没有元素相等的结点。

• 任意结点到它所有的叶子结点的深度都是相等的

• 插入时永远不可能插入到一个空结点上

【2】23树查找

2-3树的查找类似二分搜索树(又名二叉搜索树，二叉排序树，BST)的查找，根据元素的大小来决定查找的方向。

要判断一个元素是否存在，我们先将待查找元素和根结点比较。如果它和其中任意一个相等，那查找命中，否则根据比较的结果来选择查找的方向是左孩子还是右孩子。

【3】23树插入

插入元素首先进行查找命中，若查找命中则不予插入此元素，如果需要支持重复的元素则将这个元素对象添加一个属性count。若查找未命中，则在叶子结点中插入这个元素。

空树的插入很简单，创建一个结点即可。如果不是空树，插入的情况分为下面4种：

• 向2-结点中插入元素
• 向一棵只含有一个3结点树中插入元素
• 向一个父结点为2-结点的3-结点中插入元素
• 向一个父结点为3-结点的3-结点中插入元素

插入时需要注意：

• 结点不可能插入到一个空结点，首先会考虑结点融合
• 如果结点数据项大于2(也就是一个4-结点)，那么融合后会进行分裂
• 分裂的过程要保证树的绝对平衡。
• 融合分裂指的是结点分裂然后中间结点向上与原先的父结点融合形成新的父结点
• 融合分裂可能会引起连锁反应

① 向2-结点中插入元素

也就是最基本的元素插入，结点只有一个数据项那么直接融合即可。

如下所示，插入结点3，那么其首先查找到结点4，然后与结点4融合。由于新结点是有两个数据项-34，不具备分裂的条件(结点数据项大于2才会分裂)。

② 向一棵只含有一个3结点树中插入元素

如下所示，此时再插入结点4。形成一个新结点345，其实一个4-结点，那么会触发分裂。4结点会成为新的父结点，3结点和5结点成为左右子结点。

③ 向一个父结点为2-结点的3-结点中插入元素

如下所示，向34/6/7构成的子树中插入元素5。那么会经过下面这几步：

• 34与5融合，变成一个4-结点，触发分裂为三个结点3、4、5
• 4上升为父结点与原先的父结点6融合，成46新的父结点-其是一个3-结点
• 结点3、5、7成为新父结点的三个子孩子
  

④ 向一个父结点为3-结点的3-结点中插入元素

如下所示插入结点2，此时会经过如下步骤：

• 查找到结点13，进行融合得到新结点123，其是4-结点；
• 123结点是一个4-结点，那么触发分裂为1、2、3结点；
• 分裂后的2结点上升与父结点46融合成为一个4-结点，246；1、3结点成为2结点的左右子结点
• 246结点进行分裂为三个结点2、4、6；
• 分裂后的4结点上升与8融合成为一个3-结点，48；5、7结点为6结点的左右子结点。

【4】23树删除

关于23树结点的删除是一个比插入更复杂的事情，网上查阅了诸多资料，但是没有找到完善的讲解与归纳。本文这里我们尝试总结一下，如有不当请指出。

23树结点的删除整体我们可以分为两类：叶子结点的删除和非叶子结点的删除。

① 叶子结点的删除

叶子结点的删除我们要考虑这样几个场景：

• ① 叶子结点是一个3-结点，这种是最简单的，直接删除即可。
• ② 叶子结点是一个2结点，但其兄弟结点是一个3结点；这种就要进行旋转(融合、分裂)；
• ③ 叶子结点是一个2结点，兄弟结点是一个2结点，但是父结点是一个3结点；这种情况会使得父结点与子结点交换或融合；
• ④ 叶子结点是一个2结点，兄弟结点与父结点都是2结点。这种情况是最麻烦的，为了维持绝对平衡需要降低整棵树的高度（也就是根结点将会发生变化）。

总结来看就是两种情况：

• 调整当前子树以维持高度不发生变化；
• 调整根结点以维持平衡，这时树的整体高度可能发生变化

① 叶子结点是一个3-结点

如下所示，我们删除结点1或者结点2。这种是最简单的，直接删除即可。

② 叶子结点是一个2结点，但其兄弟结点是一个3结点

如下所示，我们删除结点4。这种情况调整3-结点的兄弟结点与父结点即可维护当前子树的高度不发生变化。

③ 叶子结点是一个2结点，兄弟结点是一个2结点，但是父结点是一个3结点

如下所示，删除结点2。因为当前子树中有3-结点(父结点)，那么通过调整即可维持当前子树高度不发生变化。

④ 当前子树没有3-结点

也就是叶子结点是一个2结点，兄弟结点与父结点都是2结点。这时如果所有子树都没有3结点，那么树的高度肯定-1。如果树中有3结点，那么可以通过调整维持树的高度不发生变化。

第一种情况：树的高度不发生变化

如下所示，删除右子树中叶子结点8。那么对右侧来说高度肯定发生变化，但是左侧子树中有3结点。

• 尝试通过将叶子结点8的前驱结点7与8交换，然后删除8。
• 原先父结点7的前驱结点6作为新的父结点
• 调整左侧子树
  

第二种：树的高度发生变化

如下所示，我们删除结点3。由于整棵树都没有3结点，那么56结点融合为3结点，右侧子树进行左旋，9结点与根结点7融合，结点8作为中间结点。

② 删除非叶子结点

我们分两种情况分析：

• 当前子树有3结点，那么通过调整子树来维持高度不发生变化
• 当前子树没有3结点，这时就可能导致整棵树高度发生变化

第一种情况：当前子树有3结点，那么通过调整子树来维持高度不发生变化

当前子树有3结点，那么当前子树至少有四个元素。那么删除任意一个元素，都可以通过调整子树来维持树的高度不发生变化。

如下图所示，直接将删除结点（3）与其前驱结点(2)交换位置，然后删除目标结点3即可。

如下图所示，将删除结点(2)的后继结点与其前驱结点(1)融合。

第二种情况：当前子树没有3结点，这时就可能导致整棵树高度发生变化

这个要分两种情况：

• 当前子树没有3结点，但是整棵树中有3结点，那么高度不发生变化；
• 当前子树没有3结点，整棵树中也没有3结点，高度发生变化。

如上所示，删除右侧子树的父节点9。那么右侧子树是没有办法维持原先高度的。但是整棵子树中有3结点。那么通过调整是可以维持整棵树的高度不发生变化的。

• 删除父节点9，将其前驱结点8通过右旋交换位置；
• 8结点的前驱结点7(也就是根节点)作为8结点的左子节点；
• 原先根节点的前驱结点(6)作为新的根节点；
• 拆分3-结点(14)与父节点5形成一个新的子树。

当前子树没有3结点，整棵树中也没有3结点，高度发生变化。如下所示，删除父节点8,：

• 交换前驱结点7，然后删除8
• 结点7与10融合
• 左侧父节点4上升与根节点6融合成为3结点
• 1、5、7|10成为左、中、右三子节点。
  

参考博文：

动画 | 什么是2-3树？