B树与2-3-4树之间的差异 [英] Difference between B-Trees and 2-3-4 Trees

问题描述

B树与2-3-4树有什么区别？
还可以找到每个的最大和最小高度？
感谢

解决方案

...链接到维基百科 和引用：

2-3-4树是订单4的B树。

2-3-4 是一个 B树。

它被称为2-3-4树，因为非叶，非根节点的子数为2,3或4.

如果是6，它可能被称为3-4-5-6树，或3-6棵树。

由于最小数量的孩子是最大数量的一半，可以通常跳过前者，谈论一个B树订单 m 。

B树的顺序定义为节点可以拥有的最大子节点数。

在2-3 -4树，正如我们看到的，最大值是4.

这是最差的，最好的情况是由 B树的通用公式。

最佳情况：log _m n。 （所有节点都已满）

最差情况：log _{m / 2} n。 （所有节点都是半空）

其中

• / em>是树的顺序 - 节点可以拥有的最大子节点数，在这种情况下为4，而


• n 是树中的条目

B树可以有任何数字的顺序 - 是的，但是B树的一个特定子类，你提前修复这个数字。就像谈论蝴蝶一般而不是谈论君主蝴蝶。 B树是一类数据结构，就像蝴蝶是一类昆虫一样。 君主蝴蝶是蝴蝶的一个子类，就像2-3-4树是B的一个子类trees。

What is the difference between B-Trees and 2-3-4 Trees? Also how would you find the maximum and minimum height of each? Thanks

解决方案

...a link to Wikipedia and a quote:

"2-3-4 trees are B-trees of order 4."

A 2-3-4 is a B-tree.
It is called 2-3-4 tree because the number of children for a non-leaf, non-root node is 2,3 or 4.
Had it been 6, it could have been called a 3-4-5-6 tree, or 3-6 tree for short.
Since the minimum number of children is half of the maximum, one can just usually skip the former and talk about a B-tree of order m.
The order of a B-tree is defined as the maximum number of children a node can have.
In a 2-3-4 tree, as we have seen, the maximum is 4.

It's worst and best-case height is given by the general formula for B-trees.
Best case: log_mn. (all nodes are full)
Worst case: log_m/2n. (all nodes are half-empty)
Where

• m is the order of the tree - the maximum number of children a node can have, in this case, 4 - and
• n is the number of entries in the tree

"B tree can have an order of any number " - yes, but for a particular subclass of B-trees, you fix that number in advance. It's like talking about butterflies in general vs talking about the Monarch butterfly. B-trees are a class of data structures, just like butterflies are a class of insects. Monarch butterflies are a subclass of butterflies, just like 2-3-4 trees are a subclass of B-trees.

这篇关于B树与2-3-4树之间的差异的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！