我正在尝试实现一个B树，据我所知，这是如何拆分节点：
1.试图在叶节点N处插入新值V
1.如果叶节点没有空间，则创建一个新节点，并选取N的中间值，其右侧的任何内容移动到新节点，中间值左侧的任何内容留在旧节点中，但将其向左移动以释放右侧索引，并将V插入到现在两个节点中的适当节点中
1.将我们选择的中间值插入到N的父节点中，并将新创建的节点添加到N的父节点的子节点列表中（从而使N和新节点成为兄弟节点）
1.如果N的父节点没有可用空间，则执行相同的操作，并使用值在两个拆分节点之间拆分子节点（因此最后一部分仅适用于非叶节点）
1.继续尝试将上一个分割的中间点插入到父节点中，直到到达根节点，并可能分割根节点本身，生成新的根节点
这就引出了一个问题--我如何向上遍历，我应该保持父指针吗？
因为只有当我到达了要插入的叶子节点时，我才能知道是否需要拆分它，所以一旦要拆分它，我就必须回到它的父节点，如果我也要拆分父节点，我就必须继续往上。
否则，我将不得不重新遍历树一次又一次，每次找到下一个父。
下面是我的节点类的一个例子：
template<typename KEY, typename VALUE, int DEGREE>
struct BNode
{
KEY Keys[DEGREE];
VALUE Values[DEGREE];
BNode<KEY, VALUE, DEGREE>* Children[DEGREE + 1];
BNode<KEY, VALUE, DEGREE>* Parent;
bool IsLeaf;
};（也许我不应该有一个IsLeaf字段，而只是检查它是否有任何子字段，以节省空间）
2条答案
按热度按时间kyvafyod1#
如果所有操作都从根开始，则不需要父指针。
我通常以递归方式编写插入代码，这样调用
node.insert(key)要么返回null，要么返回一个新键，以便在其父级插入。插入从root.insert(key)开始，它找到合适的子级并调用child.insert(key)。当到达叶节点时，执行插入，如果叶节点分裂，则返回非空值。然后父节点将插入新的内部键，如果分裂，则返回非空值，等等。如果
root.insert(key)返回非空值，则是时候创建新的根了hgc7kmma2#
即使你在沿着树往下走的时候没有使用递归或者显式堆栈，如果你用一个稍微修改过的算法来更快地分割节点，你仍然可以在没有父指针的情况下完成它，这个算法有以下关键特征：
使用这种 * 抢先拆分 * 算法，您只需保留对直接父级的引用（不是任何其它祖先）以使分裂成为可能，因为现在保证了分裂将不会导致另一个分裂，在树中向上级联拆分。此算法要求最大度（子节点的数目）是 * 偶数 *（因为否则两个分割节点中的一个将具有太少的键而被认为是有效的）。
另请参阅Wikipedia，其中描述了此替代算法，如下所示：
另一种算法支持从根节点到插入节点的单次遍历，在此过程中，如果遇到满节点，则会抢先将其拆分。这就避免了将父节点重新调用到内存中的需要，如果节点在二级存储上，则这可能会很昂贵。然而，要使用此算法，我们必须能够将一个元素发送到父节点，并拆分剩余的𝑈-2个元素这需要𝑈= 2𝐿而不是𝑈= 2𝐿 −1，这也解释了为什么有些教科书在定义B-树时会有这样的要求。
同一条款定义𝑈并𝐿：
每个内部节点最多包含个𝑈子节点，最少包含个𝐿子节点。
有关与标准插入算法的比较，另请参见Will a B-tree with preemptive splitting always have the same height for any input order of keys?