2-3-4树

维基百科,自由的百科全书
跳到导航 跳到搜索

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

大体同B树,2-3-4树是一种自平衡数据结构,可用於實作字典。它可以在时间内查找、插入和删除,这里的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树上的插入和删除操作也等价于在红黑树中的颜色翻转和旋转。这使得它成为理解红黑树背后的逻辑的重要工具。