c++ - 红黑树重新平衡在树旋转时崩溃

Question

我正在实现一个红黑树。目前停留在树旋转上。当我旋转并分配新的左/右 child 时，我崩溃了。我学会了在二叉树上进行左旋或右旋的方法是这样的(在 C++ 中):

void right_rotation(node *&root)
{
    auto *temp = root->left;
    root->left = temp->right;
    temp->right = root;
    root = temp;
}

这适用于 AVL 树。

这是 RB 树。我将尝试发布重现此内容所需的最低限度

#include <stdio.h>

struct foo
{
    int key;
    foo *parent;
    foo *left;
    foo *right;
    int rb; // 0 black, 1 red

    foo(int k, foo *p, foo *l, foo *r, int _rb) : key(k), parent(p), left(l), right(r), rb(_rb) {}
};

class rbtree
{
public:
    foo *root{};
    void insert(int key)
    {
        if (root != nullptr)
            insert(root, root, key);
        else
            root = new foo(key, nullptr, nullptr, nullptr, 0);
    }

    void insert(foo *&node, foo *&parent, int key)
    {
        if (!node) {
            node = new foo(key, parent, nullptr, nullptr, 1);
            rebalance(node);
        } else if (key <= node->key) {
            insert(node->left, node, key);
        } else {
            insert(node->right, node, key);
        }
    }

    void rebalance(foo *&node)
    {
        if (!node)
            return;

        if (root == node) {
            root->rb = 0;
            return;
        }

        if (node->rb == 1 && node->parent->rb == 1) {
            auto *grand_p = node->parent->parent;
            foo *aunt;

            if (grand_p->left != node->parent)
                aunt = grand_p->left;
            else
                aunt = grand_p->right;

            if (!aunt || aunt->rb == 0)
                rotate(node, grand_p);
            else
                color_flip(node);
        }

        // if there is no parent to the root
        if (!node->parent)
            root = node;

        rebalance(node->parent);
    }

    void rotate(foo *&node, foo *&grand_parent)
    {
        if (grand_parent->right->left == node) {
            right_left_rot(node);
        } // else the rest is not critical
    }

    void right_rot(foo *&root)
    {
        auto *grand_p = root->parent;
        auto *tmp = root->left;
        if (!tmp->left)
            printf("\nI am about to crash");
        root->left = tmp->right; // segfault here
        // the rest of the rotation logic
        tmp->right = root;
        root->parent = tmp;
        if (root->left)
            root->left->parent = root;
        if (grand_p) {
            if (root == grand_p->left)
                grand_p->left = tmp;
            else if (root == grand_p->right)
                grand_p->right = tmp;
        }
        tmp->parent = grand_p;
    }

    void right_left_rot(foo *&node)
    {
        right_rot(node->parent);
        // rest not important
    }

    void color_flip(foo *&node)
    {
        node->parent->parent->rb = 1;
        node->parent->parent->left->rb = 0;
        node->parent->parent->right->rb = 0;
        if (root->rb != 0)
            root->rb = 0;
    }
};

int main()
{
    rbtree rbt;
    rbt.insert(3);
    printf("\n%s%d", "Added successfully ", 3);
    rbt.insert(1);
    printf("\n%s%d", "Added successfully ", 1);
    rbt.insert(5);
    printf("\n%s%d", "Added successfully ", 5);
    rbt.insert(7);
    printf("\n%s%d", "Added successfully ", 7);
    rbt.insert(6);
    printf("\n%s%d", "Added successfully ", 6);
    return 0;
}

据我所知，tmp->left 是一个 nullptr，因此当我将它分配给 root->left 时段错误是正常的。我如何克服这个问题并同时执行此步骤而不终止？

我搜索过 SO 和其他互联网角落，看到人们使用这种方法并且他们没有提示这个段错误。

如果我检查 if (tmp->right) root->left = tmp->right; 那么代码没有被执行，我跳过了一个关键的算法步骤。通过这个 if 语句，我得到了一棵树，其中一些节点指向它们自己，它变得非常困惑。

示例案例

为了得到这种情况，我插入 3(根)->1(3 的左边)->5(3 的右边)->7(5 的右边)->6(7 的左边) .必须在 5->7->6 之间进行平衡。逻辑是进行右-左旋转。在正确的轮换中，这种情况正在发生

Answer 1

唯一需要重新平衡的是阿姨是红色的情况，在这种情况下，下一个要处理的节点将是祖 parent 节点，而不是父节点。如果阿姨是黑人，那么在单轮或双轮旋转后你就完成了。

记住，插入逻辑是:

insert as normal for any BST
set new node's color to red
LOOP:
if node is root then set node's color black and done
if node's parent's color is black then done
if node's aunt's color is red then set node's parent's and node's aunt's color to black, set node's grandparent's color to red, set node to node's grandparent and go to LOOP
if node is left child of right child or right child of left child then rotate node's parent so it is child to node otherwise set node to node's parent
set node's color to black
set node's parent's color to red
rotate so that node's parent is child to node
done

您似乎根本没有“如果节点是右 child 的左 child 或左 child 的右 child ，则旋转节点的父节点，使其成为节点的子节点，否则将节点设置为节点的父节点”步骤。

即使是最后一步，您也不会交换节点及其父节点的颜色(请注意，在此阶段，“节点”是红色违规的父节点，而不是在可选旋转之前开始的子节点)。

此外，您还有:

if (!aunt || aunt->rb == 0)

然后立即旋转，阿姨是黑色的情况是你应该颜色翻转，而不是旋转。