Красно-Черное дерево восстанавливает равновесие при вращении дерева

Question

Я реализую красно-черное дерево. В данный момент застрял на севооборотах. Когда я поворачиваюсь и назначаю новых левых / правых детей, я падаю и сгораю. Способ, которым я научился делать левые или правые повороты в двоичном дереве, выглядит примерно так (в C++):

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

Это прекрасно работает для дерева AVL.

Вот РБ-дерево. Я постараюсь опубликовать минимум, необходимый для воспроизведения этого

#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 и другие интернет-уголки и видел, что люди используют этот подход, и они не жалуются на этот segfault.

Если я сделаю проверку if (tmp->right) root->left = tmp->right; тогда код не выполняется, и я пропускаю критический шаг алгоритма. С этим if утверждение, я получаю дерево, где некоторые из узлов указывают на себя, и это становится действительно грязным.

Пример дела

Чтобы получить эту ситуацию, я вставляю 3(корень)->1(слева от 3)->5(справа от 3)->7(справа от 5)->6(слева от 7). Баланс должен быть сделан в 5->7->6. Логика состоит в том, чтобы сделать вращение вправо-влево. При правильном вращении эта ситуация происходит

Answer 1

Хорошо, после многих испытаний я обнаружил интересный случай, когда приведенный выше код работает. Наиболее заметно, линия auto *grand_p = root->parent; был причиной проблемы. Если я создаю метод, как

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

а затем получить доступ к родителю с помощью этого вызова метода

auto *grand_p = parent(root);

тогда не будет сегфоута, и весь поворот дерева будет точно таким, каким он должен быть.

Из-за моего ограниченного знания оптимизации компилятора и того, как обрабатываются ссылки ниже, я бы предположил, что происходит следующее.

В обоих случаях я получаю копию родительского указателя на переменную grandparent, но когда это делается с помощью функции, компилятор не выполняет какую-либо оптимизацию и разыменование, что может привести к segfault.

Вот еще один вопрос, который имеет похожую тему

Answer 2

Единственное время, которое следует повторить, - это случай, когда тетя красная, и в этом случае следующий обрабатываемый узел будет прародителем, а не родителем. Если тетя черная, то после одинарного или двойного поворота все готово.

Помните, логика вставки:

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)

но затем немедленно поверните, случай, когда тетя черная, когда вы должны перевернуть цвет, а не вращать.