在树数据结构方面,btw"Order"和"Degree"有什么区别

Question

B-Tree定义 他们使用'order'术语:

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

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

该度一个的节点是有孩子的数量。因此，B-tree 的每个节点的度数都大于或等于 0 且小于或等于 B-tree 的阶数。

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

类似的问题在这里。

我希望这有帮助！

Answer 2

Degree表示B树中节点可以拥有的子节点数的下限(根除).即可能的最小孩子数.而Order代表儿童数量的上限.即.可能的最大数量.

B关于订单的树属性

NOTE:维基百科也说明了这些

关于学位的B树属性

关于度的B树属性

NOTE: These can also be found in the CLRS book

Answer 3

B 树有两种流行的定义，其中：

• Knuth的定义使用了Knuth Order ( Order )
• CLRS 度数（Degree）在Cormen 等人的Introduction to Algorithms (CLRS)中的定义中使用

两者Knuth的顺序和CLRS度度量：儿童<=最大最小<= ，最小和最大的孩子，（分钟，最大），树中的每个内部节点被允许具有。两个定义都同意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 阶 k 是计算最大子节点数的索引。k 的 Knuth 阶意味着每个节点必须有一个 max = k 和一个 min = ceil(k/2)。例如，(3,6) 是 Knuth 阶 6 的 B 树。
• CLRS 度数 t 是计算最小孩子数的指标。t 的 CLRS 度意味着每个节点必须具有 min = t 和 max = 2t。例如，(3,6) 是 CLRS 度 3 的 B 树
• 在这两个定义中，都是 min = ceil(max / 2) 和 max = 2 * min 的情况。

• 在这两个定义中，key 的数量等于 child 的数量减去 1。因此，Knuth 阶数和 CLRS 度数在技术上也在计算最小和最大键- 以及同时计算最小和最大子级。

• 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 树。这些树与Red-Black Trees。
• 只有 Knuth 的定义包括2-3 棵树，其中 (min, max) = (2,3)。2-3 树是 Knuth 阶 k = 3 的 Knuth B 树。它不是有效的 CLRS B 树。很遗憾 CLRS 没有包含这棵树，因为它们与AA 树密切相关。