2-3-4树 - 维基百科,自由的百科全书
此條目没有列出任何参考或来源。 (2015年3月7日) |
2–3–4树 | |||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
类型 | 樹 | ||||||||||||||||||||
用大O符号表示的时间复杂度 | |||||||||||||||||||||
|
2-3-4树(英語:2–3–4 tree)在计算机科学中是阶为4的B树。
大体同B树,2-3-4树是一种自平衡数据结构,可用於實作字典。它可以在时间内查找、插入和删除,这里的n是树中元素的数目。
2-3-4树在多数编程语言中实现起来相对困难,因为在树上的操作涉及大量特殊情况。红黑树实现起来更简单一些,所以可以用它来替代。
![](http://upload.wikimedia.org/wikipedia/commons/0/0a/2-3-4_tree_example.png)
背景
[编辑]2-3-4树把数据存储在叫做元素的单独单元中。它们组合成节点,每个节点都是下列之一
- 2-节点,就是说,它包含1个元素和2个子節點,
- 3-节点,就是说,它包含2个元素和3个子節點,
- 4-节点,就是说,它包含3个元素和4個子節點。
![](http://upload.wikimedia.org/wikipedia/commons/7/76/2-3-4_tree_2-node.png)
![](http://upload.wikimedia.org/wikipedia/commons/4/4e/2-3-4-tree_3-node.png)
![](http://upload.wikimedia.org/wikipedia/commons/f/f6/2-3-4_tree_4-node.png)
每个子節點(可能为空)都是一个子2-3-4树。根节点是其中没有父亲的那个节点;它在遍历树的时候充当起点,因为从它可以到达所有的其他节点。叶子节点是有至少一个空子節點的节点。
同B树一样,2-3-4树是有序的:每个元素必须大于或等于它左边的和它的左子树中的任何其他元素。每个子節點因此成为了由它的左和右元素界定的一个区间。
2-3-4树是紅黑樹的一种等同,这意味着它们是等价的数据结构。换句话说,对于每个2-3-4树,都存在着至少一个数据元素是相同次序的红黑树。在2-3-4树上的插入和删除操作也等价于在红黑树中的颜色翻转和旋转。这使得它成为理解红黑树背后的逻辑的重要工具。
|