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

Answer 1

Okay after a lot of testing I found an interesting case where the code above works. Most noticeable, the line auto *grand_p = root->parent; was causing the problem. If I create a method like

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

and then access the parent through this method call

auto *grand_p = parent(root);

then there would be no segfault and the whole rotation of the tree would be exactly as it should.

Due to my limited knowledge of compiler optimization and how references are handled underneath, I would assume that the following is happening.

In both cases I am getting a copy of the parent pointer to the grandparent variable, but when this is done through a function, the compiler does not do any optimization and dereferencing, which would cause the segfault.

Here is another question which has a similar topic

Answer 2

The only time rebalance should reiterate is the case where the aunt is red, and in that case the next node to be handled will be the grandparent, not the parent. If the aunt is black then after the single or double rotation you are done.

Remember, the insert logic is:

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

You appear not to have the "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" step at all.

And even the final step you don't exchange the colors of the node and its parent (note at this stage 'node' is the parent of the red violation rather than the child as it started out before the optional rotation).

Also, you have:

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

but then immediately rotate, the case where the aunt is black is when you should color flip, not rotate.