插入Btree与父母指针

Question

我尝试在Java中为Btree编写插入代码，但是无法正确地拆分节点，任何人都可以指导我在Btree中插入，拆分和非完整插入的良好算法吗？

谢谢

Answer 1

假设每个节点：

• D的最大子女数，
• 最大键数是K = D-1，
• 最低儿童人数为d = D / 2，
• 最小键数是k = D / 2-1

这是算法：

• 插入：搜索树以查找包含密钥的叶节点。插入密钥。查看密钥是否已超过（密钥数量高于D-1），否则操作已完成。如果过度飞行，则将节点拆分为2个节点（本身和新节点），将最后一个（k）键移动到新节点，使节点（叶节点）保留k + 1个键。将叶节点中的最后一个键移动到父节点。如果父母过度飞行，请重复这些步骤。
• 删除：搜索树以查找包含要删除的密钥的节点。有2例是可能的。容器节点是叶节点，或者是内部非叶节点。如果它是内部节点，首先找到节点中密钥的直接前导，该节点始终来自引导节点。然后用这个前任密钥替换密钥。现在，您需要从叶节点中删除密钥。 （请注意，从内部节点删除总是减少为从叶节点删除）。如果是叶节点，请从叶节点中删除密钥。检查叶节点是否处于飞行状态（少于k个键），如果操作不完整则检查。如果在飞行中，则可能有3种情况。如果节点具有至少具有k + 1个键的左兄弟，则通过父级执行右旋转。否则，如果节点具有至少具有k + 1个键的右兄弟，则通过父进行左旋转。否则，如果节点没有任何具有至少k + 1个键的兄弟，则使用其中一个兄弟加入该节点，同时从父节点关闭一个键。然后检查父项是否在飞行中，如果在飞行中重复这些步骤以修复父项。
• 搜索：类似于二叉搜索树，主要区别在于现在您还需要在每个节点中执行搜索，因为每个节点都有已排序的键，您可以对每个节点执行二进制搜索。