0

我正在查看插入增强的红黑树的代码。这棵树有一个称为“大小”的附加字段，它保持以节点 x 为根的子树的大小。这是插入新节点的伪代码：

AugmentedRBT_Insert(T,x){
    BST_Insert(T,x); //insert as if it is a normal BST
    x[color]=red; //insert as a red node
    size[x]=1;
    tmp=parent[x];
    while(tmp!=NULL){   //start from the node x and follow the path to root
        size[tmp]=size[tmp]+1;  //update the size of each node
        tmp=parent[tmp];
    }
}

忘记修复着色和旋转，它们将在另一个函数中完成。我的问题是，为什么我们将新添加的节点“x”的大小设置为1？我知道它不会有任何子树，所以它的大小必须为1，但是RBT的要求之一是每个红色节点都有两个黑色孩子，实际上每个叶子节点都是NULL，即使我们插入节点“x “作为黑色，它仍然应该有 2 个黑色 NULL 节点，我认为我们必须将其大小设置为 3？我错了吗？

谢谢。

4

1 回答 1

1

与大多数二叉树一样，红黑树中的插入直接发生在叶子上。因此，以叶子为根的子树的大小为 1。红色节点确实有两个黑色子节点，因为叶子总是有“根”或“nil”作为子节点，即黑色。那些空元素不是节点，所以我们不会计算它们。

然后，我们将所有父节点的大小调整到根节点（对于我们刚刚添加的节点，它们每个都得到 +1）。

最后，如果有必要，我们会在旋转树以平衡它时修复这些值。在您的实现中，您可能希望一次完成大小更新和旋转，而不是两次。

于 2013-03-23T23:09:18.360 回答