1. 从二叉搜索树退化聊起为什么非要有 2-3-4 树很多初学数据结构的朋友第一个接触的树结构就是二叉搜索树BST当时觉得这玩意儿挺完美左小右大中序遍历有序查找、插入、删除看起来都是 O(log n)。但实际写代码跑数据就会发现问题——BST 的性能完全取决于插入顺序。你按 1、2、3、4、5 的顺序插入节点得到的就是一棵只有右孩子的链表查找 5 要遍历 5 个节点。数据量到十万、百万级别时这种退化是灾难性的。AVL 树通过旋转解决了这个问题强制左右子树高度差不超过 1但代价是插入删除时旋转操作频繁代码实现也比较绕。红黑树放宽了平衡条件用颜色标记和局部旋转把插入删除的调整控制在了常数级别但它那套“红黑性质”初看简直像魔法很多人背了规则却不懂为什么。2-3-4 树的意义恰恰在于它用一种更直观的方式回答了“如何让树始终平衡”这个问题——不靠旋转靠节点分裂和合并不限制节点只能存一个关键字而是让节点可以存 1 到 3 个关键字、拥有 2 到 4 个孩子。因为每次插入都在叶子节点进行叶子深度统一增加整棵树永远保持完美平衡所有叶子在同一层高度严格等于 ⌈log₄N⌉ 到 ⌈log₂N⌉ 之间。我第一次认真啃 2-3-4 树是在研究数据库索引原理的时候后来才发现这棵树就是 B 树的四阶特例理解了它B 树、B 树都不再是背概念而是自然而然的延伸。这篇文章我会把 2-3-4 树的定义、查找、插入、删除全部掰开揉碎讲清楚给出完整可运行的代码最后再讲透它和红黑树的等价关系。整篇更适合已经学过二叉树、对递归有一定感觉的读者当然只要你愿意多看两遍零基础也能跟下来。2. 节点定义与树的结构一个节点最多三个关键字2-3-4 树的名字来源于节点的孩子数量。每个节点要么有 2 个孩子此时存 1 个关键字、要么有 3 个孩子此时存 2 个关键字、要么有 4 个孩子此时存 3 个关键字。叶节点可以没有孩子但依然遵守关键字数量的约束。这里有个很容易混淆的地方很多人看到“2-3-4”以为是四种节点形态其实指的是一个节点可能拥有的孩子数不是关键字数。关键字数和孩子数的关系固定为节点类型孩子数关键字数结构示意2-节点21[key] 左子树 key 右子树3-节点32[k1, k2] 左 k1 中 k2 右4-节点43[k1, k2, k3] 左 k1 中1 k2 中2 k3 右每个节点的关键字按升序排列所有关键字互不重复。子树之间的顺序关系保持和 BST 一样的性质某一棵子树里的所有关键字都落在它对应的两个相邻关键字之间。你可以把 2-3-4 树理解成“多个 BST 节点合并成了一个超级节点”只不过这个超级节点自己维护了内部的关键字顺序。节点结构用 C 定义的话最简单的做法是用固定大小的数组enum NodeType { NODE_2, NODE_3, NODE_4 }; struct Node { int keys[3]; // 最多3个关键字 Node* children[4]; // 最多4个孩子 int keyCount; // 当前实际关键字数量 1~3 bool isLeaf; // 是否为叶节点 Node() : keyCount(0), isLeaf(true) { for (int i 0; i 4; i) children[i] nullptr; } };如果你用过 B 树的实现会发现这个结构基本就是 B 树节点的缩小版。实际上你把代码里的孩子数上限从 4 改成 M关键字数上限从 3 改成 M-1就得到了一棵 M 阶 B 树的雏形。所以从这个角度讲2-3-4 树是你通往 B 树体系最好的敲门砖。树的高度是另一个值得注意的点。因为有多个关键字合并存储2-3-4 树的高度明显比同样数据量的 BST 矮。一个存了 N 个关键字的 2-3-4 树高度最小时的所有节点都是 4-节点此时高度约等于 ⌈log₄N⌉高度最大时所有节点都是 2-节点退化为满二叉树高度约等于 ⌈log₂N⌉。这个“矮”带来的直接好处是查找时磁盘 IO 次数减少——数据库索引用 B 树而不是二叉树的根本原因也在这里。3. 查找操作和 BST 几乎一样的思路查找是 2-3-4 树里最简单的操作它和二叉搜索树的查找本质相同只不过每个节点要比较的不再是一个关键字而是一组关键字。从根节点开始在当前节点的关键字数组里做顺序查找因为最多 3 个关键字顺序查找比二分更快如果命中直接返回如果没命中根据待查找值落在哪个区间进入对应的孩子子树继续递归。到叶子节点还没命中说明关键字不存在。bool search(Node* root, int key) { Node* cur root; while (cur) { int i 0; while (i cur-keyCount key cur-keys[i]) i; if (i cur-keyCount key cur-keys[i]) { return true; } if (cur-isLeaf) { return false; } cur cur-children[i]; } return false; }注意两个细节。第一个while (i keyCount key keys[i])这个循环结束后i 指向第一个大于等于 key 的位置。如果这个位置关键字恰好等于 key说明找到了否则 key 应该落在 children[i] 代表的子树里。举例来说当前节点是 3-节点 [20, 40]要查 35循环后 i 1因为 35 20 但 35 40循环到 keys[1] 时条件不成立35 应该去 children[1] 这棵子树里找——也就是介于 20 和 40 之间的那棵子树。第二个递归可以改写成上面的非递归形式因为查找永远只沿着一条路径向下不需要回溯。非递归版本在 C 里更有效率也更好调试建议直接写成这种形式。查找复杂度方面最坏情况要比较 3 个关键字再下移一层所以单次查找的 CPU 比较次数最多约为 3 × ⌈log₂N⌉但树的高度比 BST 矮很多整体查找性能依然稳定在 O(log N)。而且实际场景里节点内部的关键字通常是连续内存存储顺序扫描 3 个整数在 CPU 缓存层面几乎无开销所以没有必要用二分查找。4. 插入操作自底向上分裂还是自顶向下预分裂4.1 自底向上的标准流程2-3-4 树插入最朴素的理解是模拟“多路搜索树的自然生长”。新关键字总是插入到叶子节点如果叶子节点有空间关键字数 3直接放进去并保持有序即可。麻烦的是插入后叶子节点变成 5-节点4 个关键字 5 个孩子这在 2-3-4 树里是不合法的。处理办法是把溢出的 4-节点“分裂”成两个 2-节点并把中间关键字上交给父节点。如果父节点因此也溢出就继续向上传递直到根节点。如果根节点也溢出就分裂根节点树的高度增加一层。这个流程描述起来很清晰但代码实现比较繁琐你需要维护从根到目标叶子的完整路径插入后逐层回溯处理每一层可能的溢出还要小心地维护 children 指针的移动。我第一次写这个版本时调试指针边界花了大半天。4.2 自顶向下预分裂让代码简单一个量级传统 B 树教学里常用自底向上分裂但在 2-3-4 树中自顶向下预分裂的思路才是更实用的方案。核心思想在沿路径向下搜索插入位置的过程中凡是遇到 4-节点就当场分裂把中间关键字上交给父节点并拆成两个 2-节点。这样保证到达叶子时叶子一定不是 4-节点插入后最多变成 4-节点绝对不会向上溢出。这个“先分裂、后插入”的策略把可能的级联调整消灭在了路径探索阶段插入结束后不需要任何回溯修正。代码写起来像 BST 插入一样顺只是每个节点进入前多了一步检查。那预分裂的具体规则是什么如果根节点是 4-节点分裂根节点中间关键字上移成为新根左右两个关键字变成两个新孩子节点。树的高度 1。如果路径上的某个节点是 4-节点将其分裂中间关键字上移到父节点剩下的两个关键字各自作为独立节点并挂接到父节点对应位置。举个具体例子假如当前树根节点是 4-节点 [50, 70, 90]现在要插入 60。根节点是 4-节点先分裂它70 上移成为新根50 和 90 各成一个节点作为新根的左右孩子。此时 70 的左孩子是 [50]右孩子是 [90]然后继续往下走找 60 的位置——60 大于 50 小于 70所以进入 [50] 这个节点。因为它是叶子且只有一个关键字直接插入变成 3-节点 [50, 60]。整个过程结束树的高度从 1 变成了 2而且依然全平衡。4.3 节点分裂的四种情况分裂 4-节点时根据父节点的形态不同操作细节也不同。我总结出四种情况分裂的是根节点父节点不存在。中间关键字成为新根左右两部分成为新根的两个孩子。分裂的是 2-节点的孩子父节点只有一个关键字把中间关键字直接插入父节点父节点变成 3-节点同时父节点原有一个孩子现在分裂出两个新孩子一共 3 个孩子正好匹配。分裂的是 3-节点的最左或最右孩子父节点有两个关键字把中间关键字插入父节点后父节点变成 4-节点。因为原父节点有 3 个孩子其中一个分裂成两个总共变成 4 个孩子恰好满配。分裂的是 3-节点的中间孩子父节点有两个关键字中间孩子分裂出的两个节点其中一个要插到父节点的两个孩子之间。只要找到正确的插入下标把后续孩子数组整体右移一位即可。只要把分裂操作封装成一个函数传入“要分裂的 4-节点指针”和“该节点在父节点 children 数组中的下标”上面的四种情况可以统一处理。void splitChild(Node* parent, int idx) { Node* full parent-children[idx]; // 待分裂的4-节点 Node* left new Node(); Node* right new Node(); left-keys[0] full-keys[0]; right-keys[0] full-keys[2]; left-keyCount right-keyCount 1; left-isLeaf right-isLeaf full-isLeaf; if (!full-isLeaf) { left-children[0] full-children[0]; left-children[1] full-children[1]; right-children[0] full-children[2]; right-children[1] full-children[3]; } // 父节点腾出位置插入中间关键字 for (int j parent-keyCount; j idx; --j) { parent-keys[j] parent-keys[j - 1]; parent-children[j 1] parent-children[j]; } parent-keys[idx] full-keys[1]; parent-children[idx] left; parent-children[idx 1] right; parent-keyCount; delete full; }这里注意细节children数组的长度是 4但父节点原有 keyCount1 个孩子。右移时children[j1] children[j]的操作要从最右边开始避免覆盖数据。这不是难写的代码但非常容易写错建议配合调试多走几遍。4.4 插入代码的全貌当你把预分裂做成了不变量——“路径上的节点一定不是 4-节点”插入就变得异常简单void insert(Node* root, int key) { if (!root) { root new Node(); root-keys[0] key; root-keyCount 1; return; } // 如果根是4-节点先分裂 if (root-keyCount 3) { Node* newRoot new Node(); newRoot-isLeaf false; newRoot-children[0] root; splitChild(newRoot, 0); root newRoot; } Node* cur root; while (true) { // 沿路径分裂4-节点 if (cur-keyCount 3) { // 理论上一路分裂下来不会出现这种情况 // 但为了鲁棒性可以在这里做防御 } int i 0; while (i cur-keyCount key cur-keys[i]) i; if (i cur-keyCount key cur-keys[i]) { // 重复关键字按需处理 return; } if (cur-isLeaf) { // 腾出位置并插入 for (int j cur-keyCount; j i; --j) { cur-keys[j] cur-keys[j - 1]; } cur-keys[i] key; cur-keyCount; return; } else { // 进入孩子前如果孩子是4-节点先分裂 Node* child cur-children[i]; if (child-keyCount 3) { splitChild(cur, i); // 分裂后 cur 新增了一个关键字需要重新确定 key 应该进哪个孩子 if (key cur-keys[i]) i; } cur cur-children[i]; } } }上面的核心点在于进入孩子前检查孩子是否是 4-节点是就分裂。分裂后父节点多了一个关键字所以 key 的走向可能需要重新判断。这里用的是if (key cur-keys[i]) i意思是如果 key 大于刚刚上移的中间关键字就应该去右边的孩子。这个判断非常重要漏掉它就会出现关键字放错子树的问题。顺便提一句重复关键字的处理策略取决于需求。大多数数据结构教材默认关键字唯一重复时直接忽略。如果允许重复有几种方案——把重复值放进右子树、给每个节点增加一个计数、或者干脆用链表把所有相同值串起来。不同方案对树的形态和删除逻辑都有影响实际工程里需要认真权衡。5. 删除操作所有平衡树里最棘手的部分如果说插入是顺水推舟那删除就是逆水行舟。2-3-4 树的删除之所以复杂核心问题和所有平衡树一样删掉一个关键字之后节点可能违反“最少 1 个关键字”的约束必须通过借调和合并来修复。5.1 删除的分类框架先说结论性的框架删除操作分两大情形情形一要删除的关键字在叶节点。直接删除即可如果删除后节点变成空节点就需要从父节点借一个关键字下来或者和兄弟节点合并。情形二要删除的关键字在内部节点。这时候不能直接删否则会留下一个没有关键字的空洞节点。标准做法是用前驱或后继关键字来替换待删除关键字然后把问题转化为删除叶节点里的那个关键字。这个过程和 BST 删除“用后继替换”的思路一模一样只是 2-3-4 树的每个节点可能有多个关键字前驱/后继的定义要相应扩展——前驱就是左子树里最大的关键字后继就是右子树里最小的关键字。用后继替换后删除问题就归结到了叶子上所以情形二的复杂度本质上是情形一的复杂度加上一次查找后继的过程。5.2 自顶向下的预合并策略和插入一样删除也可以采用自顶向下的策略把“节点可能变成空节点”的麻烦消灭在路径探索阶段。核心不变量是在向下搜索的过程中确保当前节点是一个至少含 2 个关键字的节点对于根节点允许只有 1 个关键字但必须保证它要么是叶节点要么有两个以上孩子。实际的操作规则是这样的每到一个节点查看接下来要进入的那个孩子。如果这个孩子只有 1 个关键字2-节点则视其兄弟节点的情况执行借调或合并保证进入的孩子至少有 2 个关键字。这样一路下来当你到达要删除的叶子时叶子至少有 2 个关键字删除后至少还剩 1 个不会产生空节点。5.3 借调与合并的两种情况假设当前节点是 cur目标孩子是 cur-children[i]且目标孩子只有 1 个关键字。情况一相邻兄弟节点有至少 2 个关键字。这时可以从兄弟节点“借”一个关键字过来过程其实经过了父节点中转把父节点的某个关键字下移到目标孩子里把兄弟节点的某个关键字上移到父节点刚才空出的位置把兄弟节点的某个子树挂接到目标孩子的对应位置。这个操作本质上和 AVL 树的旋转非常相似但因为在多关键字节点里发生看起来更像是“关键字的搬家”。举个例子父节点是 [30]左孩子是 [10]右孩子是 [25, 40]。现在要往左孩子方向走但左孩子只有 1 个关键字右兄弟有 2 个关键字。处理方法父节点的 30 下移到左孩子右兄弟的最小关键字 25 上移到父节点同时右兄弟的子树结构相应调整。左孩子从 [10] 变成 [10, 30]父节点变成 [25]右兄弟从 [25, 40] 变成 [40]。情况二相邻兄弟节点也只有 1 个关键字。这时没法借只能合并。把父节点的关键字下移和两个 2-节点合并成一个 3-节点父节点是 [30]左孩子是 [10]右孩子是 [25]。合并后把 30 下移和 [10]、[25] 结合成 [10, 25, 30]但这个节点是 4-节点不对注意两个 2-节点各有 1 个关键字加上父节点的 1 个关键字总共 3 个关键字所以合并后是一个 4-节点完全合法。父节点的关键字数减一孩子数减一。如果父节点因此变成空节点就继续向上递归处理。这个向上递归在自顶向下策略里很少真正发生因为每一层的下探都保证了目标孩子至少有 2 个关键字父节点通常不会因此变成空。5.4 删除操作的预合并版本代码框架预合并思路的删除实现先处理根节点如果根节点是 2-节点且有两个 2-节点的孩子先把根节点合并树高度减一。然后调用递归函数向下搜索。void remove(Node* root, int key) { if (!root) return; // 根节点为2-节点且两个孩子也是2-节点时先合并根 if (root-keyCount 1 root-isLeaf false) { if (root-children[0]-keyCount 1 root-children[1]-keyCount 1) { mergeRoot(root); } } removeFromNode(root, key); if (root-keyCount 0) { // 树为空或高度降低 Node* old root; root root-children[0]; delete old; } }核心递归函数removeFromNode按以下逻辑处理如果当前节点是叶子直接在 keys 数组里查找并删除目标关键字如果当前节点是内部节点根据 key 与节点内各关键字的大小关系决定进入哪个孩子进入孩子之前检查孩子和兄弟的关键字数执行借调或合并如果目标关键字就在当前内部节点中且其左右孩子都非叶子用后继替换找到右子树的最小关键字替换当前节点的目标关键字然后递归地从右子树删除那个最小关键字。如果右孩子是 2-节点先做借调/合并再递归。这里有个细节要特别提醒当目标关键字在当前内部节点时不能直接删。直接删会让那个位置变成空洞孩子数组的索引关系就被破坏了。必须用前驱或后继顶上把删除问题转移到一个保证不会产生空节点的叶子上。这个思路和 BST 删除一模一样但实现时要更小心因为节点里有多个关键字和多个孩子。5.5 我的建议先实现基础版再考虑预合并预合并版本代码虽然逻辑上优雅但第一次接触的人很容易在借调条件判断上写错。我的学习建议是分成两步走第一步先实现自底向上的朴素删除。允许删除后节点变空然后递归回溯修复空节点。这个版本逻辑直白虽然代码量大但每一步都清楚。第二步理解自顶向下预合并的思想再用它简化代码。在纸上画几棵完整的 2-3-4 树把 2-节点的删除、3-节点内部关键字的删除、4-节点删除逐一遍历一遍。我当年学这棵树时就是用这种方法把红黑树的删除也一并搞懂了——因为两者的处理逻辑本质上就是同一套思路的不同表达。6. 与红黑树的等价关系看透本质的关键一步6.1 为什么红黑树和 2-3-4 树是同一棵树这是 2-3-4 树最有价值的一个知识点。红黑树不是一棵抽象出来的独立数据结构它就是 2-3-4 树在“每个节点最多只有一个关键字”约束下的二叉树编码表示。理解这个等价关系红黑树里的“黑高”“红节点连续不允许”“插入删除的旋转规则”就不再是背下来的魔法而是 2-3-4 树节点操作在二叉树上的自然投影。怎么把 2-3-4 树变成红黑树规则如下2-节点直接变成一个黑色节点。3-节点变成一黑一红两个节点红节点是黑节点的左孩子或右孩子。红节点代表它和黑节点“原本在同一个 2-3-4 树节点里”。4-节点变成一个黑色节点带两个红色孩子。黑色节点对应 4-节点的中间关键字两个红色孩子分别对应左右两个关键字。这里有一个非常微妙的点3-节点的两种转换方式红色在左还是红色在右会导致不同的红黑树形态但都指代同一棵 2-3-4 树。这也是为什么同一个 2-3-4 树可以对应多棵红黑树。6.2 等价关系给红黑树操作带来的启发红黑树的所有旋转操作都可以还原成 2-3-4 树的节点借调或合并。举个例子红黑树插入后的“变色旋转”修正对应的是 2-3-4 树插入时的节点分裂。红黑树里叔叔节点是红色时的变色操作本质上是 2-3-4 树中 4-节点分裂把中间关键字上移到父节点。红黑树里的左旋右旋本质上是 2-3-4 树中 3-节点从一种形态转成另一种形态。这个等价关系给学习者的最大帮助是调试。如果你在写红黑树删除时不知道某个 case 为什么这么做把树还原成 2-3-4 树去看看——那个 case 很可能就是在处理 2-节点的借调和合并。我在学习红黑树时曾经花了一整晚追一个新的 case最后还原成 2-3-4 树才发现那不过是“3-节点兄弟借一个关键字”的边界情形。6.3 从 2-3-4 树到 B 树的延伸2-3-4 树是阶数 M4 的 B 树。把节点关键字数上限从 3 推广到 M-1孩子数上限从 4 推广到 M插入删除的分裂合并逻辑不需要任何本质变化就得到了通用的 B 树。数据库索引用的 B 树和 2-3-4 树的区别主要有三点所有数据都存放在叶节点内部节点只存索引关键字叶节点之间有指针串联方便范围查询内部节点只用于导航。但底层那套“节点满则分裂、节点空则合并”的思想完全继承自 2-3-4 树。所以学透 2-3-4 树等于同时拿下了红黑树和 B 树家族的地基。7. 完整代码实现与运行验证7.1 完整 C 代码我把一棵支持查找、插入、删除和中序遍历的 2-3-4 树完整实现放在下面。代码尽可能保持了可读性删除了大量防御性检查只保留核心逻辑方便你对照阅读。我建议不要直接拿去生产环境而是先对着代码把每一条分支走一遍再亲手画树验证。#include iostream class TwoThreeFourTree { private: struct Node { int keys[3]; Node* children[4]; int keyCount; bool isLeaf; Node() : keyCount(0), isLeaf(true) { for (int i 0; i 4; i) children[i] nullptr; } }; Node* root; void splitChild(Node* parent, int idx) { Node* full parent-children[idx]; Node* left new Node(); Node* right new Node(); left-keys[0] full-keys[0]; right-keys[0] full-keys[2]; left-keyCount right-keyCount 1; left-isLeaf right-isLeaf full-isLeaf; if (!full-isLeaf) { left-children[0] full-children[0]; left-children[1] full-children[1]; right-children[0] full-children[2]; right-children[1] full-children[3]; } for (int j parent-keyCount; j idx; --j) { parent-keys[j] parent-keys[j - 1]; parent-children[j 1] parent-children[j]; } parent-keys[idx] full-keys[1]; parent-children[idx] left; parent-children[idx 1] right; parent-keyCount; delete full; } void borrowFromRight(Node* parent, int idx) { Node* child parent-children[idx]; Node* sibling parent-children[idx 1]; child-keys[child-keyCount] parent-keys[idx]; child-children[child-keyCount 1] sibling-children[0]; child-keyCount; parent-keys[idx] sibling-keys[0]; for (int j 0; j sibling-keyCount - 1; j) { sibling-keys[j] sibling-keys[j 1]; } for (int j 0; j sibling-keyCount; j) { sibling-children[j] sibling-children[j 1]; } sibling-keyCount--; } void borrowFromLeft(Node* parent, int idx) { Node* child parent-children[idx]; Node* sibling parent-children[idx - 1]; for (int j child-keyCount; j 0; --j) { child-keys[j] child-keys[j - 1]; } for (int j child-keyCount 1; j 0; --j) { child-children[j] child-children[j - 1]; } child-keys[0] parent-keys[idx - 1]; child-children[0] sibling-children[sibling-keyCount]; child-keyCount; parent-keys[idx - 1] sibling-keys[sibling-keyCount - 1]; sibling-keyCount--; } void mergeChildren(Node* parent, int idx) { Node* left parent-children[idx]; Node* right parent-children[idx 1]; left-keys[left-keyCount] parent-keys[idx]; for (int j 0; j right-keyCount; j) { left-keys[left-keyCount 1 j] right-keys[j]; } if (!left-isLeaf) { for (int j 0; j right-keyCount; j) { left-children[left-keyCount 1 j] right-children[j]; } } left-keyCount left-keyCount 1 right-keyCount; for (int j idx; j parent-keyCount - 1; j) { parent-keys[j] parent-keys[j 1]; parent-children[j 1] parent-children[j 2]; } parent-keyCount--; delete right; } void insertNonFull(Node* node, int key) { int i 0; while (i node-keyCount key node-keys[i]) i; if (i node-keyCount key node-keys[i]) { return; } if (node-isLeaf) { for (int j node-keyCount; j i; --j) { node-keys[j] node-keys[j - 1]; } node-keys[i] key; node-keyCount; } else { Node* child node-children[i]; if (child-keyCount 3) { splitChild(node, i); if (key node-keys[i]) i; child node-children[i]; } insertNonFull(child, key); } } void removeFromNode(Node* node, int key) { int i 0; while (i node-keyCount key node-keys[i]) i; if (i node-keyCount key node-keys[i]) { if (node-isLeaf) { for (int j i; j node-keyCount - 1; j) { node-keys[j] node-keys[j 1]; } node-keyCount--; return; } else { if (node-children[i]-keyCount 2) { // 从左子树取前驱替换 Node* predNode node-children[i]; while (!predNode-isLeaf) { // 进入孩子前先保证孩子至少2个关键字 int c predNode-keyCount; if (predNode-children[c]-keyCount 1) { if (c 0 predNode-children[c - 1]-keyCount 2) { borrowFromLeft(predNode, c); } else if (c predNode-keyCount predNode-children[c 1]-keyCount 2) { borrowFromRight(predNode, c); } else { if (c predNode-keyCount) --c; mergeChildren(predNode, c); } } predNode predNode-children[predNode-keyCount]; } node-keys[i] predNode-keys[predNode-keyCount - 1]; predNode-keyCount--; } else if (node-children[i 1]-keyCount 2) { // 取后继替换 Node* succNode node-children[i 1]; while (!succNode-isLeaf) { int c 0; if (succNode-children[c]-keyCount 1) { if (c succNode-keyCount succNode-children[c 1]-keyCount 2) { borrowFromRight(succNode, c); } else { mergeChildren(succNode, c); } } succNode succNode-children[0]; } node-keys[i] succNode-keys[0]; for (int j 0; j succNode-keyCount - 1; j) { succNode-keys[j] succNode-keys[j 1]; } succNode-keyCount--; } else { // 两个孩子都是2-节点合并后再删除 mergeChildren(node, i); removeFromNode(node-children[i], key); } } } else { if (node-isLeaf) { return; } Node* child node-children[i]; Node* leftSibling (i 0) ? node-children[i - 1] : nullptr; Node* rightSibling (i node-keyCount) ? node-children[i 1] : nullptr; if (child-keyCount 1) { if (rightSibling rightSibling-keyCount 2) { borrowFromRight(node, i); } else if (leftSibling leftSibling-keyCount 2) { borrowFromLeft(node, i); } else if (rightSibling) { mergeChildren(node, i); child node-children[i]; } else { mergeChildren(node, i - 1); child node-children[i - 1]; } } removeFromNode(child, key); } } public: TwoThreeFourTree() : root(nullptr) {} void insert(int key) { if (!root) { root new Node(); root-keys[0] key; root-keyCount 1; return; } if (root-keyCount 3) { Node* newRoot new Node(); newRoot-isLeaf false; newRoot-children[0] root; splitChild(newRoot, 0); root newRoot; } insertNonFull(root, key); } bool search(int key) { Node* cur root; while (cur) { int i 0; while (i cur-keyCount key cur-keys[i]) i; if (i cur-keyCount key cur-keys[i]) return true; if (cur-isLeaf) return false; cur cur-children[i]; } return false; } void remove(int key) { if (!root) return; removeFromNode(root, key); if (root-keyCount 0) { Node* old root; root root-isLeaf ? nullptr : root-children[0]; delete old; } } void inOrder() { inOrderRec(root); std::cout std::endl; } void inOrderRec(Node* node) { if (!node) return; for (int i 0; i node-keyCount; i) { if (!node-isLeaf) inOrderRec(node-children[i]); std::cout node-keys[i] ; } if (!node-isLeaf) inOrderRec(node-children[node-keyCount]); } }; int main() { TwoThreeFourTree tree; int testValues[] {10, 20, 5, 6, 12, 30, 7, 17, 8, 22, 25, 35, 40, 15, 3, 9}; for (int v : testValues) { tree.insert(v); } std::cout 中序遍历: ; tree.inOrder(); std::cout 查找 17: (tree.search(17) ? 找到 : 未找到) std::endl; std::cout 查找 99: (tree.search(99) ? 找到 : 未找到) std::endl; tree.remove(17); std::cout 删除 17 后中序遍历: ; tree.inOrder(); tree.remove(8); std::cout 删除 8 后中序遍历: ; tree.inOrder(); return 0; }7.2 代码说明和踩坑提醒这段代码里的删除部分我采用了“取前驱/后继替换 下探时预合并”的双重策略。有几个实现上的细节值得专门强调第一取前驱后继时不是简单地进入左子树找最大或右子树找最小而是要一边前进一边保证路径上的孩子节点至少有 2 个关键字。上面的代码里取前驱时每次进入最右孩子前都要检查最右孩子是否只有一个关键字并根据兄弟情况做借调或合并。这一步非常容易漏漏掉之后删除到一半就会遇到空节点程序崩溃或数据错乱。第二mergeChildren函数合并后要记得处理父节点的关键字。父节点会少一个关键字孩子也少一个。代码里先合并两个孩子再左移父节点的 keys 和 children。顺序错了会覆盖数据。第三根节点删除后可能变成 0 个关键字此时要判断它是不是叶子。如果是叶子整棵树为空如果是内部节点它还有唯一一个孩子这个孩子提升为新根高度减一。这个逻辑在remove函数的末尾处理。我用上面 main 函数里的数据反复跑了多轮又随机插入了上千个整数再随机删除最后用中序遍历校验有序性、用递归校验每个节点的子树高度一致都没有问题。但我不敢说这段代码覆盖了所有边界情况——2-3-4 树的删除分支组合非常多建议你把它当作一个“能跑的参考实现”自己加断言或把树打印出来逐一对照验证。7.3 如何自测一棵 2-3-4 树是否正确自测平衡树最有效的手段是写一个校验函数递归检查所有节点每个节点的 keyCount 必须在 1~3 之间每个节点的关键字严格递增每个节点的子树高度必须完全一致对每个关键字 k左子树所有关键字都小于 k右子树所有关键字都大于 k非叶节点的孩子数 keyCount 1。bool validate(Node* node, int height) { if (!node) { height 0; return true; } if (node-keyCount 1 || node-keyCount 3) return false; for (int i 1; i node-keyCount; i) { if (node-keys[i] node-keys[i - 1]) return false; } if (node-isLeaf) { height 1; return true; } if (node-keyCount 1 ! 4 node-keyCount 1) { // 2-节点必须正好2个孩子 if (node-children[2] ! nullptr || node-children[3] ! nullptr) return false; } int childHeight -1; for (int i 0; i node-keyCount; i) { int h 0; if (!validate(node-children[i], h)) return false; if (childHeight -1) childHeight h; else if (childHeight ! h) return false; } height childHeight 1; return true; }每做完一组插入删除操作就跑一遍这个校验函数。它能帮你快速定位是哪个节点出了问题省下大量调试时间。8. 2-3-4 树在实际工程中的定位与延伸聊了这么多基础原理最后说点工程上的体会。2-3-4 树本身在实际业务代码里不常见直接手写它的场景更是少之又少但它的思想渗透在大量基础组件里。数据库索引MySQL InnoDB 的聚簇索引就是 B 树。你把 2-3-4 树的关键字数上限放大到几千就是 B 树再把数据全放到叶节点、叶节点之间加链表就是 B 树。理解 2-3-4 树的分裂合并看 B 树的页分裂和页合并是降维打击。内存中的有序集合C 的 std::map/std::set 用红黑树实现Java 的 TreeMap/TreeSet 也是红黑树。红黑树因为只存一个关键字内存利用率比 2-3-4 树高但操作的逻辑本质完全来自 2-3-4 树。文件系统与日志结构一些 LSM-Tree 的存储引擎和文件系统设计里也会用到多路搜索树来做内存索引理解了 2-3-4 树你就能更快看懂这些系统的内存表MemTable实现。如果让我用一句话总结 2-3-4 树它是一棵用“允许节点存多个关键字”来换取绝对平衡的搜索树牺牲了节点的最小粒度换来了操作逻辑的统一性和对磁盘 IO 的友好性。对于学习数据结构的人它是连接二叉树世界和多路搜索树世界的桥。根据我的学习经验刷 LeetCode 级别的算法题很少直接考 2-3-4 树但面试官非常喜欢通过它来考察你对树结构本质的理解——比如问“红黑树和 B 树的区别”“为什么数据库不用 AVL 树”“B 树为什么适合做索引”。这些问题的答案其实都在 2-3-4 树这一层就已经打好了地基。所以不要在它身上蜻蜓点水值得花两三天认真啃透。 2-3-4树详解：从节点定义、查找插入删除到红黑树等价关系
1. 从二叉搜索树退化聊起为什么非要有 2-3-4 树很多初学数据结构的朋友第一个接触的树结构就是二叉搜索树BST当时觉得这玩意儿挺完美左小右大中序遍历有序查找、插入、删除看起来都是 O(log n)。但实际写代码跑数据就会发现问题——BST 的性能完全取决于插入顺序。你按 1、2、3、4、5 的顺序插入节点得到的就是一棵只有右孩子的链表查找 5 要遍历 5 个节点。数据量到十万、百万级别时这种退化是灾难性的。AVL 树通过旋转解决了这个问题强制左右子树高度差不超过 1但代价是插入删除时旋转操作频繁代码实现也比较绕。红黑树放宽了平衡条件用颜色标记和局部旋转把插入删除的调整控制在了常数级别但它那套“红黑性质”初看简直像魔法很多人背了规则却不懂为什么。2-3-4 树的意义恰恰在于它用一种更直观的方式回答了“如何让树始终平衡”这个问题——不靠旋转靠节点分裂和合并不限制节点只能存一个关键字而是让节点可以存 1 到 3 个关键字、拥有 2 到 4 个孩子。因为每次插入都在叶子节点进行叶子深度统一增加整棵树永远保持完美平衡所有叶子在同一层高度严格等于 ⌈log₄N⌉ 到 ⌈log₂N⌉ 之间。我第一次认真啃 2-3-4 树是在研究数据库索引原理的时候后来才发现这棵树就是 B 树的四阶特例理解了它B 树、B 树都不再是背概念而是自然而然的延伸。这篇文章我会把 2-3-4 树的定义、查找、插入、删除全部掰开揉碎讲清楚给出完整可运行的代码最后再讲透它和红黑树的等价关系。整篇更适合已经学过二叉树、对递归有一定感觉的读者当然只要你愿意多看两遍零基础也能跟下来。2. 节点定义与树的结构一个节点最多三个关键字2-3-4 树的名字来源于节点的孩子数量。每个节点要么有 2 个孩子此时存 1 个关键字、要么有 3 个孩子此时存 2 个关键字、要么有 4 个孩子此时存 3 个关键字。叶节点可以没有孩子但依然遵守关键字数量的约束。这里有个很容易混淆的地方很多人看到“2-3-4”以为是四种节点形态其实指的是一个节点可能拥有的孩子数不是关键字数。关键字数和孩子数的关系固定为节点类型孩子数关键字数结构示意2-节点21[key] 左子树 key 右子树3-节点32[k1, k2] 左 k1 中 k2 右4-节点43[k1, k2, k3] 左 k1 中1 k2 中2 k3 右每个节点的关键字按升序排列所有关键字互不重复。子树之间的顺序关系保持和 BST 一样的性质某一棵子树里的所有关键字都落在它对应的两个相邻关键字之间。你可以把 2-3-4 树理解成“多个 BST 节点合并成了一个超级节点”只不过这个超级节点自己维护了内部的关键字顺序。节点结构用 C 定义的话最简单的做法是用固定大小的数组enum NodeType { NODE_2, NODE_3, NODE_4 }; struct Node { int keys[3]; // 最多3个关键字 Node* children[4]; // 最多4个孩子 int keyCount; // 当前实际关键字数量 1~3 bool isLeaf; // 是否为叶节点 Node() : keyCount(0), isLeaf(true) { for (int i 0; i 4; i) children[i] nullptr; } };如果你用过 B 树的实现会发现这个结构基本就是 B 树节点的缩小版。实际上你把代码里的孩子数上限从 4 改成 M关键字数上限从 3 改成 M-1就得到了一棵 M 阶 B 树的雏形。所以从这个角度讲2-3-4 树是你通往 B 树体系最好的敲门砖。树的高度是另一个值得注意的点。因为有多个关键字合并存储2-3-4 树的高度明显比同样数据量的 BST 矮。一个存了 N 个关键字的 2-3-4 树高度最小时的所有节点都是 4-节点此时高度约等于 ⌈log₄N⌉高度最大时所有节点都是 2-节点退化为满二叉树高度约等于 ⌈log₂N⌉。这个“矮”带来的直接好处是查找时磁盘 IO 次数减少——数据库索引用 B 树而不是二叉树的根本原因也在这里。3. 查找操作和 BST 几乎一样的思路查找是 2-3-4 树里最简单的操作它和二叉搜索树的查找本质相同只不过每个节点要比较的不再是一个关键字而是一组关键字。从根节点开始在当前节点的关键字数组里做顺序查找因为最多 3 个关键字顺序查找比二分更快如果命中直接返回如果没命中根据待查找值落在哪个区间进入对应的孩子子树继续递归。到叶子节点还没命中说明关键字不存在。bool search(Node* root, int key) { Node* cur root; while (cur) { int i 0; while (i cur-keyCount key cur-keys[i]) i; if (i cur-keyCount key cur-keys[i]) { return true; } if (cur-isLeaf) { return false; } cur cur-children[i]; } return false; }注意两个细节。第一个while (i keyCount key keys[i])这个循环结束后i 指向第一个大于等于 key 的位置。如果这个位置关键字恰好等于 key说明找到了否则 key 应该落在 children[i] 代表的子树里。举例来说当前节点是 3-节点 [20, 40]要查 35循环后 i 1因为 35 20 但 35 40循环到 keys[1] 时条件不成立35 应该去 children[1] 这棵子树里找——也就是介于 20 和 40 之间的那棵子树。第二个递归可以改写成上面的非递归形式因为查找永远只沿着一条路径向下不需要回溯。非递归版本在 C 里更有效率也更好调试建议直接写成这种形式。查找复杂度方面最坏情况要比较 3 个关键字再下移一层所以单次查找的 CPU 比较次数最多约为 3 × ⌈log₂N⌉但树的高度比 BST 矮很多整体查找性能依然稳定在 O(log N)。而且实际场景里节点内部的关键字通常是连续内存存储顺序扫描 3 个整数在 CPU 缓存层面几乎无开销所以没有必要用二分查找。4. 插入操作自底向上分裂还是自顶向下预分裂4.1 自底向上的标准流程2-3-4 树插入最朴素的理解是模拟“多路搜索树的自然生长”。新关键字总是插入到叶子节点如果叶子节点有空间关键字数 3直接放进去并保持有序即可。麻烦的是插入后叶子节点变成 5-节点4 个关键字 5 个孩子这在 2-3-4 树里是不合法的。处理办法是把溢出的 4-节点“分裂”成两个 2-节点并把中间关键字上交给父节点。如果父节点因此也溢出就继续向上传递直到根节点。如果根节点也溢出就分裂根节点树的高度增加一层。这个流程描述起来很清晰但代码实现比较繁琐你需要维护从根到目标叶子的完整路径插入后逐层回溯处理每一层可能的溢出还要小心地维护 children 指针的移动。我第一次写这个版本时调试指针边界花了大半天。4.2 自顶向下预分裂让代码简单一个量级传统 B 树教学里常用自底向上分裂但在 2-3-4 树中自顶向下预分裂的思路才是更实用的方案。核心思想在沿路径向下搜索插入位置的过程中凡是遇到 4-节点就当场分裂把中间关键字上交给父节点并拆成两个 2-节点。这样保证到达叶子时叶子一定不是 4-节点插入后最多变成 4-节点绝对不会向上溢出。这个“先分裂、后插入”的策略把可能的级联调整消灭在了路径探索阶段插入结束后不需要任何回溯修正。代码写起来像 BST 插入一样顺只是每个节点进入前多了一步检查。那预分裂的具体规则是什么如果根节点是 4-节点分裂根节点中间关键字上移成为新根左右两个关键字变成两个新孩子节点。树的高度 1。如果路径上的某个节点是 4-节点将其分裂中间关键字上移到父节点剩下的两个关键字各自作为独立节点并挂接到父节点对应位置。举个具体例子假如当前树根节点是 4-节点 [50, 70, 90]现在要插入 60。根节点是 4-节点先分裂它70 上移成为新根50 和 90 各成一个节点作为新根的左右孩子。此时 70 的左孩子是 [50]右孩子是 [90]然后继续往下走找 60 的位置——60 大于 50 小于 70所以进入 [50] 这个节点。因为它是叶子且只有一个关键字直接插入变成 3-节点 [50, 60]。整个过程结束树的高度从 1 变成了 2而且依然全平衡。4.3 节点分裂的四种情况分裂 4-节点时根据父节点的形态不同操作细节也不同。我总结出四种情况分裂的是根节点父节点不存在。中间关键字成为新根左右两部分成为新根的两个孩子。分裂的是 2-节点的孩子父节点只有一个关键字把中间关键字直接插入父节点父节点变成 3-节点同时父节点原有一个孩子现在分裂出两个新孩子一共 3 个孩子正好匹配。分裂的是 3-节点的最左或最右孩子父节点有两个关键字把中间关键字插入父节点后父节点变成 4-节点。因为原父节点有 3 个孩子其中一个分裂成两个总共变成 4 个孩子恰好满配。分裂的是 3-节点的中间孩子父节点有两个关键字中间孩子分裂出的两个节点其中一个要插到父节点的两个孩子之间。只要找到正确的插入下标把后续孩子数组整体右移一位即可。只要把分裂操作封装成一个函数传入“要分裂的 4-节点指针”和“该节点在父节点 children 数组中的下标”上面的四种情况可以统一处理。void splitChild(Node* parent, int idx) { Node* full parent-children[idx]; // 待分裂的4-节点 Node* left new Node(); Node* right new Node(); left-keys[0] full-keys[0]; right-keys[0] full-keys[2]; left-keyCount right-keyCount 1; left-isLeaf right-isLeaf full-isLeaf; if (!full-isLeaf) { left-children[0] full-children[0]; left-children[1] full-children[1]; right-children[0] full-children[2]; right-children[1] full-children[3]; } // 父节点腾出位置插入中间关键字 for (int j parent-keyCount; j idx; --j) { parent-keys[j] parent-keys[j - 1]; parent-children[j 1] parent-children[j]; } parent-keys[idx] full-keys[1]; parent-children[idx] left; parent-children[idx 1] right; parent-keyCount; delete full; }这里注意细节children数组的长度是 4但父节点原有 keyCount1 个孩子。右移时children[j1] children[j]的操作要从最右边开始避免覆盖数据。这不是难写的代码但非常容易写错建议配合调试多走几遍。4.4 插入代码的全貌当你把预分裂做成了不变量——“路径上的节点一定不是 4-节点”插入就变得异常简单void insert(Node* root, int key) { if (!root) { root new Node(); root-keys[0] key; root-keyCount 1; return; } // 如果根是4-节点先分裂 if (root-keyCount 3) { Node* newRoot new Node(); newRoot-isLeaf false; newRoot-children[0] root; splitChild(newRoot, 0); root newRoot; } Node* cur root; while (true) { // 沿路径分裂4-节点 if (cur-keyCount 3) { // 理论上一路分裂下来不会出现这种情况 // 但为了鲁棒性可以在这里做防御 } int i 0; while (i cur-keyCount key cur-keys[i]) i; if (i cur-keyCount key cur-keys[i]) { // 重复关键字按需处理 return; } if (cur-isLeaf) { // 腾出位置并插入 for (int j cur-keyCount; j i; --j) { cur-keys[j] cur-keys[j - 1]; } cur-keys[i] key; cur-keyCount; return; } else { // 进入孩子前如果孩子是4-节点先分裂 Node* child cur-children[i]; if (child-keyCount 3) { splitChild(cur, i); // 分裂后 cur 新增了一个关键字需要重新确定 key 应该进哪个孩子 if (key cur-keys[i]) i; } cur cur-children[i]; } } }上面的核心点在于进入孩子前检查孩子是否是 4-节点是就分裂。分裂后父节点多了一个关键字所以 key 的走向可能需要重新判断。这里用的是if (key cur-keys[i]) i意思是如果 key 大于刚刚上移的中间关键字就应该去右边的孩子。这个判断非常重要漏掉它就会出现关键字放错子树的问题。顺便提一句重复关键字的处理策略取决于需求。大多数数据结构教材默认关键字唯一重复时直接忽略。如果允许重复有几种方案——把重复值放进右子树、给每个节点增加一个计数、或者干脆用链表把所有相同值串起来。不同方案对树的形态和删除逻辑都有影响实际工程里需要认真权衡。5. 删除操作所有平衡树里最棘手的部分如果说插入是顺水推舟那删除就是逆水行舟。2-3-4 树的删除之所以复杂核心问题和所有平衡树一样删掉一个关键字之后节点可能违反“最少 1 个关键字”的约束必须通过借调和合并来修复。5.1 删除的分类框架先说结论性的框架删除操作分两大情形情形一要删除的关键字在叶节点。直接删除即可如果删除后节点变成空节点就需要从父节点借一个关键字下来或者和兄弟节点合并。情形二要删除的关键字在内部节点。这时候不能直接删否则会留下一个没有关键字的空洞节点。标准做法是用前驱或后继关键字来替换待删除关键字然后把问题转化为删除叶节点里的那个关键字。这个过程和 BST 删除“用后继替换”的思路一模一样只是 2-3-4 树的每个节点可能有多个关键字前驱/后继的定义要相应扩展——前驱就是左子树里最大的关键字后继就是右子树里最小的关键字。用后继替换后删除问题就归结到了叶子上所以情形二的复杂度本质上是情形一的复杂度加上一次查找后继的过程。5.2 自顶向下的预合并策略和插入一样删除也可以采用自顶向下的策略把“节点可能变成空节点”的麻烦消灭在路径探索阶段。核心不变量是在向下搜索的过程中确保当前节点是一个至少含 2 个关键字的节点对于根节点允许只有 1 个关键字但必须保证它要么是叶节点要么有两个以上孩子。实际的操作规则是这样的每到一个节点查看接下来要进入的那个孩子。如果这个孩子只有 1 个关键字2-节点则视其兄弟节点的情况执行借调或合并保证进入的孩子至少有 2 个关键字。这样一路下来当你到达要删除的叶子时叶子至少有 2 个关键字删除后至少还剩 1 个不会产生空节点。5.3 借调与合并的两种情况假设当前节点是 cur目标孩子是 cur-children[i]且目标孩子只有 1 个关键字。情况一相邻兄弟节点有至少 2 个关键字。这时可以从兄弟节点“借”一个关键字过来过程其实经过了父节点中转把父节点的某个关键字下移到目标孩子里把兄弟节点的某个关键字上移到父节点刚才空出的位置把兄弟节点的某个子树挂接到目标孩子的对应位置。这个操作本质上和 AVL 树的旋转非常相似但因为在多关键字节点里发生看起来更像是“关键字的搬家”。举个例子父节点是 [30]左孩子是 [10]右孩子是 [25, 40]。现在要往左孩子方向走但左孩子只有 1 个关键字右兄弟有 2 个关键字。处理方法父节点的 30 下移到左孩子右兄弟的最小关键字 25 上移到父节点同时右兄弟的子树结构相应调整。左孩子从 [10] 变成 [10, 30]父节点变成 [25]右兄弟从 [25, 40] 变成 [40]。情况二相邻兄弟节点也只有 1 个关键字。这时没法借只能合并。把父节点的关键字下移和两个 2-节点合并成一个 3-节点父节点是 [30]左孩子是 [10]右孩子是 [25]。合并后把 30 下移和 [10]、[25] 结合成 [10, 25, 30]但这个节点是 4-节点不对注意两个 2-节点各有 1 个关键字加上父节点的 1 个关键字总共 3 个关键字所以合并后是一个 4-节点完全合法。父节点的关键字数减一孩子数减一。如果父节点因此变成空节点就继续向上递归处理。这个向上递归在自顶向下策略里很少真正发生因为每一层的下探都保证了目标孩子至少有 2 个关键字父节点通常不会因此变成空。5.4 删除操作的预合并版本代码框架预合并思路的删除实现先处理根节点如果根节点是 2-节点且有两个 2-节点的孩子先把根节点合并树高度减一。然后调用递归函数向下搜索。void remove(Node* root, int key) { if (!root) return; // 根节点为2-节点且两个孩子也是2-节点时先合并根 if (root-keyCount 1 root-isLeaf false) { if (root-children[0]-keyCount 1 root-children[1]-keyCount 1) { mergeRoot(root); } } removeFromNode(root, key); if (root-keyCount 0) { // 树为空或高度降低 Node* old root; root root-children[0]; delete old; } }核心递归函数removeFromNode按以下逻辑处理如果当前节点是叶子直接在 keys 数组里查找并删除目标关键字如果当前节点是内部节点根据 key 与节点内各关键字的大小关系决定进入哪个孩子进入孩子之前检查孩子和兄弟的关键字数执行借调或合并如果目标关键字就在当前内部节点中且其左右孩子都非叶子用后继替换找到右子树的最小关键字替换当前节点的目标关键字然后递归地从右子树删除那个最小关键字。如果右孩子是 2-节点先做借调/合并再递归。这里有个细节要特别提醒当目标关键字在当前内部节点时不能直接删。直接删会让那个位置变成空洞孩子数组的索引关系就被破坏了。必须用前驱或后继顶上把删除问题转移到一个保证不会产生空节点的叶子上。这个思路和 BST 删除一模一样但实现时要更小心因为节点里有多个关键字和多个孩子。5.5 我的建议先实现基础版再考虑预合并预合并版本代码虽然逻辑上优雅但第一次接触的人很容易在借调条件判断上写错。我的学习建议是分成两步走第一步先实现自底向上的朴素删除。允许删除后节点变空然后递归回溯修复空节点。这个版本逻辑直白虽然代码量大但每一步都清楚。第二步理解自顶向下预合并的思想再用它简化代码。在纸上画几棵完整的 2-3-4 树把 2-节点的删除、3-节点内部关键字的删除、4-节点删除逐一遍历一遍。我当年学这棵树时就是用这种方法把红黑树的删除也一并搞懂了——因为两者的处理逻辑本质上就是同一套思路的不同表达。6. 与红黑树的等价关系看透本质的关键一步6.1 为什么红黑树和 2-3-4 树是同一棵树这是 2-3-4 树最有价值的一个知识点。红黑树不是一棵抽象出来的独立数据结构它就是 2-3-4 树在“每个节点最多只有一个关键字”约束下的二叉树编码表示。理解这个等价关系红黑树里的“黑高”“红节点连续不允许”“插入删除的旋转规则”就不再是背下来的魔法而是 2-3-4 树节点操作在二叉树上的自然投影。怎么把 2-3-4 树变成红黑树规则如下2-节点直接变成一个黑色节点。3-节点变成一黑一红两个节点红节点是黑节点的左孩子或右孩子。红节点代表它和黑节点“原本在同一个 2-3-4 树节点里”。4-节点变成一个黑色节点带两个红色孩子。黑色节点对应 4-节点的中间关键字两个红色孩子分别对应左右两个关键字。这里有一个非常微妙的点3-节点的两种转换方式红色在左还是红色在右会导致不同的红黑树形态但都指代同一棵 2-3-4 树。这也是为什么同一个 2-3-4 树可以对应多棵红黑树。6.2 等价关系给红黑树操作带来的启发红黑树的所有旋转操作都可以还原成 2-3-4 树的节点借调或合并。举个例子红黑树插入后的“变色旋转”修正对应的是 2-3-4 树插入时的节点分裂。红黑树里叔叔节点是红色时的变色操作本质上是 2-3-4 树中 4-节点分裂把中间关键字上移到父节点。红黑树里的左旋右旋本质上是 2-3-4 树中 3-节点从一种形态转成另一种形态。这个等价关系给学习者的最大帮助是调试。如果你在写红黑树删除时不知道某个 case 为什么这么做把树还原成 2-3-4 树去看看——那个 case 很可能就是在处理 2-节点的借调和合并。我在学习红黑树时曾经花了一整晚追一个新的 case最后还原成 2-3-4 树才发现那不过是“3-节点兄弟借一个关键字”的边界情形。6.3 从 2-3-4 树到 B 树的延伸2-3-4 树是阶数 M4 的 B 树。把节点关键字数上限从 3 推广到 M-1孩子数上限从 4 推广到 M插入删除的分裂合并逻辑不需要任何本质变化就得到了通用的 B 树。数据库索引用的 B 树和 2-3-4 树的区别主要有三点所有数据都存放在叶节点内部节点只存索引关键字叶节点之间有指针串联方便范围查询内部节点只用于导航。但底层那套“节点满则分裂、节点空则合并”的思想完全继承自 2-3-4 树。所以学透 2-3-4 树等于同时拿下了红黑树和 B 树家族的地基。7. 完整代码实现与运行验证7.1 完整 C 代码我把一棵支持查找、插入、删除和中序遍历的 2-3-4 树完整实现放在下面。代码尽可能保持了可读性删除了大量防御性检查只保留核心逻辑方便你对照阅读。我建议不要直接拿去生产环境而是先对着代码把每一条分支走一遍再亲手画树验证。#include iostream class TwoThreeFourTree { private: struct Node { int keys[3]; Node* children[4]; int keyCount; bool isLeaf; Node() : keyCount(0), isLeaf(true) { for (int i 0; i 4; i) children[i] nullptr; } }; Node* root; void splitChild(Node* parent, int idx) { Node* full parent-children[idx]; Node* left new Node(); Node* right new Node(); left-keys[0] full-keys[0]; right-keys[0] full-keys[2]; left-keyCount right-keyCount 1; left-isLeaf right-isLeaf full-isLeaf; if (!full-isLeaf) { left-children[0] full-children[0]; left-children[1] full-children[1]; right-children[0] full-children[2]; right-children[1] full-children[3]; } for (int j parent-keyCount; j idx; --j) { parent-keys[j] parent-keys[j - 1]; parent-children[j 1] parent-children[j]; } parent-keys[idx] full-keys[1]; parent-children[idx] left; parent-children[idx 1] right; parent-keyCount; delete full; } void borrowFromRight(Node* parent, int idx) { Node* child parent-children[idx]; Node* sibling parent-children[idx 1]; child-keys[child-keyCount] parent-keys[idx]; child-children[child-keyCount 1] sibling-children[0]; child-keyCount; parent-keys[idx] sibling-keys[0]; for (int j 0; j sibling-keyCount - 1; j) { sibling-keys[j] sibling-keys[j 1]; } for (int j 0; j sibling-keyCount; j) { sibling-children[j] sibling-children[j 1]; } sibling-keyCount--; } void borrowFromLeft(Node* parent, int idx) { Node* child parent-children[idx]; Node* sibling parent-children[idx - 1]; for (int j child-keyCount; j 0; --j) { child-keys[j] child-keys[j - 1]; } for (int j child-keyCount 1; j 0; --j) { child-children[j] child-children[j - 1]; } child-keys[0] parent-keys[idx - 1]; child-children[0] sibling-children[sibling-keyCount]; child-keyCount; parent-keys[idx - 1] sibling-keys[sibling-keyCount - 1]; sibling-keyCount--; } void mergeChildren(Node* parent, int idx) { Node* left parent-children[idx]; Node* right parent-children[idx 1]; left-keys[left-keyCount] parent-keys[idx]; for (int j 0; j right-keyCount; j) { left-keys[left-keyCount 1 j] right-keys[j]; } if (!left-isLeaf) { for (int j 0; j right-keyCount; j) { left-children[left-keyCount 1 j] right-children[j]; } } left-keyCount left-keyCount 1 right-keyCount; for (int j idx; j parent-keyCount - 1; j) { parent-keys[j] parent-keys[j 1]; parent-children[j 1] parent-children[j 2]; } parent-keyCount--; delete right; } void insertNonFull(Node* node, int key) { int i 0; while (i node-keyCount key node-keys[i]) i; if (i node-keyCount key node-keys[i]) { return; } if (node-isLeaf) { for (int j node-keyCount; j i; --j) { node-keys[j] node-keys[j - 1]; } node-keys[i] key; node-keyCount; } else { Node* child node-children[i]; if (child-keyCount 3) { splitChild(node, i); if (key node-keys[i]) i; child node-children[i]; } insertNonFull(child, key); } } void removeFromNode(Node* node, int key) { int i 0; while (i node-keyCount key node-keys[i]) i; if (i node-keyCount key node-keys[i]) { if (node-isLeaf) { for (int j i; j node-keyCount - 1; j) { node-keys[j] node-keys[j 1]; } node-keyCount--; return; } else { if (node-children[i]-keyCount 2) { // 从左子树取前驱替换 Node* predNode node-children[i]; while (!predNode-isLeaf) { // 进入孩子前先保证孩子至少2个关键字 int c predNode-keyCount; if (predNode-children[c]-keyCount 1) { if (c 0 predNode-children[c - 1]-keyCount 2) { borrowFromLeft(predNode, c); } else if (c predNode-keyCount predNode-children[c 1]-keyCount 2) { borrowFromRight(predNode, c); } else { if (c predNode-keyCount) --c; mergeChildren(predNode, c); } } predNode predNode-children[predNode-keyCount]; } node-keys[i] predNode-keys[predNode-keyCount - 1]; predNode-keyCount--; } else if (node-children[i 1]-keyCount 2) { // 取后继替换 Node* succNode node-children[i 1]; while (!succNode-isLeaf) { int c 0; if (succNode-children[c]-keyCount 1) { if (c succNode-keyCount succNode-children[c 1]-keyCount 2) { borrowFromRight(succNode, c); } else { mergeChildren(succNode, c); } } succNode succNode-children[0]; } node-keys[i] succNode-keys[0]; for (int j 0; j succNode-keyCount - 1; j) { succNode-keys[j] succNode-keys[j 1]; } succNode-keyCount--; } else { // 两个孩子都是2-节点合并后再删除 mergeChildren(node, i); removeFromNode(node-children[i], key); } } } else { if (node-isLeaf) { return; } Node* child node-children[i]; Node* leftSibling (i 0) ? node-children[i - 1] : nullptr; Node* rightSibling (i node-keyCount) ? node-children[i 1] : nullptr; if (child-keyCount 1) { if (rightSibling rightSibling-keyCount 2) { borrowFromRight(node, i); } else if (leftSibling leftSibling-keyCount 2) { borrowFromLeft(node, i); } else if (rightSibling) { mergeChildren(node, i); child node-children[i]; } else { mergeChildren(node, i - 1); child node-children[i - 1]; } } removeFromNode(child, key); } } public: TwoThreeFourTree() : root(nullptr) {} void insert(int key) { if (!root) { root new Node(); root-keys[0] key; root-keyCount 1; return; } if (root-keyCount 3) { Node* newRoot new Node(); newRoot-isLeaf false; newRoot-children[0] root; splitChild(newRoot, 0); root newRoot; } insertNonFull(root, key); } bool search(int key) { Node* cur root; while (cur) { int i 0; while (i cur-keyCount key cur-keys[i]) i; if (i cur-keyCount key cur-keys[i]) return true; if (cur-isLeaf) return false; cur cur-children[i]; } return false; } void remove(int key) { if (!root) return; removeFromNode(root, key); if (root-keyCount 0) { Node* old root; root root-isLeaf ? nullptr : root-children[0]; delete old; } } void inOrder() { inOrderRec(root); std::cout std::endl; } void inOrderRec(Node* node) { if (!node) return; for (int i 0; i node-keyCount; i) { if (!node-isLeaf) inOrderRec(node-children[i]); std::cout node-keys[i] ; } if (!node-isLeaf) inOrderRec(node-children[node-keyCount]); } }; int main() { TwoThreeFourTree tree; int testValues[] {10, 20, 5, 6, 12, 30, 7, 17, 8, 22, 25, 35, 40, 15, 3, 9}; for (int v : testValues) { tree.insert(v); } std::cout 中序遍历: ; tree.inOrder(); std::cout 查找 17: (tree.search(17) ? 找到 : 未找到) std::endl; std::cout 查找 99: (tree.search(99) ? 找到 : 未找到) std::endl; tree.remove(17); std::cout 删除 17 后中序遍历: ; tree.inOrder(); tree.remove(8); std::cout 删除 8 后中序遍历: ; tree.inOrder(); return 0; }7.2 代码说明和踩坑提醒这段代码里的删除部分我采用了“取前驱/后继替换 下探时预合并”的双重策略。有几个实现上的细节值得专门强调第一取前驱后继时不是简单地进入左子树找最大或右子树找最小而是要一边前进一边保证路径上的孩子节点至少有 2 个关键字。上面的代码里取前驱时每次进入最右孩子前都要检查最右孩子是否只有一个关键字并根据兄弟情况做借调或合并。这一步非常容易漏漏掉之后删除到一半就会遇到空节点程序崩溃或数据错乱。第二mergeChildren函数合并后要记得处理父节点的关键字。父节点会少一个关键字孩子也少一个。代码里先合并两个孩子再左移父节点的 keys 和 children。顺序错了会覆盖数据。第三根节点删除后可能变成 0 个关键字此时要判断它是不是叶子。如果是叶子整棵树为空如果是内部节点它还有唯一一个孩子这个孩子提升为新根高度减一。这个逻辑在remove函数的末尾处理。我用上面 main 函数里的数据反复跑了多轮又随机插入了上千个整数再随机删除最后用中序遍历校验有序性、用递归校验每个节点的子树高度一致都没有问题。但我不敢说这段代码覆盖了所有边界情况——2-3-4 树的删除分支组合非常多建议你把它当作一个“能跑的参考实现”自己加断言或把树打印出来逐一对照验证。7.3 如何自测一棵 2-3-4 树是否正确自测平衡树最有效的手段是写一个校验函数递归检查所有节点每个节点的 keyCount 必须在 1~3 之间每个节点的关键字严格递增每个节点的子树高度必须完全一致对每个关键字 k左子树所有关键字都小于 k右子树所有关键字都大于 k非叶节点的孩子数 keyCount 1。bool validate(Node* node, int height) { if (!node) { height 0; return true; } if (node-keyCount 1 || node-keyCount 3) return false; for (int i 1; i node-keyCount; i) { if (node-keys[i] node-keys[i - 1]) return false; } if (node-isLeaf) { height 1; return true; } if (node-keyCount 1 ! 4 node-keyCount 1) { // 2-节点必须正好2个孩子 if (node-children[2] ! nullptr || node-children[3] ! nullptr) return false; } int childHeight -1; for (int i 0; i node-keyCount; i) { int h 0; if (!validate(node-children[i], h)) return false; if (childHeight -1) childHeight h; else if (childHeight ! h) return false; } height childHeight 1; return true; }每做完一组插入删除操作就跑一遍这个校验函数。它能帮你快速定位是哪个节点出了问题省下大量调试时间。8. 2-3-4 树在实际工程中的定位与延伸聊了这么多基础原理最后说点工程上的体会。2-3-4 树本身在实际业务代码里不常见直接手写它的场景更是少之又少但它的思想渗透在大量基础组件里。数据库索引MySQL InnoDB 的聚簇索引就是 B 树。你把 2-3-4 树的关键字数上限放大到几千就是 B 树再把数据全放到叶节点、叶节点之间加链表就是 B 树。理解 2-3-4 树的分裂合并看 B 树的页分裂和页合并是降维打击。内存中的有序集合C 的 std::map/std::set 用红黑树实现Java 的 TreeMap/TreeSet 也是红黑树。红黑树因为只存一个关键字内存利用率比 2-3-4 树高但操作的逻辑本质完全来自 2-3-4 树。文件系统与日志结构一些 LSM-Tree 的存储引擎和文件系统设计里也会用到多路搜索树来做内存索引理解了 2-3-4 树你就能更快看懂这些系统的内存表MemTable实现。如果让我用一句话总结 2-3-4 树它是一棵用“允许节点存多个关键字”来换取绝对平衡的搜索树牺牲了节点的最小粒度换来了操作逻辑的统一性和对磁盘 IO 的友好性。对于学习数据结构的人它是连接二叉树世界和多路搜索树世界的桥。根据我的学习经验刷 LeetCode 级别的算法题很少直接考 2-3-4 树但面试官非常喜欢通过它来考察你对树结构本质的理解——比如问“红黑树和 B 树的区别”“为什么数据库不用 AVL 树”“B 树为什么适合做索引”。这些问题的答案其实都在 2-3-4 树这一层就已经打好了地基。所以不要在它身上蜻蜓点水值得花两三天认真啃透。