节点必须包含的最小键数是多少？

Question

我有两本数据结构书.在两本书中,有两种不同的B树插入方法:

假设我想将值k插入B树.在搜索适当的叶节点以插入值k之后,计算特定叶节点中存在的值.如果叶节点已满,则:

1.从叶子元素和新元素中选择单个中值.之后将节点分成两个节点.中间值转移到父节点.

2.在m/2-1(m为树的顺序)position.median值转移到父节点后,将节点分成两个节点.之后将值插入到适当的位置.

以下哪种方法是正确的？

另一个问题:

对于订单n的B树,节点必须包含的最小密钥数是多少？我已经搜索了互联网和书籍,但无法得到确切的等式,我可以找到最小的密钥数:e,g if order = 5然后任何节点(root除外)的最小键数为2.这是怎么回事？

任何答案将不胜感激!

Answer 1

根据Knuth的定义,m阶的B树是满足以下属性的树:

• 每个节点最多只有m个孩子.
• 每个非叶节点(根除外)至少有ceil(m/2)个子节点.
• 如果根不是叶节点,则根至少有两个子节点.
• 具有k个子节点的非叶节点包含k-1个密钥.
• 所有叶子都出现在同一级别,并携带信息.

每个内部节点的键用作分隔其子树的分隔值.例如,如果内部节点有3个子节点(或子树),那么它必须有2个键:a1和a2.最左边子树中的所有值都小于a1,中间子树中的所有值都在a1和a2之间,最右边子树中的所有值都将大于a2.

内部节点

内部节点是除叶节点和根节点之外的所有节点.它们通常表示为一组有序的元素和子指针.每个内部节点包含最多U个子节点和最少L个子节点.因此,元素的数量总是比子指针的数量少1(元素的数量在L-1和U-1之间).U必须是2L或2L-1; 因此每个内部节点至少半满.U和L之间的关系意味着可以连接两个半满节点以构成合法节点,并且可以将一个完整节点拆分为两个合法节点(如果有空间将一个元素推送到父节点).这些属性使得可以删除新值并将新值插入B树,并调整树以保留B树属性.

根节点

根节点的子节点数与内部节点具有相同的上限,但没有下限.例如,当整个树中的元素少于L-1时,根将是树中唯一的节点,根本没有子节点.

叶节点

叶节点对元素数量有相同的限制,但没有子节点,也没有子节点.

http://en.wikipedia.org/wiki/B-Tree

并补充说:

使用Knuths定义的5阶B树(最大子项数)[4将是最大键数].

拆分后内部节点的最小子节点数为3 [2个键].由于节点在溢出B树的顺序时分裂.

B-Tree列表11108,3267,11357,12080,6092

添加3267,11108,11357,12080; 这是显示键,而不是孩子.

??? 3267, 11108, 11357, 12080

然后加入6092; 这是显示键,而不是孩子.

拆分前(键数> order-1)[5> 5-1 = 4]:

??? 3267, 6092, 11108, 11357, 12080

拆分后:

??? 11108
    ??? 3267, 6092
    ??? 11357, 12080

注意:根节点没有最小数量的键/子节点作为其他节点.

正在删除:

删除后重新平衡

如果从叶节点删除元素使其低于最小大小,则必须重新分配一些元素以使所有节点达到最小值.在某些情况下,重新排列会将缺陷移动到父级,并且重新分配必须迭代地应用于树,甚至可能应用于根.由于最小元素数不适用于根,因此使根成为唯一的缺陷节点不是问题.重新平衡树的算法如下:[需要引证]

1. 如果右兄弟的元素数量超过最小数量

   • 将分隔符添加到缺陷节点的末尾
   • 将父分隔符替换为右兄弟的第一个元素
   • 将右兄弟的第一个子节点作为缺陷节点的最后一个子节点

2. 否则,如果左兄弟的元素数量超过最小数量

   • 将分隔符添加到缺陷节点的开头
   • 将父分隔符替换为左兄弟的最后一个元素
   • 插入左兄弟的最后一个子节点作为缺陷节点的第一个子节点

3. 如果两个直接兄弟姐妹只有最少数量的元素

   • 创建一个新节点,其中包含来自缺陷节点的所有元素,来自其中一个兄弟节点的所有元素,以及两个组合兄弟节点之间的父节点中的分隔符
   • 从父项中删除分隔符,并用组合节点替换它分隔的两个子项
   • 如果这会使父项中的元素数量达到最小值,则使用该缺陷节点重复这些步骤,除非它是根,因为允许根不足

要考虑的唯一其他情况是根没有元素和一个子元素.在这种情况下,用其唯一的孩子替换它就足够了.

预删除节点9062.

??? 6169, 12789
    ??? 1009, 4238, 5139
    ??? 6625, 9062
    ??? 12909, 14508, 14703, 14985

平衡之前

??? 6169, 12789
    ??? 1009, 4238, 5139
    ??? 6625 
    ??? 12909, 14508, 14703, 14985

平衡后

??? 6169, 12909
    ??? 1009, 4238, 5139
    ??? 6625, 12789
    ??? 14508, 14703, 14985

正如你所看到的,中间节点的孩子从它的父母那里借了12789来满足最低要求,而父母从它最右边的孩子那里借了12909来满足它的最低要求.