问插入带有父指针的Btree

EN

假设每个节点：

• 的最大子项数为D，
• 的最大键数为D-1，
• 的最小子项数为d= D/2，
• 的最小键数为K= D/2-1

以下是算法：

• Insert：搜索树以查找包含键的叶节点。插入钥匙。查看密钥是否溢出(密钥数量大于D-1)，如果不是，则操作完成。如果超过飞行，将节点拆分为2个节点(本身和一个新节点)，将最后(k)个关键字移动到新节点，使节点(叶节点)保留k +1个关键字。将叶子节点中的最后一个关键字移动到父节点。如果parent已超载，请重复这些步骤。
• Delete：搜索树以查找包含要删除的键的节点。可能有2例。容器节点是叶节点，或者是内部非叶节点。如果是内部节点，则首先在节点中查找键的直接前置节点，该节点总是来自前导节点。然后用这个前置密钥替换该密钥。现在，您需要从叶子节点中删除键。(请注意，从内部节点删除总是减少到从叶节点删除)。如果是叶节点，则从叶节点中删除键。检查叶节点是否在流下(少于k个key)，如果不是，则操作完成。然而，如果在飞行中，可能有3个案例。如果节点具有至少具有k+1关键帧的左侧同级节点，则通过父节点执行右旋转。否则，如果节点具有至少具有k+1关键帧的右同级节点，则通过父节点执行左旋转。否则，如果该节点没有任何至少具有k+1键的同级节点，则将该节点与其一个同级节点连接起来，同时从父节点中取出一个键。然后检查父节点是否在运行中，如果在运行中重复这些步骤来修复parent.
• Search：类似于二进制搜索树，主要区别是现在您还需要在每个节点中执行搜索，由于每个节点都有排序的键，因此您可以在每个节点上执行二进制搜索。