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

Question

我基本了解2-3-4树如何在每次操作后维护高度平衡特性，以确保即使是最坏情况下的操作时间也为O(n logn)。

但我不理解为什么只有2-3-4树？

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

- Lazer

---

如果你曾经实现过2-3-4树或红黑树，你就会知道这并不是一件很容易做对并测试的事情。甚至有一个简化版本的红黑树，即AA树，它比红黑树不太对称，但似乎是一个具有较低实现复杂度的良好替代品。当你需要更多的子节点或更扁平的树时，你可以选择B树，并以统一的方式明确支持许多子节点。 - Alexey Frunze

此外，还存在数据本地性和每个节点的开销（由于分配器成本）的担忧。这些问题往往鼓励实践中基于数组（例如哈希表）的解决方案。 - Donal Fellows

Answer 1

2-3-4树的实现通常需要多个类（2NODE，3NODE，4NODE），或者只使用一个NODE，该节点具有一组项目。如果使用多个类，则浪费大量时间构造和销毁节点实例，并且重新父级化它们很麻烦。如果使用单个类并使用数组来保存项目和子节点，那么您要么不断调整数组大小，这同样是浪费的，要么会浪费超过一半的内存空间用于未使用的数组元素。与红黑树相比，这不是很有效率。

红黑树仅具有一种节点结构。由于红黑树与2-3-4树具有二元性，因此RB树可以使用与2-3-4树完全相同的算法（无需像Cormen、Leiserson和Rivest描述的愚蠢混乱/复杂的实现，导致AA树不比2-3-4算法简单）。

因此，使用红黑树易于实现，而且内存/CPU效率高。 （AVL树也不错。它们产生更加平衡的树，很容易编写，但是由于过于频繁地维护仅略微更紧凑的树而变得不太有效率。）

哦，而且不会使用2-3-4-5-6等树，因为没有任何收获。 与2-3树相比，2-3-4的净增益是因为它们可以轻松地完成而无需递归（递归往往效率较低，特别是当它不能被编码为尾递归时）。但是，B树和B+树基本上是2-3-4-5-6-7-8-9等树，其中选择节点的最大大小n，以便在单个磁盘扇区中可以存储n个记录。（即每个磁盘扇区都是树中的一个节点，扇区的大小等于节点中存储的项目数。）这是因为在内存中线性搜索512条记录的时间仍然比遍历树中的下一级所需的磁盘搜索/提取快得多。O（512）仍然是O（1），因此对于树维护O（lg n）。

- Jeff Wiegley

Answer 2

在我的算法课程中，他们告诉我们常用于从硬盘访问内存的是B/B+树。您可以创建一个存储可用RAM大小的树，通过这样做，您可以最小化从磁盘操作读取的次数（如果您使用存储例如10^8个元素的节点的B树，则只需要log_10^8(n)次从磁盘操作中读取即可找到硬盘上的某些内容，这并不算多）。因此，您所称的2-3-4-5-...树实际上是一种广泛使用的解决方案。

- Lemmore

Answer 3

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

但显然，这种类型的树有一个概括：(a,b)树。

- cha0site

---

有趣！这意味着我们不能有3-4树，但我不确定为什么？ - Lazer

我也不确定。这似乎是一棵相当理论化的树，通常不会被探索...网络上关于(a,b)树的资料并不多。 - cha0site