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

For this sort of thing I've found on-paper debugging helpful. — 500 - Internal Server Error, Apr 17 '19 at 11:11
print your tree before the failing step, check whether your assumptions are correct — , Apr 17 '19 at 11:14
I don't think we can help you all that much without a complete example where we could see the crash for ourselves (see also [Minimal, Complete, and Verifiable example](https://stackoverflow.com/help/mcve) ) — , Apr 17 '19 at 11:16
If you are getting a segfault at the indicated position then tmp is null )and tmp->right is meaningless). Trying to rotate a null node into a parent position to any other node indicates you have an error in the logic that determines what node you are treating as root for the call to the rotation function. Beyond that, as said, we need an MCV example. — SoronelHaetir, Apr 17 '19 at 23:07
Sorry for the late reply and sorry for not providing enough. I hope with the edit it is more clear. — mnestorov, Apr 18 '19 at 09:55
@SoronelHaetir the logic on paper should be like this, I understand what you mean, but however I try to go around it, I have to point the left side of the current root to the right side of the right tmp. Doing it later will result in an invalid tree. — mnestorov, Apr 18 '19 at 09:58

score 0 · Answer 1 · answered Apr 18 '19 at 16:04

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.

True, I do not have that logic. I was trying to provide a minumal running examlpe for the issue. You are correct when you state the rules, but the problem I am having is not with the rotation logic, but with the pointers and their references. Upon `root->left = tmp->right;` it is crashing because of `tmp->right` being null, and that's understandable, but it should not be like that and in other implementations it works with that pointer logic. — mnestorov, Apr 18 '19 at 19:21
The fact that you are getting a null node at that position means that you have an error somewhere in the logic before that (perhaps even on a prior insert, that is why you were told to print out your tree and examine that the RB tree conditions have actually been met). That it shows up in the rotation is merely a symptom. Your current problem is elsewhere. There may or may not be problems in the rotation function, I haven't examined that particularly closely since you aren't calling for a rotate in the right conditions in the code I commented on. — SoronelHaetir, Apr 18 '19 at 22:10

score 0 · Accepted Answer · answered Apr 21 '19 at 20:32

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

Red-Black Tree rebalancing crashes on tree rotation

2 Answers2