1. 从二叉搜索树的失衡困境说起如果你学过二叉搜索树BST大概都遇到过这样一个场景明明叫搜索树但插入一组有序数据比如 1、2、3、4、5树就变成了一条直线。查找 5 很快但查找 1 要一路走到树底。更糟的是这种退化在真实场景里太常见了——日志时间戳、自增ID、订单编号哪一样不是近乎有序的数据BST 在这种输入下直接退化成链表查找复杂度从 O(log n) 掉到 O(n)。于是人们想尽办法给树治病。AVL 树通过旋转维持平衡任何节点的左右子树高度差不超过 1这是一种很严格的平衡但代价是插入、删除时经常要旋转而且旋转次数多的时候会显得有点折腾。红黑树放宽了平衡条件用颜色标记和一系列变色、旋转规则把树控制在近似平衡的状态工程里用得极多比如 Java 的 TreeMap、STL 的 map。可是你有没有想过有没有一种树天生就是完美平衡的不需要旋转结构本身就是平衡的保证有就是本文的主角——2-3树。我第一次接触 2-3 树是在学 B 树之前当时觉得它多此一举节点里还能放两个键、三个孩子乱糟糟的。直到把插入和删除的完整过程走了一遍才意识到 2-3 树的设计有多么干净它不靠旋转不靠颜色只靠分裂和合并就维持了绝对的平衡——所有叶子节点都在同一层。这个性质放在任何 BST 变体里都是降维打击级别的。这篇文章写给三类人正在准备考研数据结构的人2-3树是408和许多高校自命题的常客、刚开始学 B 树和红黑树但被各种旋转规则绕晕的人以及单纯想搞明白为什么会有这种奇怪的树的探索型学习者。我会把这棵树的查找、插入、删除全部拆开讲每一步都配例子还会聊清楚它和红黑树、B 树之间的血缘关系。看完你会发现红黑树那些黑红黑红的规则本质上就是在模拟 2-3 树的行为。2. 2-3 树到底长什么样2 节点与 3 节点2.1 先忘掉二叉树的直觉传统二叉树的定义是每个节点最多有两个孩子节点里存一个键。2-3 树把这个定义推翻了它的节点有两种形态2 节点存 1 个键有 2 个孩子如果没有孩子那它就是叶子节点。3 节点存 2 个键有 3 个孩子如果没有孩子它也是叶子节点。注意命名里2和3指的是孩子数量不是键的数量。2 节点有两个孩子所以叫23 节点有三个孩子所以叫3。这个命名初学者很容易搞反我当年就以为2 节点存 2 个键结果后面全乱了。记住这个对应关系键数 孩子数 - 1。2.2 中序遍历依然有序2-3 树仍然是一棵搜索树所以它继承了 BST 的核心性质中序遍历结果是有序序列。只不过因为 3 节点里有两个键比较顺序要额外小心。对于一个 3 节点假设它存两个键 a 和 b且 a b那么它的三个孩子分别对应左子树的所有键 a中间子树的所有键在 a 和 b 之间右子树的所有键 b这个三路划分是 2-3 树一切操作的基础。你可以把它理解成普通的 BST 在每个节点只做一个二选一的决策去左还是去右而 2-3 树的 3 节点让你做三选一的决策。多一个选择树的高度就有机会变得更矮。2.3 完美平衡的定义2-3 树最核心的性质只有一条从根节点到任意叶子节点的路径长度完全相等。这意味着什么意味着这种树天生不会出现左边很深、右边很浅的情况。不管插入什么顺序的数据所有叶子都在同一层。这就是标题里说的完美平衡——不是近似平衡不是旋转出来的平衡而是结构本身就保证的平衡。每插入一个数据树可能会长高但只有一种情况会让树长高根节点分裂。换句话说树的高度增加是整体抬升而不是局部生长。这个特性让 2-3 树的高度始终保持在 O(log n) 的量级。可以做一个粗略的推算高度为 h 的 2-3 树最少能容纳多少节点如果所有节点都是 2 节点那它其实退化成了一棵满二叉树节点数是 2^h - 1但这是最少的情况。如果所有节点都是 3 节点节点数是 3^h - 1这是最多的情况。所以对于 n 个键的 2-3 树高度 h 大致满足log₃(n1) ≤ h ≤ log₂(n1)也就是说树的高度介于 log₃n 和 log₂n 之间。即便在最坏情况下查找也要 O(log₂n) 次比较比链表的 O(n) 好了太多。3. 查找操作在三岔路口做选择查找是 2-3 树里最简单的操作理解了它后面插入删除的定位阶段就不容易迷路。3.1 查找的完整流程假设我们要在 2-3 树里查找键 x从根节点开始如果当前节点是2 节点设它存的键为 ax 等于 a找到了返回。x 小于 a进入左孩子继续找。x 大于 a进入右孩子继续找。如果当前节点是3 节点设它存的两个键为 a 和 ba bx 等于 a 或等于 b找到了返回。x 小于 a进入左孩子继续找。x 大于 a 且小于 b进入中间的孩子继续找。x 大于 b进入右孩子继续找。如果走到了空指针null说明 x 不在树中查找失败。这个流程本质上和 BST 的查找一模一样唯一区别就是多了一个中间方向的判断。你可以把 3 节点看作一个双桶先和 a 比再和 b 比然后决定走哪条岔路。3.2 为什么查找效率这么高我记得第一次算 2-3 树的查找复杂度时最惊讶的一点是它不需要像平衡 BST 那样在查找过程中做任何额外操作——没有旋转没有调整就是一路向下比大小。查找一个键最多需要比较多少次路径长度 h 是 O(log₂n)每一层最多比较 2 次遇到 3 节点时先和 a 比再和 b 比所以总比较次数不超过 2h也就是 O(log n)。这个上界是非常稳的因为完美平衡已经保证了最坏情况就是 log₂n 级别。我在写代码模拟 2-3 树时经常先把查找函数写出来测试因为它是后续 insert、delete 里定位目标节点的骨架。记住一点插入先查找删除先查找所有操作都从根开始往下走这和 BST 的习惯完全一致。4. 插入操作分裂与上溢平衡的秘密武器插入是 2-3 树的精髓所在也是第一次让人惊叹原来平衡可以这么优雅的地方。4.1 插入的第一步永远从叶子开始2-3 树的插入策略和 BST 有一个本质区别BST 插入新节点是挂在树上的新节点永远是叶子而 2-3 树的插入是把键塞进已有的叶子节点里塞不下了再想办法。所以插入的第一步是先做一次查找找到按理说应该待的叶子节点。如果查找过程中发现了相同的键那就直接返回不允许重复键当然你可以在实现里定义重复键的语义但标准 2-3 树假设键互异。找到叶子节点后分两种基本情况叶子是2 节点直接把新键塞进去变成3 节点。完事树仍然平衡。叶子是3 节点这时候塞不下了于是进入分裂流程。4.2 3 节点插入临时 4 节点与分裂当一个 3 节点存 a、b 两个键要插入一个新键 x 时我们先假装它是可以装 3 个键、4 个孩子的临时 4 节点把 x 放进去并排序。假设排序结果是 a x b其他顺序同理。然后把这个临时 4 节点分裂成两个 2 节点a 单独作为一个节点b 单独作为一个节点中间的键 x上溢到父节点。这个上溢是整个插入操作的核心动作。上溢到父节点以后父节点可能也会从 2 节点变成 3 节点皆大欢喜也可能从 3 节点变成临时 4 节点麻烦继续然后继续分裂、继续上溢……直到某个祖先节点接得住为止。4.3 上溢的传播与根节点分裂上溢传播的具体逻辑是这样的父节点是2 节点把上溢的键塞进去父节点变成 3 节点传播结束。父节点是3 节点父节点变成临时 4 节点继续把中间键上溢到它的父节点。注意此时原父节点也要分裂成两个 2 节点。这个过程一直向上走。如果一路走到了根节点根节点也变成临时 4 节点怎么办那就把根分裂成两个 2 节点并把中间键提升为新的根节点。这是唯一一种让 2-3 树高度增加的情况。整个树的高度从中间长高了一层所有叶子仍然在同一层。你看看这个设计高度增加并不是因为某个分支长太快而是因为根节点分家了——全局所有路径同时加长完美平衡没有受到任何破坏。我给一个具体的例子来演示。假设现在有棵空树依次插入键10、20、30、40、50、60。插入 10根是一个 2 节点存 10。插入 2010 是 2 节点直接变成 3 节点存 10、20。插入 30根是 3 节点临时变成 (10, 20, 30)分裂为 10 和 30 两个节点20 上溢成新根。此时树变成根是 20左孩子是 10右孩子是 30。插入 40先找到右孩子30 是 2 节点直接变成 3 节点存 30、40。插入 50右孩子变成临时 4 节点 (30, 40, 50)分裂为 30 和 5040 上溢给根。根现在是 20 和 40 组成的 3 节点两个新分裂出来的节点 30、50 分别挂在中孩子和右孩子位置。此时结构为根 (20, 40)左孩子 10中孩子 30右孩子 50。插入 60右孩子 50 是 2 节点变成 3 节点存 50、60。你看最终这棵树所有叶子都在同一层结构非常整齐。整个过程中我只用了塞进节点和分裂上溢两个动作没有一次旋转。4.4 插入的代码思路如果让你手写 2-3 树插入函数是递归写起来最自然的递归搜索到叶子节点执行插入。返回一个上溢键如果有的话给父节点。父节点收到上溢键后尝试合并进自己如果自己也变成 4 节点就再次分裂并把中间键上溢。这种自底向上返回上溢键的模式和很多平衡树里自底向上回溯调整的思想是一样的理解了它后面学 B 树、B 树插入时几乎零成本迁移。5. 删除操作最绕人的环节但有一套固定打法删除是 2-3 树里最复杂、也最劝退初学者的地方。好消息是它的原理非常机械只要掌握了转化为删除叶子 处理下溢这两步就不会乱。5.1 删除的总策略先转为删除叶子节点回想 BST 的删除如果要删的节点有两个孩子就找它的前驱或后继替换值然后删掉那个前驱/后继节点。这个思路在 2-3 树里完全适用原因很简单2-3 树的中序遍历是有序的前驱或后继一定在叶子节点上这不是 2-3 树特有的性质BST 里也是这样但 2-3 树里更直观。所以删除的流程是先查找要删除的键 x。如果 x 在内部节点里找到它的中序前驱左子树中最大的键或中序后继右子树中最小的键用这个键替换 x。此时删除操作转化为删除那个前驱/后继所在的叶子节点里的键。这个转化特别重要。删内部节点的键会破坏树结构但删叶子节点的键最多让叶子节点变瘦处理起来就单纯多了。5.2 删除叶子节点三种情况现在要删除的键在叶子节点里。分三种情况情况 A叶子是 3 节点。直接删掉其中一个键它变成 2 节点树依然平衡。万事大吉。情况 B叶子是 2 节点但它的父节点是 3 节点或者父节点是 2 节点但兄弟节点够胖。此时可以从父节点或兄弟那里借一个键过来重新分配保证自身不空。这就是所谓的借位borrow。情况 C叶子是 2 节点父节点也是 2 节点兄弟节点也是 2 节点谁都借不出。这时候只能合并merge把父节点拉下来和当前空节点、兄弟节点合并成一个 3 节点。合并操作可能导致父节点变空于是下溢继续向上传播一路合并到根。这三类情况的划分是删除操作的骨架。我建议你一定要画图光靠文字记不住。5.3 借位操作的具体细节借位听起来简单做起来有个小坑不能破坏中序有序性。假设当前要删的叶子节点是左孩子它的兄弟是右孩子父节点是个 2 节点存键 a。删掉左孩子的键后左孩子空了。为了补上它我们从父节点拿键 a 下来放进左孩子。再从右兄弟里拿最小的键上移到父节点的位置。这里的搬运顺序是父节点键下移兄弟节点键上移。搬的时候要小心子树归属的重分配。这一步很像 AVL 旋转里的双旋转搬运本质上是把三个节点的数据重新均分。那能不能直接从兄弟节点搬一个键过来而不动父节点不行。因为那样兄弟节点可能就少于应有的键数了整个树的排序和平衡都会出问题。记住借位永远要经过父节点中转。5.4 合并操作与下溢传播当兄弟节点也是 2 节点没法借时只能合并。合并的本质是当前空节点 兄弟 2 节点 父节点里的一个键三者合成一个新的 3 节点。听起来是3 个节点变 1 个节点树的高度可能会局部减少。那父节点呢它交出了一个键之后自己可能变成空节点如果它原本是 2 节点于是它变成了新的下溢节点继续往上递归处理。这个下溢向上传播的过程和插入时的上溢向上传播是对称的。一个是往父节点塞键一个是向父节点要键。如果合并一路传到根根也变成空节点那就直接删除根让合并出来的新节点当根。这是唯一一种让树高度降低的情况同样不破坏完美平衡。5.5 一个删除的完整例子基于上面那棵插入了 10、20、30、40、50、60 的树我们来删 40。这棵树的结构是根 (20, 40)左孩子 10中孩子 30右孩子 (50, 60)。40 在根里是个内部键。找它的中序后继右子树 (50,60) 里最小的键是 50。用 50 替换 40。现在变成删除叶子节点 (50,60) 里的 50。但删掉 50 后叶子从 3 节点变成 2 节点只剩 60满足条件操作结束。最终树是根 (20, 50)左孩子 10中孩子 30右孩子 60。你看整个过程非常干净。如果删的是叶子里的唯一键比如删 10情况 B 或 C 就会触发借位/合并但套路还是那些。5.6 删除的代码思路删除比插入难在自顶向下和自底向上混合。有的教材比如 Sedgewick采用一种预调整策略在递归下行的过程中如果发现当前节点是 2 节点就提前从父节点或兄弟节点借位或合并保证当前节点至少有 2 个键。这样递归到叶子时叶子要么是 3 节点要么至少有 2 个键直接删起来格外顺利不需要回溯修复。这种贪心式下降比先删再回溯修复的写法更省心而且不容易出 bug。我第一次写实现时用的就是预调整策略调了几天没调通换了这种写法后一次通过。6. 2-3 树和红黑树、B 树的血缘关系学 2-3 树的时候很多人的困惑是我学了它有什么用平时工程里根本没见过这种树。其实你天天在用——只是它换了个马甲。6.1 红黑树2-3 树的一种编码方式红黑树是 2-3 树的一种二叉树编码。红黑树里每一个3 节点被拆成两个 2 节点并且用一条红色边把它们连起来。那些黑红黑红的规则本质上就是在表达这棵树是一棵2-3 树只是换成了二叉树的形态。具体对应关系是这样的2-3 树的 2 节点 → 红黑树的黑色节点。2-3 树的 3 节点 → 红黑树里一个黑色节点带一个红色子节点红色子在左边就是左倾红黑树在右边就是右倾红黑树。所以红黑树的每条路径黑色节点数相同对应 2-3 树的所有叶子在同一层红黑树的红色节点不能连续对应 3 节点的两个孩子里最多一个红色。当你把红黑树的红色节点压平到它父节点里就会得到一棵等价的 2-3 树。红黑树再复杂你只要从 2-3 树的视角去理解那些旋转和变色规则就都有了意义。6.2 2-3 树就是 3 阶 B 树更准确地说2-3 树是 B 树的一个特例B 树的阶数 m3 时就是 2-3 树。B 树的节点最多有 m 个孩子存 m-1 个键2-3 树最多 3 个孩子存 2 个键。所以 2-3 树的分裂上溢和借位合并在 B 树里完全一样只是每节点最多键数变成了更大的数。很多学 B 树的人会跳过 2-3 树直接背 B 树的插入删除步骤背得云里雾里。我的建议是先吃透 2-3 树再学 B 树因为 B 树的所有关键操作节点分裂、键上溢、兄弟借位、合并都能在 2-3 树这个小规模模型里看得清清楚楚。规模小了逻辑才不会被大量细节淹没。6.3 为什么工程里不用 2-3 树既然 2-3 树这么优雅为什么 Java 的 TreeMap、C 的 std::map 不直接用 2-3 树原因很实际2-3 树的 3 节点在内存里不规整。普通二叉树每个节点大小一致可以用统一的结构体表示。而 2-3 树的节点可能是 2 节点也可能是 3 节点要么浪费内存统一按 3 节点分配要么搞两个结构体代码复杂还不好缓存。红黑树用颜色标记把 3 节点拆成两个普通二叉树节点每个节点大小完全一致在内存布局、缓存友好性上明显更好。而 B 树则是磁盘/块设备场景下的王者一个节点正好填满一个磁盘页IO 次数少得可怜。所以 2-3 树在真实工程里很少直接出现它更多是作为一个教学模型存在——用最小的规模把平衡树的所有核心机制讲明白。这也是我写这篇文章的初衷。7. 手算题、代码实现与常见误区7.1 考研/面试里 2-3 树怎么考我在帮学弟学妹复习数据结构时发现2-3 树在考试里通常以三种形式出现按序列构造 2-3 树画出最终结构。这是最基础的题考的其实就是插入操作注意分裂顺序别搞错。删除若干键画出每步结果。难点在于处理 2 节点删除时的借位和合并尤其是合并后父节点也要继续处理的情况很容易画漏。概念性问题如 2-3 树的高度范围、与 B 树和红黑树的关系、为什么是完美平衡等。针对画图的题我推荐一个习惯每画一步都要检查所有叶子是否同一层。尤其删除之后如果发现某一层出现了断层那一定是哪一步合并没做对。面试里则更常问红黑树和 2-3 树的对应关系很少让你手写 2-3 树。所以下面给你一份参考思路如果遇到手写 2-3 树的高阶面试题不至于无从下手。7.2 一份极简的代码骨架下面的代码用 Python 简化实现 2-3 树的插入和查找重点展示分裂上溢的逻辑。删除因为篇幅关系不展开但骨架思路和插入是对称的。class Node: def __init__(self): self.keys [] # 有序存储长度 1 或 2 self.children [] # 长度 len(keys) 1 def is_leaf(self): return not self.children def is_full(self): return len(self.keys) 2 def find_key(node, key): 返回 (i, found)如果 foundTruekey 在 node.keys[i]否则 key 应插入在 children[i] 方向。 for i, k in enumerate(node.keys): if key k: return i, True if key k: return i, False return len(node.keys), False def insert(root, key): overflow, val _insert(root, key) if overflow: old_root root root Node() root.keys [val] root.children [old_root, Node()] # 实际需要把旧根分裂后的两个节点挂上 return root def _insert(node, key): 递归插入。返回 (是否有上溢, 上溢的键)。 i, found find_key(node, key) if found: return False, None if node.is_leaf(): node.keys.insert(i, key) if node.is_full(): # 分裂成两个节点返回中间键 mid node.keys[1] left Node() left.keys [node.keys[0]] right Node() right.keys [node.keys[2]] return True, (mid, left, right) return False, None # 内部节点递归到子节点 overflow, payload _insert(node.children[i], key) if not overflow: return False, None mid, left, right payload # 用 left、mid、right 去替换 children[i] node.children[i] left node.children.insert(i 1, right) node.keys.insert(i, mid) if node.is_full(): # 继续分裂向上 mid2 node.keys[1] left2 Node() left2.keys [node.keys[0]] left2.children node.children[:2] right2 Node() right2.keys [node.keys[2]] right2.children node.children[2:] return True, (mid2, left2, right2) return False, None这段代码做了一些简化比如根节点分裂时的细节处理不完全但核心的上溢返回结构是对的。建议你自己跑一遍把每一步的节点状态打出来对照我第 4 节手算的例子效果最好。7.3 我踩过的坑和一些小经验最后讲几条我学习 2-3 树时踩过的坑每条都是拿调试时间换来的。一是画图时容易把 3 节点的孩子方向画反。记住左边小、中间居中、右边大无论节点里有多少个键孩子的区间永远是按顺序排的。如果画完发现左子树里有一个大于该节点某个键的值那一定是孩子挂错了。二是分裂时谁上溢不能搞错。3 节点变成临时 4 节点后上溢的是中间那个键不是最大或最小键。被区间隔开的两个键分别形成独立的左右节点顺序不能颠倒。写代码时尤其要注意 keys 和 children 两个列表的同步更新一旦错位整棵树就废了。三是删除的预调整策略一定要熟练掌握。如果你先一路删到底再回溯修复代码会写得非常痛苦因为你需要区分当前空节点到底是因为删除导致还是本来就是个空节点。边下降边调整逻辑简单很多而且不容易出现空指针崩溃。四是千万不要试图用 AVL 树的旋转思路硬套 2-3 树。2-3 树没有旋转只有分裂、合并、借位。你如果习惯了旋转会很自然地想在 3 节点里做文章结果把简单问题搞复杂。把 2-3 树当成一套独立的操作体系反而更容易理解。学 2-3 树最奇妙的一点是它结构很简单——2 节点、3 节点、完美平衡这几个概念——却能生长出一套完整的插入删除机制。等你亲手画了好几棵 2-3 树的插入删除过程再回头去看红黑树和 B 树一定会有种豁然开朗的感觉。我当初就是这么被劝退又劝回来的希望你这趟旅程能走得比我顺。