Olverae Assets

1 一句话定义

2-3-4 树是一棵每个节点能装 1~3 个键的搜索树：装满（3 个键 = 4-节点）就裂开、把中键顶上去，靠这一招让所有叶子永远停在同一层——天生绝对平衡。

BST 会长歪、AVL 要靠旋转扶正；2-3-4 树换了个思路：不往下加层，而是让节点先"变胖"。键不够 3 个就继续塞进同一个节点；一旦塞到第 4 个（4-节点），就把中间那个键往上顶给父亲、自己裂成两半。由于"长高"只发生在顶部（裂根），整棵树所有叶子始终齐平，查找/插入稳定 O(log n)。

三种节点：k 个键的节点正好有 k+1 个孩子，孩子按键划分大小区间（如 [20|40] 的三个孩子分别管 <20、20~40、>40）。下方这棵小树三个叶子都在同一层——这就是 2-3-4 的招牌。

2 模型 · 看插入怎么"边走边裂"

分两小步：第 1 步先弄懂"一个节点里，值该往哪个孩子走"；第 2 步看插入时遇到满节点（4-节点）怎么裂开、把中键顶上去。

第 1 步 · 值往哪个孩子走？（点点看）

一个节点里的键把数轴切成几段，每段对应一个孩子。比如 3-节点 [17 | 42] 把数轴切成三段。输入一个数，看它落进哪一段、于是走第几个孩子

孩子 0
< 17 17 孩子 1
17 ~ 42 42 孩子 2
> 42

给定位 →

规律：有 k 个键，就有 k+1 个孩子。"值往哪走" = 数一数有几个键比它小，那个数就是孩子的编号。查找和插入下行时，每一步都这么做。

你刚才点的那条规律，写成代码就是这 4 行（后面插入演示里会反复调用它）：

// 在节点 n 里，值 v 该往第几个孩子走
int childIndex(struct node *n, int v) {
    int i = 0;
    while (i < n->numKeys && v > n->key[i]) i++;  // 数有几个键比 v 小
    return i;                                   // 这个数就是孩子编号
}

节点在代码里长什么样

一个节点要能装最多 3 个键、最多 4 个孩子，外加记一下当前装了几个键：

struct node {
    int numKeys;            // 当前键数：1 / 2 / 3
    int key[3];             // 最多 3 个键，保持升序
    struct node *child[4];  // 比键数多一个；叶子时全是 NULL
};

// 造一个新节点：先装一个键 v，孩子全空（叶子）
struct node *newNode(int v) {
    struct node *n = malloc(sizeof(struct node));
    n->numKeys = 1;  n->key[0] = v;
    for (int i = 0; i < 4; i++) n->child[i] = NULL;
    return n;
}

// 下面三个助手由例题脚手架提供（签名如下），你只需写主干 insert：
int  childIndex(struct node *n, int v);  // v 该走第几个孩子（0..numKeys）
void splitChild(struct node *p, int i);  // 把满的 p->child[i] 裂开，中键提到 p
struct node *splitRoot(struct node *root); // 根是 4-节点时裂根，返回新根
void insertLeaf(struct node *leaf, int v); // 在叶子里按升序插一个键

插入策略叫「自顶向下、边走边裂」：从根往下找插入位置，路上只要遇到 4-节点就先把它裂开（中键顶给父亲），这样父亲一定有空位接住、绝不会连环爆。下面就来看这个完整的 insert 代码怎么一行行跑。

第 2 步 · 看 insert 一行行跑。右边就是真实 C 代码，会随动画逐行高亮当前执行到哪。关键直觉：4-节点（满了）一旦挡路就裂开，中键升给父亲；裂根是树唯一长高的方式，所以叶子永远齐平。点下面三个例子，再点 ▶ 慢慢看（建议 0.5×）。

代码里 childIndex（上面已给）负责"往哪走"；splitRoot / splitChild 负责"把 4-节点裂开、中键上提"，insertLeaf 负责"在叶子里有序插一个键"——这三个小助手在例题脚手架里已给好，你只需照着这段 insert 把主干写出来。

2-3-4 树插入演示

