Email: BuddyZhang1 buddy.zhang@aliyun.com
目录
2-3 树原理
2-3 树由二节点和三节点构成绝对平衡的树。2-3 树是绝对平衡的树（它是一棵空树或它的左 右两个子树的高度差的绝对值不超过 1，并且左右两个子树都是一棵平衡二叉树）。2-3 树每次 添加元素不会直接添加，而是进行节点融合，在融合之后，根据情况，进行分开融合等操作，将 树转化为一个绝对平衡的 2-3 树。
节点分裂/提取
比如上图单个4节点，只需将中间节点往上提，左边值作为其左子树，右边值作为其右子树即可。
节点合并
比如有父节点的 4 节点，节点分裂后，需与父节点进行合并。若合并后父节点还是 4 节点， 则继续分裂，直至满足定义为止。上图中16 与 36 合并后，满足条件，无需再进行操作。
2-3 树节点的插入
2-3 树中，插入一个节点后，也要满足 2-3 树的定义。我们需要找到一个适合的位置来插入 新的值，但是和二叉树不同的是，它不会生成新的叶子节点来存储，而是找到合适的叶子节点 来进行合并。但是注意，插入的原则是尽量保持树的高度，也就是尽量不要增加树的高度。因为 树的高度越小，查找效率会更高。下面分几种情况来说明不同的处理情况。其关键字是往上分裂， 从下往上生长。
向空树中插入一个节点
生成新节点，则其为根节点, 直接插入，满足 2-3 树的要求。
如上图，向一棵空的 2-3 树中插入 58 节点，直接插入之后，58 成为了 2-3 树的根节点， 此时满足 2-3 树的要求。
向 2- 节点中插入一个节点
如果不能直接放到空的子节点，则放到父节点中，此时成为 3- 节点，仍然满足定义， 如下图：
在上图中，准备插入 12 节点，首先没有找到空的子节点可以插入，那么就找 9 节点进行融合， 由于 9 节点是一个 2- 节点，因此可以直接融合，此时如何 2-3 树的要求，不需要做其他操作。
向 3- 节点中插入一个节点，父节点是一个 2- 节点
在 2-3 树中，将节点插入到一个 3- 节点中，此时是一个临时的 4- 节点。临时 4- 节点 不满足 2-3 树的定义，因此需要将临时 4- 节点中的某个节点分离出来，然后向上与父节点 融合。此时父节点是一个 2- 节点，将分离的节点与 2- 节点融合成一个 3- 节点，此时 满足 2-3 树的要求，因此插入成功，例如下图：
向上图中插入 13，此时找到了 “9-12” 节点，融合之后形成一个临时的 4- 节点，如下图：
此时临时 4- 节点不能满足 2-3 树的要求，因此需要对 12 节点进行分离，分离之后，由于 父节点 8 是一个 2- 节点，因此与父节点进行融合，形成 “8-12” 3- 节点，如下图：
经过融合后，新节点 “8-12” 符合 2-3 树的要求，因此插入成功。
向 3- 节点中插入一个节点，父节点是一个 3- 节点
在 2-3 树中，将节点插入到一个 3- 节点中，此时是一个临时的 4- 节点。临时 4- 节点 不满足 2-3 树的定义，因此需要将临时 4- 节点中的某个节点分离出来，然后向上与父节点 融合。此时父节点是一个 3- 节点，将分离的节点与 3- 节点融合成一个临时 4- 节点，此时 不满足 2-3 树的要求，因此需要继续分裂和融合操作，直至满足 2-3 树要求为止，例如下图：
如上图，向 “14-20” 3- 节点中插入 18，此时构成了一个临时的 4- 节点，如下图：
此时需要对临时 4- 节点进行分离和提取，将 14,18,20 分离成 3 个 2- 节点，然后将 18 节点向上融合，此时父节点 “8-12” 是一个 3- 节点，与 18 融合之后，形成了一个临时 4- 节点，
“8-12-18” 组成了一个临时的 4- 节点，此时将临时 4- 节点进行分裂成 3 个 2- 节点， 此时提取 12 节点继续与父节点 5 融合，由于 5 节点是 2- 节点，那么可以直接进行融合， 融合后的 3- 节点符合 2-3 树的要求，如下：
插入 2-3 树例子
本节给出了一个 2-3 插入的完整例子，如下：
首先添加一个节点 58 作为根节点，此时满足 2-3 树的要求。
接着添加一个节点 36，为了保持 2-3 高度最小，那么将 36 插入到 58 节点的左边，构成 一个 3 节点，此时也符合 2-3 树的要求。
插入 23 节点，也为了 2-3 树的高度最小，那么构成一个 4 节点，由于此时不符合 2-3 树 最大节点树不能操作 3，此时需要进行提取操作，将 36 向上提取，如下：
经过提取之后，36 节点需要向父节点进行合并，但是此时 36 之上已经没有节点，因此 36 成 为了新的父节点，23 和 58 称为了节点的子节点，此时符合 2-3 树的要求。
继续插入 16 到 23 的左边，此时符合 2-3 树的要求，插入成功。
继续插入 5 到 16,23 节点上，此时该节点是一个 4 节点，因此不符合 2-3 树要求，因此 需要对 16 进行提取，如下：
提取之后，5 节点与 23 节点称为了 16 节点的子节点，此时提取完成，接下来是将提取的结果 16 向上合并，16 与 36 节点进行合并，如下：
合并之后的 3 节点 ‘16,36’ 符合 2-3 树高度最小以及节点树不大于 3 的条件，因此合并 成。
2-3 树节点的删除
2-3 树的删除的情况会复杂一些，下面分几种情况来说。
待删除的值在叶子节点,叶子节点为 3- 节点
2-3 树删除中，如果待删除的值在叶子节点, 叶子节点为 3- 节点, 直接删除即可。如下图。
如上图，12 是 2-3 树的叶子，12 与 9 构成了一个 3- 节点，因此可以直接删除 12，如下图：
待删除的值在叶子节点,叶子节点为 2- 节点, 兄弟节点为 3- 节点
2-3 树删除中，如果待删除的值在叶子节点, 叶子节点为 2- 节点, 但兄弟节点为 3- 节点。先删除节点， 此时被删除后，节点会为空。通过向兄弟节点借一个最近的键值，然后 再调整该节点与父节点的值。如下图。
如上图，7 是 2-3 树的叶子，12 与 9 构成了一个 3- 节点，7 与其是兄弟节点。此时要删除 7。 将 7 从 2-3 树中直接删除，那么 7 处成为空节点，此时从 “23,9” 这个兄弟 3- 节点中， 借一个临近的节点，如下图：
由于借了 9 节点之后，大小关系不满足，因此调整父节点 8 与 9，使新树满足 2-3 树的要求。 如下图：
待删除的值在叶子节点, 叶子节点为 2- 节点, 兄弟节点为 2- 节点, 父节点为 3- 节点
2-3 树删除中，如果待删除的值在叶子节点, 叶子节点为 2- 节点, 兄弟节点也为 2- 节点，此时需要看父节点，父节点为 3- 节点。此时兄弟节点不够借，父节点降元，从 3- 节点变成 2- 节点，与兄弟节点合并。如下图。
如上图，需要删除 36 节点，此时 11，18 都是 2- 节点，父节点 “15,30” 是一个 3- 节点， 将 36 节点删除之后，此时无法从兄弟节点中借到节点，因此只能从父节点中借节点，那么父节 点从 3- 节点降元成为 2- 节点，如下图：
父节点由 3- 节点变成 2- 节点，18 与 30 融合成一个 3- 节点，均符合 2-3 树的要求， 因此删除成功。
待删除的值在叶子节点, 叶子节点为 2- 节点, 兄弟节点为 2- 节点, 父节点为 2- 节点
2-3 树删除中，如果待删除的值在叶子节点, 叶子节点为 2- 节点, 兄弟节点也为 2- 节点，此时父节点也是为 2- 节点。面对这种情况，直接删除删除该节点，然后将兄弟节点 与父节点融合成一个新节点，此时将新融合的节点当做新的节点，此时新节点也是叶子节点， 所以继续套用之前讨论过关于叶节点删除的情况，继续调整 2-3 树。如果调整过程中， 遇到父节点是根节点，那么树的高度将减 1。例如下图。
如上图，需要删除 12 节点，此时兄弟节点 8 与父节点 9 都是 2- 节点，删除 12 之后， 将 8 节点与 9 节点融合成新的节点，如下图：
由于 “8-9” 节点的融合成为一个新的 3- 节点，此时会引起兄弟节点的融合，因此兄弟节点 会向上融合，与 5 节点形成一个新的 3- 节点 “2-5”。此时 2-3 树达到平衡，总体高度减少 了 1。此时删除完成，如下图：
再如下面的例子，如下图。
在该 2-3 树中需要删除 30 节点，此时父节点 25 与兄弟节点 22 都是 2- 节点，此时直接删除 30 节点，根据之前分析，此时兄弟节点 22 与父节点 25 合并 成一个 3- 节点，并且这个 3- 节点作为一个 “新删除的节点”。如下图：
此时 “22-25” 构成新删除节点，由于此时父节点是 3- 节点，兄弟节点是 2- 节点，因此 父节点需要降元，与兄弟节点融合成 3- 节点，如下图：
待删除的值在父节点, 前驱替换法
2-3 树删除中，如果待删除的值在父节点, 此时使用二叉树中序的概念，找到 父节点的前驱，前驱是父节点左子树中最大值节点，此时删除父节点。如下图。
如上图，此时需要删除父节点 5，找到父节点 5 的前驱就是 3 节点，此时将 5 节点与 3 节点进行交换，如下图：
此时交换之后，5 节点成为了 2 的子节点，此时 5 节点就是一个叶子，因此可以按之前 对叶子节点的讨论办法来删除 5 节点。值得注意的是 5 节点不仅可以是一个 2- 节点，也 可以是一个 3- 节点。如上，交换之后 5 节点删除后，父节点与兄弟节点需要融合，如下
待删除的值在父节点, 后继替换法
2-3 树删除中，如果待删除的值在父节点, 此时使用二叉树中序的概念，找到 父节点的后继，后继是父节点右子树中最小值节点，此时删除父节点。如下图。
如上图，此时需要删除父节点 5，找到父节点 5 的后继就是 7 节点，此时将 5 节点与 7 节点进行交换，如下图：
此时交换之后，5 节点成为了 8 的子节点，此时 5 节点就是一个叶子，因此可以按之前 对叶子节点的讨论办法来删除 5 节点。值得注意的是 5 节点不仅可以是一个 2- 节点，也 可以是一个 3- 节点。如上，交换之后 5 节点删除后，父节点与兄弟节点需要融合，如下
2-3 树最小实践
实践源码
开发者可以从上面的链接中获得所有的实践代码，也可以使用如下命令获得：
mkdir -p 2-3-tree
cd 2-3-tree
wget https://raw.githubusercontent.com/BiscuitOS/HardStack/master/Algorithem/tree/2-3-tree/Basic/Makefile
wget https://raw.githubusercontent.com/BiscuitOS/HardStack/master/Algorithem/tree/2-3-tree/Basic/README.md
wget https://raw.githubusercontent.com/BiscuitOS/HardStack/master/Algorithem/tree/2-3-tree/Basic/tree23.c
wget https://raw.githubusercontent.com/BiscuitOS/HardStack/master/Algorithem/tree/2-3-tree/Basic/tree23_run.c
wget https://raw.githubusercontent.com/BiscuitOS/HardStack/master/Algorithem/tree/2-3-tree/Basic/tree23.h
wget https://raw.githubusercontent.com/BiscuitOS/HardStack/master/Algorithem/tree/2-3-tree/Basic/tree23_perform.h实践源码具体内容如下：
/*
* 2-3-Tree Manual.
*
* (C) 2019.05.20 <buddy.zhang@aliyun.com>
*
* This program is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License version 2 as
* published by the Free Software Foundation.
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
/* Head of 2-3 tree */
#include <tree23.h>
/* Root of Tree23 */
static struct tree23_root *BiscuitOS_root;
#define NUM_MAX 16
/* data */
static unsigned long Tree23_data[NUM_MAX] = { 23, 67, 344, 56, 12334, 56,
87, 568, 423, 987, 1, 876, 76542, 3245,
8976, 90 };
int main()
{
int i;
/* creat 2-3 tree */
BiscuitOS_root = tree23_root_init();
for (i = 0; i < NUM_MAX; i++) {
/* Insert node into 2-3 tree */
tree23_insert(Tree23_data[i], BiscuitOS_root);
}
printf("Itervate over 2-3 Tree.\n");
/* tree23 interate over */
tree23_print(BiscuitOS_root->root);
/* Erase */
tree23_erase(423, BiscuitOS_root);
tree23_erase(876, BiscuitOS_root);
printf("Re- Itervate over 2-3 Tree\n");
tree23_print(BiscuitOS_root->root);
/* delete 2-3 tree */
tree23_deltree(BiscuitOS_root);
return 0;
}源码编译
使用如下命令进行编译：
make源码运行
实践源码的运行很简单，可以使用如下命令，并且运行结果如下：
$ ./tree23
Itervate over 2-3 Tree.
ldata: 1
rdata: 23
ldata: 56
ldata: 56
ldata: 67
ldata: 87
rdata: 90
ldata: 344
ldata: 423
rdata: 568
ldata: 876
ldata: 987
ldata: 3245
rdata: 8976
rdata: 12334
ldata: 76542
Re- Itervate over 2-3 Tree
ldata: 1
rdata: 23
ldata: 56
ldata: 56
ldata: 67
ldata: 87
ldata: 90
ldata: 344
rdata: 568
ldata: 987
ldata: 3245
ldata: 8976
rdata: 12334
ldata: 76542运行分析
在实践代码中，向 2-3 树中添加了多个数据，并遍历所有的节点，以及删除了对应的节点
2-3 树性能测试
首先通过最小实践章节获得对应的测试源码，开发者可以参考如下命令进行测试：
make
./tree23_test 18 8tree23_perform 用于测试 2-3 tree 的插入和删除性能，如上面的命令，插入 18 个数据， 然后删除 8 个数据。测试结果如下：
$ ./tree23_test 18 8
Runtime in clock ticks: 21, seconds: 0.000021
**Tree remnants incoming**
ldata: 13200439
ldata: 67992512
ldata: 307759200
rdata: 340750784
rdata: 728072320
ldata: 948322048
ldata: 1196858880
ldata: 1385551232
ldata: 1842947456
ldata: 1982501504从上面可以看出，总共花费时间 0.000021。开发者还可以根据需求进行更多的测试。
红黑树与 2-3 树的关系
2-3 树与红黑树是同一种树，只不过红黑树是 2-3 树的一种只含 2 节点的表现形式。(注： 红黑树并不是只有这一种实现方式）。可以把 2-3 树的三节点看作二分搜索树中的两个节点 合作构成的一个节点，二其中小的一方就是红节点。
一个 2-3 树按照上面的设定展开
可以看到，将部分节点横放后，2-3 树与红黑树其实是等价的
红黑树基于 2-3 树的基本性质
红节点一定属于一个黑节点的左孩子, 2-3 树中对应的 3 节点对应红黑树中的黑节点和黑节点 左下角的红节点
1) 每个节点或者是红色的，或者是黑色的。
2) 根节点一定是黑色的, 2-3 树中，当根节点是 2 上节点的时候明显对应为黑色，当跟节点是三节点的时候，红黑树中对应的红节点就跑到左下角了。
3) 每一个叶子节点 (指最后的空节点，并不指左右节点都为空的那个节点) 是黑色的相当于定义了空节点本身就是一个黑色的节点。
4) 如果一个节点是红色的，那么他的孩子节点都是黑色的 2-3 树中，红色节点对应的部分就是 3 节点，如果 3 节点的孩子是一个二节点，那当然没话说，是一个黑色节点，如果 3 节点的下面也是一个三节点，对应到红黑树中，就变成了一个黑节点以及黑节点左孩子红节点！注意：这个结论对于黑节点不成立，黑节点的右孩子一定是黑色的，但是左孩子可能为黑，可能为红！
5) (核心)从任意一个节点到叶子结点，经过的黑色节点个数是一样的在 2-3 树中，保持着绝对的平衡性，说明这是一颗满二叉树，所有叶子节点的深度都是一样的，对应到红黑树中，也就对应着所有的黑节点。
红黑树是保持 “黑平衡” 的二叉树，严格意义上讲，不是平衡二叉树,最大高度为 2logn – 高度的复杂度为 O(logn).
附录
赞赏一下吧 🙂
