树数据结构中“阶”和“度”有什么区别

Question

B 树定义 他们使用“顺序”术语：

According to Knuth's definition, a B-tree of order m is a tree which satisfies the following properties:

1. Every node has at most m children.
...

并且“学位”在树术语中定义为：

Degree – number of sub trees of a node.

那么，它们是同一件事吗？我感觉不出有什么不同。

Answer 1

Degree

表示 B 树中节点可以拥有的子节点数量的下限（根除外）。即可能的最小儿童数量。而

Order

代表孩子数量的上限。 IE。可能的最大数量。

B 与订单相关的树属性

NOTE

：维基百科也说明了这些

B 树关于度的属性

B 树关于度的属性

NOTE

：

These can also be found in the CLRS book

Answer 2

B 树是一种特定类型的树，其中每个节点具有最大数量的子节点。 B 树的order 就是最大值。例如，二叉搜索树的阶数为 2。

节点的度是它拥有的子节点的数量。因此，B 树的每个节点的度都大于或等于 0 且小于或等于 B 树的阶。

树没有“度”，只是它的节点有度。所以一棵树有最大度和最小度，指的是它的节点的最大和最小度。

类似问题

这里。

希望有帮助！

Answer 3

B 树有两种流行的定义：

• Knuth Order（Order）是按 Knuth 的定义使用的
• CLRS Degree (Degree) 用于Cormen et al中Introduction to Algorithms (CLRS)中的定义

Knuth order 和CLRS Degree 度量：min ，最小和最大子节点，(<= children <= maxmin, max)，树中的每个内部节点都允许有。两个定义都同意 min 不能小于 max/2:

Knuth Order, k |  (min,max)  | CLRS Degree, t
---------------|-------------|---------------
     0         |      -      |        –
     1         |      –      |        –
     2         |      –      |        –
     3         |    (2,3)    |        –
     4         |    (2,4)    |      t = 2
     5         |    (3,5)    |        –
     6         |    (3,6)    |      t = 3
     7         |    (4,7)    |        –
     8         |    (4,8)    |      t = 4
     9         |    (5,9)    |        –
     10        |    (5,10)   |      t = 5

主要相似点/不同点：

Knuth order k 是计算“最大”子代数量的索引。 k 的 Knuth 阶意味着每个节点必须具有 max = k 和 min = ceil(k/2)。例如，(3,6) 是 Knuth 阶 6 的 B 树。
• CLRS 度 t 是计算“最小”儿童数量的指数。 CLRS 度数 t 意味着每个节点必须具有 min = t 和 max = 2t。例如，(3,6) 是 CLRS 度为 3 的 B 树
在这两个定义中，情况都是 min = ceil(max / 2) 和 max = 2 * min。
• 在这两个定义中，键的数量都等于子元素的数量
减一
• 。因此，从技术上讲，Knuth 阶和 CLRS 度也在计算最小和最大
keys
• – 以及同时计算最小和最大

  children。 Knuth 的定义允许树 (min,max)，其中 max an 是奇整数

  ，但 CLRS 的定义忽略它们。根据 CLRS 的定义，任何 (t, 2t-1) 形式的树都是无效的。例如，(min,max) = (5,9) 的树通过 Knuth 的定义是有效的，但通过 CLRS 的定义是无效的。

• 有趣的旁白：

这两个定义都包括

---

2-3-4 树

，即具有 (min, max) = (2,4) 的树。它是 Knuth 阶 k = 4 的 B 树，也是度 t = 2 的 CLRS B 树。这些树与

红黑树

密切相关。
• 仅 Knuth 的定义包括 2-3 棵树，其中 (min, max) = (2,3)。 2-3 树是 Knuth B 树，其 Knuth 阶 k = 3。它不是有效的 CLRS B 树。遗憾的是 CLRS 不包含这棵树，因为它们与AA 树
密切相关。
• 你好，大家好吗

Answer 4