insert - 插入 ab*-tree

Question

我无法理解如何将元素插入 ab*-tree，尤其是在涉及根节点时。

假设您有 9 阶的 ab*-tree，并且您要将以下项目插入树中，0、1、2、5、7、9、10 和 12 我认为您开始插入根然后当你插入 12 时它会被填满，所以它会溢出，因此它会导致根被分割并有一个包含 7 的根节点，一个包含 0、1、2、5 和右的左子节点包含 9、10 和 12 的孩子。我的想法是正确的还是有其他方法可以做到这一点。

PS：请注意我使用 b-tree 作为标签，因为我不能使用 b*-tree 任何帮助将不胜感激：）

Answer 1

(r+1)/2 r=8 9/2=4,5 截断它然后你有 4. 0,1,2,5 你的根必须是第 4 个元素。它意味着 5 并且留下了 0-1-2 right child 7-9-10-12.I'm not sure I have udnerstooth your question if you write your capacity order I may help you better