Mas*_*sse 5 tree b-tree data-structures
我正在读考试,然后来到B树上.维基百科将B树描述为树,其中节点具有至少d且最多2d的密钥,因此最多2d + 1叶.例如,如果d = 1,它将有最多2个键和3个子项,使其成为2-3树.然而,除非我弄错,否则这不允许例如2-3-4树.
然而,我们的材料将b树描述为树,其中每个节点至少具有t> = 2 t-1个密钥和至多2t-1个密钥.这意味着节点具有奇数个键和偶数个子节点.例如,t = 2将具有1到3个键,最多4个子项,使其成为2-3-4树.另一方面,这种符号不可能有2-3棵树.
除此之外,Knuth还有一个符号,其中d表示节点中的最大子节点数.这种表示法允许偶数和奇数的孩子,允许2-3棵树和2-3-4棵树.
我知道2-3棵树和2-3-4棵树都存在.
什么是真正的符号？有真正的符号吗？作为一个额外的问题; 什么是大小为h的树中的最大键数？
如果您仔细阅读 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:
分裂。当我们添加一个新元素并且一个节点的键数超过最大数量时会发生2t
因此我们有2t+1键，我们将节点拆分为两个节点，并将一个元素推送到父节点，将2t键留在两个子节点中，并将t键留在每个节点中孩子。这是可以接受的，因为节点中键的最小数量确实是t。
合并。当我们删除一个键并且一个节点包含的数量小于最小数量 时t，就会发生这种情况，并且它的兄弟节点也是最小的。因此，我们在新的合并节点中有t-1 + t键，生成的节点必须有效：t-1 + t = 2t-1 <= 2t。伟大的。
t->也是如此2t+1：
分裂。
2t+2变成t，t+1这没关系。
合并。
t-1 + t = 2t-1 <= 2t+1
当然，运行时间没有区别，只是轻微的实现差异，理论上的重要性很小（您可以使用第一个变体稍微优化一些算法，但不会太多，以至于会改变运行时复杂性）。