2-3-4树

2–3–4树
类型	树
用大O符号表示的时间复杂度
算法 平均 最差 空间 $O(n)$ $O(n)$ 搜索 $O(\log n)$ $O(\log n)$ 插入 $O(\log n)$ $O(\log n)$ 删除 $O(\log n)$ $O(\log n)$

2-3-4树（英语：2–3–4 tree）在计算机科学中是阶为4的B树。

大体同B树，2-3-4树是一种自平衡数据结构，可用于实作字典。它可以在${\text{O}}(\log n)$时间内查找、插入和删除，这里的n是树中元素的数目。

2-3-4树在多数编程语言中实现起来相对困难，因为在树上的操作涉及大量特殊情况。红黑树实现起来更简单一些，所以可以用它来替代。

背景

2-3-4树把数据存储在叫做元素的单独单元中。它们组合成节点，每个节点都是下列之一

• 2-节点，就是说，它包含1个元素和2个子节点，
• 3-节点，就是说，它包含2个元素和3个子节点，
• 4-节点，就是说，它包含3个元素和4个子节点。

2-节点

3-节点

4-节点

每个子节点（可能为空）都是一个子2-3-4树。根节点是其中没有父亲的那个节点；它在遍历树的时候充当起点，因为从它可以到达所有的其他节点。叶子节点是有至少一个空子节点的节点。

同B树一样，2-3-4树是有序的：每个元素必须大于或等于它左边的和它的左子树中的任何其他元素。每个子节点因此成为了由它的左和右元素界定的一个区间。

2-3-4树是红黑树的一种等同，这意味着它们是等价的数据结构。换句话说，对于每个2-3-4树，都存在着至少一个数据元素是相同次序的红黑树。在2-3-4树上的插入和删除操作也等价于在红黑树中的颜色翻转和旋转。这使得它成为理解红黑树背后的逻辑的重要工具。