logo标签列表

B树和2-3-4树的区别

data-structurestreetheoryb-tree
14

B-树和2-3-4树的区别是什么？

此外，您如何找到每个树的最大和最小高度？

我只能添加一个维基百科链接来帮助您了解 2-3-4 树：http://en.wikipedia.org/wiki/2-3-4_tree - Frank Heikens
不是作业或个人复习。 - zorgo
2个回答
26

这段文本包含了一个指向 维基百科 的链接和一句引用：

"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树的一般公式给出。

最好情况：logmn. (所有节点都是满的)
最坏情况：logm/2n. (所有节点都是一半空的)

其中，

  • m 是树的阶数——一个节点可以有的最大子节点数量，在这种情况下为4——而
  • n 是树中条目的数量。

"B树的阶数可以是任何数字" - 是的，但对于B树的一个特定子类，您需要事先固定该数字。这就像谈论蝴蝶一般与谈论帝王蝶一样。B树是一类数据结构，就像蝴蝶是昆虫一类。而帝王蝶则是蝴蝶的一个子类，正如2-3-4树是B树的一个子类。

-1

B树出现的主要原因是在插入时所需的节点分裂次数比2-4树少。在2-4树中，有时会出现级联分裂的情况，但在B树中不存在级联分裂。

B树中可以进行级联分裂：http://en.wikipedia.org/wiki/B_Tree#Insertion - jrouquie
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接