真实 C 代码 · insert（当前执行行高亮）

颜色说明

当前节点正在裂开的 4-节点裂出的新节点

提示

点上方一个例子，再点 ▶ 看插入怎么一步步下行、遇满则裂。

层数（叶子都在底层）

—

当前根的键

3 核心要点 · 4 句人话看懂 2-3-4 树

每张卡片先用一句大白话说清"它到底在讲什么"，再配最小例子。

① 节点能装多个键（2/3/4-节点）

一句话：和 BST"一格一个值"不同，2-3-4 的一个节点能挤 1~3 个键。k 个键就配 k+1 个孩子，孩子各管一段大小区间。

2-节点=1 键 2 娃，3-节点=2 键 3 娃，4-节点=3 键 4 娃（已满）。节点内的键始终升序排列。

2-节点: [30] → 2 个孩子

3-节点: [20|40] → 3 个孩子

4-节点: [20|40|60] → 4 个孩子（满）

② 满了就裂：中键上提

一句话：4-节点是"满载"。再要往这边塞，就把它裂成两半，中间那个键顶给父亲，左右各成一个 2-节点。

中键上提后，父亲多了一个键、多了一个孩子。"自顶向下"策略会在下行途中提前裂掉挡路的 4-节点，所以父亲永远有空位接。

裂 [20|40|60]：

40 ↑ 提给父亲

[20] [60] ← 左右两个 2-节点

③ 为什么永远平衡

一句话：裂变只会把键往上推，树长高只发生在裂根那一刻——而裂根让每条路径同时 +1 层，所以叶子永远齐平。

不像 BST 可能一头沉。2-3-4 树所有叶子严格同层，高度恒为 O(log n)，查找/插入/删除都稳定 O(log n)。

普通插入：键在原层裂、上提

裂根：整棵树 +1 层（唯一长高）

⟹ 叶子永远在同一层

④ 它和红黑树是"一对"

一句话：2-3-4 树概念清楚但实现笨重；红黑树就是它的"二叉化"等价版——同样的平衡逻辑，用红/黑色边代替"胖节点"。

考试常考手算裂变（4-node 分裂 / 中键上提）和"插入后根变成谁"。实际工程里更多见红黑树（C++ map、Java TreeMap）。

2-3-4 树：节点变胖 → 裂变

红黑树：保持二叉 → 变色 + 旋转

两者等价，平衡逻辑相同

4 错误实验室 · 点一下亲眼看 bug

下面 4 个是 2-3-4 树最常翻车的坑——第 ① 个正是考试爱挖的"级联裂变"。点击卡片，控制台会模拟运行效果。

① 裂变时父亲也满了（级联）

自底向上裂、却没处理"父亲已是 4-节点" → 中键无处可放

② 不裂直接塞第 4 个键

往 4-节点再插一个 → 5 个键，越界、不再是合法节点

③ 上提的不是"中键"

提了最小或最大键 → 大小顺序乱掉，不再是搜索树

④ 根满了却不裂根

只在中途裂、忘了根也可能是 4-节点 → 中键无父可提

// 点击上方任一卡片，查看错误代码与运行效果

$ ./a.out （等待运行...）

5 即时小测 · 5 题 + 动手例题

这 5 题都卡在初学者最常错的点上——节点类型、值往哪走、裂变结果、为什么平衡、插入后的根。最后到练习系统亲手算一次裂变。

去做例题：2-3-4 树 · 插入后的根

去做例题

读完这节，你应该明白：

2-3-4 树和 AVL 是同一个目标（保持平衡）的两条不同路线。AVL 维持二叉、靠旋转扶正；2-3-4 树让节点变胖（1~3 个键），靠裂变保持平衡。规则就一条主线：下行途中遇到 4-节点（含根）就先裂开，把中键顶给父亲，于是父亲永远有空位、绝不连环爆；而树长高只发生在裂根那一刻，且让所有路径同时 +1 层，所以叶子永远齐平、高度恒为 O(log n)。考试爱考"手算裂变"和"插入后根变成谁"。它的二叉化等价物就是工程里更常用的红黑树 ↓

2-3-4 Trees

2-3-4 树