在 CLRS 算法简介中:B-Tree definition给定属性指出:
5.There are lower and upper bounds on the number of keys a node can contain. These bounds can be expressed in terms of a fixed integer t >= 2 called the minimum degree of the B-tree:
a. Every node other than the root must have at least t - 1 keys. Every internal node other than the root thus has at least t children. If the tree is nonempty, the root must have at least one key.
b. Every node can contain at most 2t - 1 keys. Therefore, an internal node can have at most 2t children. We say that a node is full if it contains exactly 2t - 1 keys.
上面是这么说的
t
是最小度数。
我的问题是t在计数什么，子节点指针还是键的数量。以及属性 5.b 如何保持这一点。
我浏览了维基百科对B-Tree、2-Tree和2-3-4 Tree的定义，结果发现没有给出了树阶的具体定义(根据Knuth阶数等于节点的子指针的最大数量)。
最佳答案
您似乎对 Knuth 阶数和 CLRS 阶数之间的差异感到有点困惑，所以请允许我解释一下。 Knuth 阶 和 CLRS 度 度量:min <= Children <= max，最小和最大子节点，(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 是计算子代最大数量的索引。 k 的 Knuth 阶意味着每个节点必须具有 max = k 和 min = ceil(k/2)。例如，(3,6) 是 Knuth 6 阶 B 树。
- CLRS 度 t 是计算最小 child 数量的指数。 CLRS 度数 t 意味着每个节点必须具有 min = t 和 max = 2t。例如，(3,6) 是 CLRS 度为 3 的 B 树
- 在这两个定义中，情况都是 min = ceil(max/2) 和 max = 2 * min。
在这两个定义中，键的数量都等于子元素的数量减一。因此，从技术上讲，Knuth 阶和 CLRS 度都在计算最小和最大键，并同时计算最小和最大子。
Knuth 的定义允许树 (min,max)，其中 max an 是奇数，但 CLRS 的定义忽略它们。根据 CLRS 的定义，任何 (t, 2t-1) 形式的树都是无效的。例如，(min,max) = (5,9) 的树根据 Knuth 的定义是有效的，但根据 CLRS 的定义是无效的。
有趣的旁白:
- 两个定义都包括2-3-4 trees ，它们是 (min, max) = (2,4) 的树。它是 Knuth 阶 k = 4 的 B 树，也是度 t = 2 的 CLRS B 树。这些树与 Red-Black Trees 密切相关。 .
- 只有 Knuth 的定义包括 2-3 trees ，其中(最小值，最大值)=(2,3)。 2-3 树是 Knuth 阶 k = 3 的 Knuth B 树。它不是有效的 CLRS B 树。遗憾的是 CLRS 不包含这棵树，因为它们与 AA trees 密切相关。 .
关于algorithm - CLRS B-Tree 属性节点可以包含的键数的下限和上限，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/45809726/