查看“︁2-3-4树”︁的源代码

{{unreferenced|time=2015-03-07T02:59:20+00:00}}
{{Infobox data structure
|name=2–3–4树
|type=[[樹 (資料結構)|樹]]
|space_avg=<math>O(n)</math>
|space_worst=<math>O(n)</math>
|search_avg=<math>O(\log n)</math>
|search_worst=<math>O(\log n)</math>
|insert_avg=<math>O(\log n)</math>
|insert_worst=<math>O(\log n)</math>
|delete_avg=<math>O(\log n)</math>
|delete_worst=<math>O(\log n)</math>
}}
'''2-3-4树'''（{{lang-en|2–3–4 tree}}）在[[计算机科学]]中是阶为4的[[B树]]。

大体同[[B树]]，2-3-4树是一种自平衡[[数据结构]]，可用於實作[[字典 (資料結構)|字典]]。它可以在<math>\text{O}(\log n)</math>时间内查找、插入和删除，这里的''n''是树中元素的数目。

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

[[File:2-3-4 tree example.png|center]]

== 背景 ==

2-3-4树把数据存储在叫做''元素''的单独单元中。它们组合成''节点''，每个节点都是下列之一
* 2-节点，就是说，它包含1个元素和2个子節點，
* 3-节点，就是说，它包含2个元素和3个子節點，
* 4-节点，就是说，它包含3个元素和4個子節點。

[[File:2-3-4 tree 2-node.png|frame|left|2-节点]]
[[File:2-3-4-tree 3-node.png|frame|left|3-节点]]
[[File:2-3-4 tree 4-node.png|frame|left|4-节点]]
{{clear}}

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

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

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

[[Category:B树]]