2-3-4树

维基百科,自由的百科全书
跳转至: 导航搜索

2-3-4 树计算机科学中是阶为 4 的B树

大体上同B树一样,2-3-4 树是可以用做字典的一种自平衡数据结构。它可以在O(log n)时间内查找、插入和删除,这里的 n 是树中元素的数目。

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

2-3-4 tree example.png

背景[编辑]

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 树上的插入和删除操作也等价于在红黑树中的颜色翻转和旋转。这使得它成为理解红黑树背后的逻辑的重要工具。