c++ - Red-Black Tree rebalancing crashes on tree rotation

Question

I am implementing a red-black tree. Currently stuck on tree rotations. When I rotate and assign the new left/right children, I crash and burn. The way I have learned to do left or right rotations on a binary tree is like so (in c++):

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

This works fine for an AVL tree.

Here is the RB-tree. I'll try to post the minimum it takes to reproduce this

#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;
}

From what I know, the tmp->left is a nullptr, thus when I am assigning it to the root->left it is normal to segfault. How do I overcome this and both execute this step and not terminate?

I have searched over SO and other internet corners and have seen that people use this approach and they do not complain of this segfault.

If I do a check if (tmp->right) root->left = tmp->right; then the code is not being executed and I am skipping over a critical algorithm step. With this if statement, I get a tree where some of the nodes point to themselves and it gets really messy.

Sample case

To get this situation, I insert 3(root)->1(go left of 3)->5(go right of 3)->7(go right of 5)->6(go left of 7). A balance must be made at 5->7->6. The logic is to do a Right-Left rotation. At the right rotation, this situation is happening

标签： c++red-black-treered-black-tree-insertion

Answer 1

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

请记住，插入逻辑是：

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 (!aunt || aunt->rb == 0)

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