Red-Black 树重新平衡在树旋转时崩溃

Question

我正在实施 red-black 树。目前停留在树旋转上。当我旋转并分配新的 left/right children 时，我崩溃了。我学会了在二叉树上进行左旋转或右旋转的方法是这样的（在 c++ 中）：

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

这适用于 AVL 树。

这里是RB-tree。我将尝试 post 重现此内容所需的最低限度

#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(3 的左边) 7).必须在 5->7->6 之间进行平衡。逻辑是进行 Right-Left 旋转。在正确的旋转中，这种情况正在发生

Answer 1

唯一一次重新平衡应该重申的是阿姨是红色的情况，在这种情况下，下一个要处理的节点将是 grandparent，而不是 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

您似乎根本没有 "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" 步骤。

甚至最后一步你也不交换节点的颜色和它的parent（注意在这个阶段'node'是红色违规的parent而不是child，因为它在可选轮换之前开始。

此外，您还有：

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

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

Answer 2

好的，经过大量测试后，我发现了一个有趣的案例，上面的代码可以正常工作。最引人注目的是 auto *grand_p = root->parent; 行导致了问题。如果我创建一个像

这样的方法

foo *rbtree::parent(foo *root)
{
    return *&root->parent;
}

然后通过这个方法调用访问parent

auto *grand_p = parent(root);

那么就不会有段错误，树的整个旋转将完全按照它应该的方式进行。

由于我对编译器优化以及底层如何处理引用的了解有限，我假设发生了以下情况。

在这两种情况下，我都得到了指向 grandparent 变量的 parent 指针的副本，但是当这是通过函数完成时，编译器不会进行任何优化和取消引用，这会导致段错误。

这是另一个问题 similar topic

Red-Black 树重新平衡在树旋转时崩溃

Red-Black Tree rebalancing crashes on tree rotation

c++

red-black-tree

red-black-tree-insertion