中财网侯门妻不可欺免费下载:数据结构十一：2-3-4树（O(logn)）
来源：百度文库 编辑：中财网 时间：2024/04/30 01:16:40
2-3-4 树在计算机科学中是阶为 4 的B树。
大体上同B树一样，2-3-4 树是可以用做字典的一种自平衡数据结构。它可以在O（log n）时间内查找、插入和删除，这里的 n 是树中元素的数目。
2-3-4 树在多数编程语言中实现起来相对困难，因为在树上的操作涉及大量的特殊情况。红黑树实现起来更简单一些，所以可以用它来替代。
[编辑] 背景
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 树上的插入和删除操作也等价于在红黑树中的颜色翻转和旋转。这使得它成为理解红黑树背后的逻辑的重要工具。