9

我对2-3-4 树如何在操作后保持高度平衡属性操作有一个基本的了解，以确保即使是最坏情况下的操作也是 O(n logn)。

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

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

4

3 回答 3

17

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

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

因此，红黑树因其易于实现以及内存/CPU 效率而受到关注。（AVL 树也很好。它们产生更平衡的树，而且简单地编写代码很愚蠢，但由于过于频繁地工作而只维护稍微紧凑的树，它们往往效率较低。）

哦，还有 2-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-12T01:28:32.730 回答
1

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

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

于 2012-01-06T23:00:19.920 回答
1

在我的算法课程中，他们告诉我们，它们通常用于从硬盘访问内存——称为 B/B+ 树。您制作存储可用内存大小的树，这样做可以最大限度地减少磁盘操作中的簧片数量（如果您使用存储例如 10^8 个元素的节点制作 B，则您只需要来自磁盘操作的 log_10^8(n) 簧片到在硬盘上找到什么都没有的东西。所以你称之为 2-3-4-5-... 树的东西实际上是广泛的解决方案。

于 2020-12-20T05:08:29.337 回答