为什么我们不使用 2-3 或 2-3-4-5 树？
我对 2-3-4 棵树如何保持高度平衡有基本的了解一次又一次的属性操作，以确保即使是最坏情况的操作也是 O(n logn)。
但我不太明白为什么只有2-3-4？
为什么不是 2-3 或 2-3-4-5 等？
I have a basic understanding of how 2-3-4 trees maintain the height balance property operation after operation to make sure even the worst case operations are O(n logn).
But I do not understand it well enough to know why only 2-3-4?
Why not 2-3 or 2-3-4-5 etc?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
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-4 比 2-3 棵树有净增益，因为它们可以轻松地在没有递归的情况下完成（递归往往效率较低，特别是当它不能以尾递归方式编码时）。然而，B 树和 Bplus 树几乎都是 2-3-4-5-6-7-8-9 等树，其中选择节点的最大大小 n，以便可以将 n 条记录存储在单个磁盘扇区。 （即每个磁盘扇区都是树中的一个节点，扇区的大小等于节点中存储的项目数。）这是因为在内存中线性搜索 512 条记录的时间仍然比向下遍历要快得多树中需要另一个磁盘查找/获取的级别。并且 O(512) 仍然是 O(1)，因此保持树的 O(lg n) 。
Implementation of 2-3-4 trees typically requires either multiple classes (2NODE, 3NODE, 4NODE) or you have just NODE that has an array of items. In the case of multiple classes you waste lots of time constructing and destructing node instances and reparenting them is cumbersome. If you use a single class with arrays to hold items and children then you are either resizing arrays constantly which is similarly wasteful or you wind up wasting over half your memory on unused array elements. It's just not very efficient compared to Red-Black trees.
Red-Black trees have only one type of node structure. Since Red-Black trees have a duality with 2-3-4 trees, RB trees can use the exact same algorithms as 2-3-4 trees (no need for the stupidly confusing/complex implementations described in Cormen, Leiserson and Rivest that led to AA trees which are not less complex than the 2-3-4 algorithm.)
So, Red-Black trees for their ease of implementation plus their memory/CPU efficiency. (AVL trees are nice too. They produce more well balanced trees and are stupid simply to code but they tend to be less efficient due to working too often to maintain only a slightly more compact tree.)
Oh, and 2-3-4-5-6... etc aren't done because nothing is gained. 2-3-4 has a net-gain over 2-3 trees because they can be done without recursion easily (recursion tends to be less efficient, especially when it cannot be coded tail-recursively). However, B-Trees and Bplus-Trees are pretty much 2-3-4-5-6-7-8-9-etc trees where the max size of the nodes, n, is chosen so that n records can be stored in a single disk sector. (i.e. each disk sector is a node in the tree and the size of the sector is equivalent to the number of items stored in the node.) This is because the time to search through 512 records linearly in memory is still MUCH faster than traversing down a level in the tree which requires another disk seek/fetch. and O(512) is still O(1) and thus maintains O(lg n) for the tree.
说实话，我不知道2-3-4树。在我的数据结构课上，我们学习了 2-3 棵树，说实话，我们大多数人都在练习的湿部分实现了 AVL 树。
但显然，这种类型的树有一个概括：
(a,b) 树。
To be honest, I wasn't aware of 2-3-4 trees. At my Data Structures class, we were taught 2-3 trees, and to be honest, most of us implemented AVL trees for the wet part of the exercise.
But apparently, there's a generalization of this type of tree:
(a,b) tree.
在我的算法课程中，他们告诉我们它们通常用于从硬盘访问内存 - 称为 B/B+ 树。您制作存储可用内存大小的树，通过这样做，您可以最小化光盘操作中的簧片数量（如果您使用存储例如 10^8 元素的节点制作 B，则您只需要 log_10^8(n) 光盘操作中的簧片即可在硬盘上找到一些没什么的东西，所以你称之为 2-3-4-5-... 树的东西实际上是广泛的解决方案。
At my algoritm course they told us that they are commonly used for acessing memory from hard disc - known as B/B+ trees. You make tree that store sizeof your avabile ram and by doing so you minimalize number of reed from disc operation (if you made B with node that store for example 10^8 elements you only need log_10^8(n) reed from disc operation to find something on hard disc which is nothing. So something that you called 2-3-4-5-... trees is in fact widespread solution.