2-3树

二叉搜索树退化链表

在树的数据结构中，最先有点是二叉查找树，也就是英文缩写 BST 树。在使用数据插入的过程中，理想情况下它是一个平衡的二叉树(左右子树高度差不超过1)，但实际上可能会出现二叉树都一边倒，让二叉树退化为像链表一样的数据结构。从而树形结构的时间复杂度也从 O(logn) 升级到 O(n)，如下图：

• 二叉搜索树的数据插入过程是，插入节点与当前节点做比对，小于在左，大于在右。
• 随着数据的插入顺序不同，就会出现完全不同的数据结构。可能是一棵平衡二叉树，也极有可能退化成链表的树。
• 当树结构退化成链表以后，整个树索引的性能也跟着退化成链表。

2-3 树解决平衡问题

2-3 树是一种非常巧妙的结构，在保持树结构的基础上，它允许在一个节点中可以有两个元素，等元素数量等于 3 个时候再进行调整。通过这种方式来保证整个二叉搜索树的平衡性。

• 左侧是二叉搜索树，右侧是 2-3 平衡树，分别插入节点 4、5，观察树形结构变化。
• 二叉搜索树开始出现偏移，节点一遍倒。
• 2-3 树通过一个节点中存放 2 到 3 个元素，来调整树形结构，保持平衡。
• 所谓的保持平衡就是从根节点，到每一个最底部的自己点，链路长度一致。

2-3 树结构定义和特性

序号	描述	示意图
1	2-，1 个数据节点 2 个树杈
2	3-，2 个数据节点 3 个树杈
3	三叉与两叉的不同点在于，除了两边的节点，中间件还有一个节点。这个节点是介于 2、4 之间的值。
4	当随着插入数据，会出现临时的一个节点中，有三个元素。 这时会被调整成一个二叉树。

综上我们可以总结出，2-3 树的一些性质；

1. 2-3 树所有子叶节点都在同一层
2. 1 个节点可以有 1 到 2 个数据，如果有三个需要调整树结构
3. 1 个节点 1 个数据时，则有两个子节点
4. 1 个节点 2 个数据时，则有三个子节点，且中间子节点是介于两个节点间的值

数据插入

模拟在二叉搜索树中退化成链表的数据，插入到 2-3 树的变化过程，数据包括；1、2、3、4、5、6、7，插入过程图如下：

以上，就是整个数据在插入过程中，2-3 树的演化过程，接下来我们具体讲解每一步的变化：

1. α，向节点 1 插入数据 2，此时为了保持平衡，不会新产生分支，只会在一个节点中存放两个节点。
2. β，继续插入数据 3，此时这个节点有三数据，1、2、3，是一个临时区域。
3. γ，把三个数据的节点，中间节点拉起来，调整成树形结构。
4. δ，继续插入数据 4，为了保持树平衡，会插在节点 3 的右侧。
5. ε，继续插入数据 5，插入后 3、4、5 共用 1 个节点，当一个节点上有三个数据时候，则需要进行调整。
6. ζ，中间节点 4 向上 调整，调整后，1 节点在左、3 节点在中间、5 节点在右。
7. η ，继续插入数据 6，在保持树平衡的情况下，与节点 5 公用。
8. θ ，继续插入数据 7，插入后，节点 7 会与当前的节点 5 6 共用。此时是一个临时存放，需要调整。初步调整后，抽出 6 节点，向上存放，变为 2 4 6 共用一个节点，这是一个临时状态，还需要继续调整。
9. ι，因为根节点有三个数据 2、4、6，则继续需要把中间节点上移，1、3 和 5、7 则分别成二叉落到节点 2、节点 6 上。

数据删除

有了上面数据插入的学习，在看数据删除其实就是一个逆向的过程，在删除的主要包括这样两种情况：

1. 删除了 3-节点，也就是包含两个数据元素的节点，直接删除即可，不会破坏树平
   衡。
2. 删除了 2-节点，此时会破坏树平衡，需要将树高缩短或者元素合并，恢复树平
   衡。

承接上面👆的例子，我们把数据再从 7、6、5、4、3、2、1 顺序删除，观察 2-3 树的结构变化，如下：

1. α，删除节点 7，因为节点 7 只有一个数据元素，删除后将节点 5、6 合并，但此时破坏了 2-3 树的平衡性，需要缩短树高进行调整。
2. β，因为删除节点后，整个树结构不平衡，所以需要缩短树高，调整元素。节点 2、4 合并，节点 1、3 分别插入左侧和中间。
3. γ，删除节点 6，这个节点是 3-节点(可以分出 3 个叉的意思)，删除后不会破坏树平衡，保持不变。
4. δ，删除节点 5，此时会破坏树平衡，需要把跟节点 4 下放，与 3 合并。
5. ε，删除节点 4，这个节点依旧是 3-节点，所以不需要改变树结构。
6. ζ，删除节点 3，此时只有 1、2 节点，需要合并。
7. η ，删除节点 2，此时节点依旧是 3-节点，所以不需要改变树结构。

再看一个稍微复杂点 2-3 树删除：

上面👆这张图，就一个稍微复杂点的 2-3 平衡树，树的删除过程主要包括；

1. 删除 4，其实需要将节点 3、5 合并，指向节点 2，保持树平衡。
2. 删除 7，节点 8、9 合并。
3. 删除 14，节点 15 上移，恢复成 3-叉树。

如果有时候不好理解删除，可以试想下，这个要删除的节点，在插入的时候是个什么效果。

数据查找

相比于插入和删除，查找的过程还是比较简单的，不需要调整数据结果。基本原则就是：

1. 小于当前节点值，左侧寻找
2. 大于当前节点值，右侧寻找
3. 一直到找到索引值，停止。

🔍第一层寻找：

🔍第二层寻找：

🔍第三次寻找：