C++ red-black 树实现的问题

Question

我正在尝试制作 RB 树的 C++ 实现。但是当我尝试删除一个元素时——我发现树的一些叶子具有不同的黑色高度值。在调用 remove 函数之前一切正常 - 树插入后的插入和重新平衡工作正常。但是在一次调用 remove 函数之后它就不再平衡了。

常规删除：

void RbTree::remove(int data) {
Node* cur = root;
while (cur != nil && cur->data != data) { // Searching for node with expected key
    if (cur->data < data)
        cur = cur->RIGHT;
    else
        cur = cur->LEFT;
    if (cur == nil) 
        return;
}
removeNode(cur); // Recurrent BST node removing

RbTree::Node* RbTree::removeNode(Node*& cur) {
    if (cur->RIGHT == nil && cur->LEFT == nil) { // No children
        Node* dad = cur->ancestor;
        if (cur == root) { // If current node is root
            cur = root = nil;
        }     else { // Dad now points to nil
            if (cur->color == BLACK)
            fixRemoving(cur);
        dad->RIGHT == cur ? dad->RIGHT = nil : dad->LEFT = nil; 
    }
} else if (!(cur->RIGHT != nil && cur->LEFT != nil)) { // If there's only one children for current node
    Node* dad = cur->ancestor;
    Node* son;
    cur->RIGHT != nil ? son = cur->RIGHT : son = cur->LEFT; // Searching for son
    dad->RIGHT == cur ? dad->RIGHT = son : dad->LEFT = son; // Dad now points to son
    son->ancestor = dad;
    son->color = BLACK; // Changing son's color
    if (cur->color == BLACK) {
        fixRemoving(son);
    }
} else { // If left and right child exist
    Node* found = findMin(cur->RIGHT); // Finding the least element in right subtree
    cur->data = found->data; // Copying data
    removeNode(found); // Recurrently remove found node
}
return cur;

修复删除功能：

void RbTree::fixRemoving(Node*& node) {
Node* dad = node->ancestor;
Node* bro;
if (node == dad->LEFT) {
    bro = dad->RIGHT;
    if (bro->color == RED) {
        bro->color = BLACK;
        dad->color = RED;
        leftRotate(dad);
        bro = dad->RIGHT;
    }
    Node* leftNephew = bro->LEFT;
    Node* rightNephew = bro->RIGHT;
    if (leftNephew->color == BLACK && rightNephew->color == BLACK) { // 1) If both of bro's children are black
        bro->color = RED;
        dad->color = BLACK; 
        fixRemoving(dad);
        return;

    } else if (leftNephew->color == RED) { // 2) Else if only left is red - we need to make those steps and go to 3)
        leftNephew->color = BLACK;
        bro->color = RED;
        rightRotate(bro); 
    }
    rightNephew->color = BLACK; // 3) Now left nephew is black and right is red
    bro->color = dad->color;
    dad->color = BLACK;
    leftRotate(dad);
} else { // Same things there
    bro = dad->LEFT;
    if (bro->color == RED) {
        bro->color = BLACK;
        dad->color = RED;
        rightRotate(dad);
        bro = dad->LEFT;
    }
    Node* leftNephew = bro->LEFT;
    Node* rightNephew = bro->RIGHT;
    if (leftNephew->color == BLACK && rightNephew->color == BLACK) {
        bro->color = RED;
        dad->color = BLACK;
        fixRemoving(dad);
        return;
    } else if (leftNephew->color == RED) {
        leftNephew->color = BLACK;
        bro->color = RED;
        rightRotate(bro);
    }
    rightNephew->color = BLACK;
    bro->color = dad->color;
    dad->color = BLACK;
    rightRotate(dad);
}

我想我可能有以下问题：

使用正确的节点参数调用 fixRemoving 函数
fixRemoving 方法的主体

我正在使用的算法：

找到一个我们想要删除的节点，就像我们在普通 BST 中所做的那样。
如果它没有 children - 只需删除它，如果它只有 1 children - 我们放置这个 child 而不是可移动节点，将其着色为黑色。
如果它同时具有 children - 我们在右子树中找到最少的元素并循环删除他。
如果节点的原始颜色是黑色 - 那么我们需要修复一棵树。

修复算法已在代码中描述 - 我希望不需要额外的信息。

求求你帮忙！

Answer 1

我基本同意你的算法。但我不同意在只有 1-child 时尝试修复节点。找到要删除的节点后 - 计算其 children 在 3 种情况下，删除节点很容易，成本也很低。那些是

0-children 节点为红色 => 直接删除它
0-children且该节点为根节点=>删除即可
1-child，所有情况。实际情况是要删除的节点是黑色的，而 child 是红色的。其他 3 种可能性都是无效的 Red-Black 树，因此不会发生。解决方案是删除节点，替换为 child，并将 child 设为黑色。不需要其他进一步的修正。

对于2-children，你需要找到继任者（右边child然后左边尽可能远）或前任（左边child然后右边最远）你可以走了）。这个节点永远是0或者1child的情况，不可能是2。我会测试 successor/predecessor 是否是“便宜删除”节点，如果不是，则选择 predecessor/successor。您的目标是获得便宜的删除。然后，您需要使用 successor/predecessor 交换要删除的节点，但保留原始颜色。交换了节点（我的意思是所有指针链接）之后，您的问题就减少到删除一个具有 0 到 1 child 的节点，这可能很容易。

那还剩下什么？

也就是删除一个0-children节点，叶子节点，颜色为黑色，不是根节点。这是需要修正的情况，没有其他情况需要修正。

C++ red-black 树实现的问题

Problems with C++ red-black tree implementation

c++

algorithm

tree

red-black-tree