2-3 树
2–3树是一种树型数据结构，内部节点（存在子节点的节点）要么有2个孩子和1个数据元素，要么有3个孩子和2个数据元素，叶子节点没有孩子，并且有1个或2个数据元素。
2–3树由约翰·霍普克洛夫特于1970年发明。
2–3树和AA树是等距同构的，意味着它们是同一种数据结构。
换句话说，对于每个2–3树，都至少有1个AA树和它的元素排列是相同的。
2–3树是平衡树，意味着右边，左边，中间的子树的元素数量都是相同或接近的。
定义
（1）2-3 树要么为空要么具有以下性质：
（2）对于 2- 节点，和普通的 BST 节点一样，有一个数据域和两个子节点指针，两个子节点要么为空，要么也是一个2-3树，当前节点的数据的值要大于左子树中所有节点的数据，要小于右子树中所有节点的数据。
（3）对于 3- 节点，有两个数据域 a 和 b 和三个子节点指针，左子树中所有的节点数据要小于a，中子树中所有节点数据要大于 a 而小于 b ，右子树中所有节点数据要大于 b 。
例如图 2.1 所示的树为一棵 2-3 树：
性质
性质：
（1）对于每一个结点有 1 或者 2 个关键码。
（2）当节点有一个关键码的时，节点有 2 个子树。
（3）当节点有 2 个关键码时，节点有 3 个子树。
（4）所有叶子点都在树的同一层。
2-3 树查找
2-3 树的查找类似二叉搜索树的查找过程，根据键值的比较来决定查找的方向。
例如在图 2.1 所示的 2-3 树中查找键为H的节点：
例如在图 2.1 所示的 2-3 树中查找键为 B 的节点：
2-3 树插入
插入
在树的插入之前需要对带插入的节点进行一次查找操作，若树中已经有此节点则不予插入，若没有查找到此节点则记录未命中查找结束时访问的最后一个节点。
空树的插入最简单，创建一个节点即可，这里不予赘述。
对于非空树插入主要分为 4 种情况：
（1）向 2- 节点中插入新节点
（2）向一棵只含 3- 节点的树中插入新节点
（3）向一个父节点为 2- 节点的 3- 节点中插入新节点
（4）向一个父节点为 3- 节点的 3- 节点中插入新节点
向2-节点中插入新节点
操作步骤：如果未命中查找结束于一个 2-节点，直接将 2- 节点替换为一个 3- 节点，并将要插入的键保存在其中。
图解：
向一棵只含 3- 节点的树中插入新节点
操作步骤：先临时将新键存入唯一的 3- 节点中，使其成为一个 4- 节点，再将它转化为一颗由 3 个 2- 节点组成的 2-3 树，分解后树高会增加 1。
图解：
向一个父节点为 2- 节点的 3- 节点中插入新节点
操作步骤：先构造一个临时的 4- 节点并将其分解，分解时将中键移动到父节点中(中键移动后，其父节点中的位置由键的大小确定)
图解：
向一个父节点为3-节点的3-节点中插入新节点
操作步骤：插入节点后一直向上分解构造的临时4-节点并将中键移动到更高层双亲节点，直到遇到一个-2节点并将其替换为一个不需要继续分解的3-节点，或是到达树根(3-节点)。
图解：
分解根节点
操作步骤：如果从插入节点到根节点的路径上全是3-节点（包含根节点在内），根节点将最终被替换为一个临时的4-节点，将临时的4-节点分解为3个2-节点，分解后树高会增加1。
图解：
2-3树删除
删除之前，先要对2-3树进行一次命中的查找，查找成功才可以进行删除操作。
删除节点大概分为3种情形
（1）删除非叶子节点。
（2）删除不为2-节点的叶子节点。
（3）删除为2-节点的叶子节点。
删除非叶子节点
操作步骤：使用中序遍历下的直接后继节点key来覆盖当前待删除节点key，再删除用来覆盖的后继节点key。
图解：
删除不为2-节点的叶子节点
操作步骤：删除不为2-节点的叶子节点，直接删除节点即可。
图解：
删除为2-节点的叶子节点
删除为2-节点的叶子节点的步骤相对复杂，删除节点后需要做出相应判断，并根据判断结果调整树结构。
主要分为四种情形：
（1）删除节点为2-节点，父节点为2-节点，兄弟节点为3-节点
操作步骤：当前待删除节点的父节点是2-节点、兄弟节点是3-节点，将父节点移动到当前待删除节点位置，再将兄弟节点中最接近当前位置的key移动到父节点中。
图解：
（2）删除节点为2-节点，父节点为2-节点，兄弟节点为2-节点
操作步骤：当前待删除节点的父节点是2-节点、兄弟节点也是2-节点，先通过移动兄弟节点的中序遍历直接后驱到兄弟节点，以使兄弟节点变为3-节点；再进行6.3.1的操作。
图解：
（3）删除节点为2-节点，父节点为3-节点
操作步骤：当前待删除节点的父节点是3-节点，拆分父节点使其成为2-节点，再将再将父节点中最接近的一个拆分key与中孩子合并，将合并后的节点作为当前节点。
图解：
（4）2-3树为满二叉树，删除叶子节点
操作步骤：若2-3树是一颗满二叉树，将2-3树层树减少，并将当前删除节点的兄弟节点合并到父节点中，同时将父节点的所有兄弟节点合并到父节点的父节点中，如果生成了4-节点，再分解4-节点。
图解：
结语
2-3 树作为一种平衡查找树，查询效率比普通的二叉排序树要稳定许多。
但是2-3树需要维护两种不同类型的结点，查找和插入操作的实现需要大量的代码，而且它们所产生的额外开销可能会使算法比标准的二叉查找树更慢。
参考资料
| [动画 | 什么是2-3树？（修改删除操作方式）](https://www.cxyxiaowu.com/7676.html) |
更多学习
更多实时资讯，前沿技术，生活趣事。尽在【老马啸西风】
交流社群：[交流群信息](https://mp.weixin.qq.com/s/rkSvXxiiLGjl3S-ZOZCr0Q)
