为什么我们不使用2-3或2-3-4-5树？

我对2-3-4 trees在操作之后如何保持高度平衡属性操作有一个基本的了解，以确保即使最坏的情况操作都是O（n logn）。为什么我们不使用2-3或2-3-4-5树？

但我不明白为什么只有2-3-4？

为什么不是2-3或2-3-4-5等？

2012-01-06 Lazer

如果你曾经实施2-3-4或红黑树，你会知道做正确然后测试并不是很微不足道。甚至还有红黑树的简化版本，即[AA树]（http://en.wikipedia.org/wiki/AA_tree），它与红黑树不太对称，但似乎是它是一个很好的替代方案，具有较低的实现复杂性当您需要更多的子节点或更平坦的树时，您可以使用b树并以统一的方式明确支持许多子节点。 – 2012-01-07 00:08:11

另外，总是有数据局部性和每个节点开销（由于分配器成本）的担忧。在实践中，这些问题倾向于鼓励基于数组的解决方案（例如哈希表）。 – 2012-03-05 08:58:29

说实话，我并不知道2-3-4树。在我的数据结构课上，我们学习了2-3棵树，说实话，我们大多数人在练习的湿部分实现了AVL树。

但显然，这种类型的树的泛化： (a,b) tree。

来源

2012-01-06 23:00:19 cha0site

有趣！这意味着我们不能有3-4棵树，我不知道为什么？ – Lazer 2012-01-06 23:05:09

我也不确定。这似乎是一个相当理论的树，而不是通常探索的树......网上的树（a，b）没有太多。 – cha0site 2012-01-06 23:15:03

矢量树，很好。 :-) – 2012-01-13 17:58:24

2-3-4树的实现通常需要多个类（2NODE，3NODE，4NODE），或者您只有NODE具有一组项目。在多个类的情况下，您浪费大量时间来构造和破坏节点实例，并重新设置它们非常麻烦。如果你使用一个包含数组的类来保存项目和子项，那么你要么不断调整数组的大小，这同样是浪费，要么就是浪费了一半以上的内存，浪费在未使用的数组元素上。与红黑树相比，它效率不高。

红黑树只有一种节点结构。由于红黑树具有2-3-4树的对偶性，所以RB树可以使用与2-3-4树完全相同的算法（不需要Cormen，Leiserson和Rivest中描述的那些愚蠢混乱/复杂的实现）到AA树并不比2-3-4算法复杂）。

所以，红黑树的实现方便以及它们的内存/ CPU效率。（AVL树也很好，它们生成更加平衡的树并且仅仅为了编码而变得愚蠢，但由于经常工作以维持仅稍微更紧凑的树而往往效率较低）。

哦， 3-4-5-6 ......等都没有完成，因为没有获得任何东西。 2-3-4的净增益超过2-3棵树，因为它们可以很容易地完成而不会递归（递归往往效率较低，特别是当它不能以尾递归方式编码时）。然而，B-Trees和Bplus-Trees几乎都是2-3-4-5-6-7-8-9-等树，其中节点的最大尺寸n被选择为使得n个记录可以被存储在单个磁盘扇区。（即每个磁盘扇区是树中的一个节点，扇区的大小等于存储在节点中的项的数量）。这是因为在内存中线性搜索512条记录的时间比遍历速度快得多树中需要另一个磁盘寻找/获取的级别。并且O（512）仍然是O（1），因此为该树维护O（lg n）。

来源

2012-06-12 01:28:32

为什么我们不使用2-3或2-3-4-5树？

回答

相关问题