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

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)

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