数据结构与算法——2-3树

前言

前面讲到了二叉搜索树 (BST) 和二叉平衡树 (AVL) ，二叉搜索树在最好的情况下搜索的时间复杂度为 O(logn) ，但如果插入节点时，插入元素序列本身就是有序的，那么BST树就退化成一个线性表了，搜索的时间复杂度为 O(n)。
如果想要减少比较次数，就需要降低树的高度。在插入和删除节点时，要保证插入节点后不能使叶子节点之间的深度之差大于 1，这样就能保证整棵树的深度最小，这就是AVL 树解决 BST 搜索性能降低的策略。但由于每次插入或删除节点后，都可能会破坏 AVL 的平衡，而要动态保证 AVL 的平衡需要很多操作，这些操作会影响整个数据结构的性能，除非是在树的结构变化特别少的情形下，否则 AVL 树平衡带来的搜索性能提升有可能还不足为了平衡树所带来的性能损耗。
因此，引入了 2-3 树来提升效率。2-3 树本质也是一种平衡搜索树，但 2-3 树已经不是一棵二叉树了，因为 2-3 树允许存在 3 这种节点，3- 节点中可以存放两个元素，并且可以有三个子节点。

2-3 树定义

2-3 树的定义如下：
（1）2-3 树要么为空要么具有以下性质：
（2）对于 2- 节点，和普通的 BST 节点一样，有一个数据域和两个子节点指针，两个子节点要么为空，要么也是一个2-3树，当前节点的数据的值要大于左子树中所有节点的数据，要小于右子树中所有节点的数据。
（3）对于 3- 节点，有两个数据域 a 和 b 和三个子节点指针，左子树中所有的节点数据要小于a，中子树中所有节点数据要大于 a 而小于 b ，右子树中所有节点数据要大于 b 。
例如图 2.1 所示的树为一棵 2-3 树：

图2.1

2-3 树性质

性质：
（1）对于每一个结点有 1 或者 2 个关键码。
（2）当节点有一个关键码的时，节点有 2 个子树。
（3）当节点有 2 个关键码时，节点有 3 个子树。
（4）所有叶子点都在树的同一层。

2-3树查找

2-3 树的查找类似二叉搜索树的查找过程，根据键值的比较来决定查找的方向。

例如在图 2.1 所示的 2-3 树中查找键为H的节点：

img

例如在图 2.1 所示的 2-3 树中查找键为 B 的节点：

img

2-3树插入

插入

在树的插入之前需要对带插入的节点进行一次查找操作，若树中已经有此节点则不予插入，若没有查找到此节点则记录未命中查找结束时访问的最后一个节点。
空树的插入最简单，创建一个节点即可，这里不予赘述。
对于非空树插入主要分为 4 种情况：
（1）向 2- 节点中插入新节点
（2）向一棵只含 3- 节点的树中插入新节点
（3）向一个父节点为 2- 节点的 3- 节点中插入新节点
（4）向一个父节点为 3- 节点的 3- 节点中插入新节点

向2-节点中插入新节点

操作步骤：如果未命中查找结束于一个 2-节点，直接将 2- 节点替换为一个 3- 节点，并将要插入的键保存在其中。

图解：

img

img

向一棵只含 3- 节点的树中插入新节点

操作步骤：先临时将新键存入唯一的 3- 节点中，使其成为一个 4- 节点，再将它转化为一颗由 3 个 2- 节点组成的 2-3 树，分解后树高会增加 1。

图解：

img

向一个父节点为 2- 节点的 3- 节点中插入新节点

操作步骤：先构造一个临时的 4- 节点并将其分解，分解时将中键移动到父节点中(中键移动后，其父节点中的位置由键的大小确定)

图解：

img

img

向一个父节点为3-节点的3-节点中插入新节点

操作步骤：插入节点后一直向上分解构造的临时4-节点并将中键移动到更高层双亲节点，直到遇到一个-2节点并将其替换为一个不需要继续分解的3-节点，或是到达树根(3-节点)。

图解：

img

img

img

分解根节点

操作步骤：如果从插入节点到根节点的路径上全是3-节点（包含根节点在内），根节点将最终被替换为一个临时的4-节点，将临时的4-节点分解为3个2-节点，分解后树高会增加1。

图解：

img

2-3树删除

删除之前，先要对2-3树进行一次命中的查找，查找成功才可以进行删除操作。
删除节点大概分为3种情形

（1）删除非叶子节点。
（2）删除不为2-节点的叶子节点。
（3）删除为2-节点的叶子节点。

删除非叶子节点

操作步骤：使用中序遍历下的直接后继节点key来覆盖当前待删除节点key，再删除用来覆盖的后继节点key。

图解：

img

删除不为2-节点的叶子节点

操作步骤：删除不为2-节点的叶子节点，直接删除节点即可。**

图解：

img

删除为2-节点的叶子节点

删除为2-节点的叶子节点的步骤相对复杂，删除节点后需要做出相应判断，并根据判断结果调整树结构。主要分为四种情形：

删除节点为2-节点，父节点为2-节点，兄弟节点为3-节点

操作步骤：当前待删除节点的父节点是2-节点、兄弟节点是3-节点，将父节点移动到当前待删除节点位置，再将兄弟节点中最接近当前位置的key移动到父节点中。

图解：

img

删除节点为2-节点，父节点为2-节点，兄弟节点为2-节点

操作步骤：当前待删除节点的父节点是2-节点、兄弟节点也是2-节点，先通过移动兄弟节点的中序遍历直接后驱到兄弟节点，以使兄弟节点变为3-节点；再进行6.3.1的操作。

图解：

img

img

删除节点为2-节点，父节点为3-节点

操作步骤：当前待删除节点的父节点是3-节点，拆分父节点使其成为2-节点，再将再将父节点中最接近的一个拆分key与中孩子合并，将合并后的节点作为当前节点。

图解：

img

2-3树为满二叉树，删除叶子节点

操作步骤：若2-3树是一颗满二叉树，将2-3树层树减少，并将当前删除节点的兄弟节点合并到父节点中，同时将父节点的所有兄弟节点合并到父节点的父节点中，如果生成了4-节点，再分解4-节点。

图解：

img

结语

2-3 树作为一种平衡查找树，查询效率比普通的二叉排序树要稳定许多。但是2-3树需要维护两种不同类型的结点，查找和插入操作的实现需要大量的代码，而且它们所产生的额外开销可能会使算法比标准的二叉查找树更慢。

今日问题：

大家的开工状态怎么样？

打卡格式：

打卡 X 天，答：xxx 。