编辑“︁2-3-4树”︁（章节）

== 背景 ==

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树]]