data-structures - b树的顺序

Question

我正在为考试而学习，并且遇到了 B 树。维基百科将 B 树描述为一棵树，其中节点具有至少 d 和至多 2d 个键，因此最多具有 2d+1 个叶子。例如，如果 d=1，则最多有 2 个键和 3 个子节点，从而使其成为 2-3 棵树。但是，除非我弄错了，否则这不允许例如 2-3-4 树。

然而，我们的 Material 将 b 树描述为一棵树，其中每个节点至少有 t>=2 t-1 个键，最多有 2t-1 个键。这意味着节点具有奇数个键和偶数个子节点。例如 t=2 将有 1 到 3 个键，最多 4 个 child ，使其成为 2-3-4 树。另一方面，不可能有带有这种符号的 2-3 树。

最重要的是，Knuth 有一个表示法，其中 d 表示节点中子节点的最大数量。这种表示法允许偶数和奇数的 child ，允许 2-3 棵树和 2-3-4 棵树。

我知道 2-3 棵树和 2-3-4 棵树都存在。

什么是真正的符号？有真正的记号吗？作为一个额外的问题；大小为 h 的树中的最大键数是多少？

Answer 1

如果您更仔细地阅读维基文章，您会发现 B 树有两种主要变体(不包括 B* 和 B+ 等结构变体)，一种是 t -> 2t键，其中一个带有 t -> 2t+1键。

将这些变体翻译成#children 我们有一个 t+1 -> 2t+1 children ，还有一个 t+1 -> 2t+2 children 。

所以基本上回答你的问题，2-3 和 2-3-4 树都是有效的树，每个树都根据不同的变体/定义:

2-3 是第一类( t+1 -> 2t+1 child ，其中 t=1)

2-3-4 是第二类( t+1 -> 2t+2 child ，其中 t=1)

这两种变体的有效性源于这样一个事实，即拆分和合并(从/向 ADT 删除和插入的操作)都是有效的:
t -> 2t :

split 。
当我们添加一个新元素并且节点的键数超过最大数量时发生 2t所以我们有 2t+1键，我们将节点拆分为两个节点，并将一个元素推送到父节点，留下 2t两个 child 的 key ，以及 t每个 child 的 key 。这是可以接受的，因为节点中的最小键数确实是 t .

合并。
当我们删除一个键并且一个节点包含小于最小数量时发生，t ，它的兄弟也是最小的。所以我们有 t-1 + t新合并节点中的键，结果节点必须有效:t-1 + t = 2t-1 <= 2t .伟大的。
t也是如此-> 2t+1 :

split 。2t+2变成 t和 t+1没关系。

合并。t-1 + t = 2t-1 <= 2t+1
当然，运行时间没有区别，只是理论上重要性很小的轻微实现差异(您可以使用第一个变体稍微优化一些算法，但不会改变运行时复杂性)。