我正在为考试而学习，并且来到了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个子代，从而使其成为2-3-4棵树。另一方面，不能使用这种表示法的2-3棵树。
最重要的是，用Knuth表示，其中d表示节点中最大子代数。该表示法将允许偶数和奇数个 child ，同时允许2-3棵树和2-3-4棵树。
我知道2-3棵树和2-3-4棵树都存在。
真正的符号是什么？有没有真正的记号？作为一个额外的问题；大小为h的树中最大 key 数是多少？
最佳答案
如果您更仔细地阅读Wiki文章，您会发现B树有两种主要变体(不包括B *和B +之类的结构变体)，一种具有t-> 2t键，一种具有t-> 2t+1键。
将这些变体翻译为#children，我们有一个带有t+1-> 2t+1子级的变量，另一个带有t+1-> 2t+2子级的变量。
因此，从本质上来说，要回答您的问题，2-3和2-3-4树都是有效树，每个树都根据不同的变体/定义:
2-3是第一类(t+1-> 2t+1子项，其中t = 1)
2-3-4是第二种类型(t+1-> 2t+2子项，其中t = 1)
这两种变体的有效性源于以下事实:拆分和合并(对从ADT删除和插入到ADT中的操作)都是有效的:t-> 2t:
split 。
当我们添加新元素并且节点的键数超过最大数目2t时发生
因此，我们有了2t+1键，将节点分为两个节点，并将一个元素推到父级，将2t键保留在两个子级中，将t键保留在每个子级中。这是可以接受的，因为节点中的最小键数确实是t。
合并。
当我们删除一个键并且一个节点包含的数量少于最小数量t时发生，它的 sibling 数量也最小。因此，我们在新的合并节点中有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
当然，运行时间没有差异，只是实现上的微小差异，理论上的重要性不大(您可以使用第一个变量对某些算法进行稍微优化，但不会太大，以至于会改变运行时的复杂性)。