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

Question

中使用 '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'在Tree terms中定义为：

Degree – number of sub trees of a node.

那么，它们是同一回事吗？我感觉不出任何区别。

Answer 1

A B-tree 是一种特定类型的树，除其他外，每个节点的最大数量为 children。 B-tree 的 order 是最大值。例如，二叉搜索树的阶数为 2。

一个节点的度数就是它拥有的children个数。所以B-tree的每个节点的度都大于或等于零且小于或等于B-tree.

的阶

一棵树没有 "degree," 除了它的节点有度。所以一棵树有一个最大度和一个最小度，指的是它的节点的最大度和最小度。

类似问题here。

希望对您有所帮助！

Answer 2

Degree 表示 B 树中一个节点可以拥有的 children 个数的下限（根节点除外）。即可能的最小数量 children。而 Order 代表 children 数量的上限。 IE。可能的最大数量。

B 树属性关于顺序

NOTE: Wikipedia also states these

关于度数的 B 树属性

B Tree Properties with respect to Degree

NOTE: These can also be found in the CLRS book

Answer 3

a B-tree 有两个流行的定义，其中：

Knuth Order (Order) 被Knuth定义
CLRS Degree (Degree) 在Cormen et al中的定义中使用算法简介 (CLRS)

Knuth 阶 和 CLRS 度 测量：min <= children <= max，最小值和最大值children，（min，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 阶数 k 是计算 children 的最大数量的索引。 k 的 Knuth 阶意味着每个节点必须有一个 max = k，和一个 min = ceil(k/2)。例如，(3,6) 是 Knuth 6 阶的 B-tree。
CLRS度t是统计children的最小个数的指标。 t 的 CLRS 度意味着每个节点必须有一个 min = t 和 max = 2t。例如，(3,6) 是 CLRS 度数 3
在这两个定义中，都是 min = ceil(max / 2) 和 max = 2 * min.
在这两种定义中，键的数量等于children减去一个的情况。所以 Knuth order 和 CLRS degree 在技术上也在计算最小和最大 keys – 以及同时计算最小和最大 children.
Knuth 的定义允许树 (min,max)，其中 max an 是奇数，但 CLRS 的定义忽略了它们。根据 CLRS 的定义，(t, 2t-1) 形式的任何树都是无效的。例如，具有 (min,max) = (5,9) 的树根据 Knuth 的定义是有效的，但根据 CLRS 的定义是无效的。

有趣的旁白：

两个定义都包含 2-3-4 trees, which are trees with (min, max) = (2,4). It is a B-tree with Knuth order k = 4 and it's a CLRS B-tree with degree t = 2. These trees are closely related to Red-Black Trees.
只有 Knuth 的定义包括 2-3 trees, where (min, max) = (2,3). A 2-3 tree is a Knuth B-tree with Knuth order k = 3. It is not a valid CLRS B-tree. It's a shame that CLRS don't include this tree because they are closely related to AA trees.

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

What is the difference btw "Order" and "Degree" in terms of Tree data structure

tree

terminology

data-structures