LINUX.ORG.RU
Форум — Development  

Красно-чёрное дерево. Потеря связности блоков памяти

 , ,


0

3

Пишу красно-чёрное дерево на Си.

В данный момент в коде уже реализованы функции перекрашивания recolor, а также левого и правого поворотов с перекрашиванием left_rotation_and_recolor и right_rotation_and_recolor, что позволяет обрабатывать последовательности чисел отсортированных как по возрастанию, так и по убыванию.

Теперь пришла пора реализовать функции left_rotation и right_rotation, чтобы можно было выполнить вставку узла в ситуации, подобной приведённой ниже (применив сначала перекрашивание, затем левый поворот и затем правый поворот с перекрашиванием):

        50(b)                       50(b)                       50(b)                           30(b)
        /  \                        /  \                        /  \                            /  \
    20(r)   60(b)               20(r)   60(b)               30(r)   60(b)                   20(r)   50(r)
    /  \       \                /  \       \                /  \       \                /       \   /       \
10(b)   30(b)   70(r)   =>  10(b)   30(r)   70(r)   =>  20(r)   40(b)   70(r)   =>  10(b)   25(b)   40(b)   60(b)
        /  \                        /  \                /  \                                /                  \
    25(r)   40(r)               25(b)   40(b)       10(b)   25(b)                       22(r)                   70(r)
    /                           /                           /
22(r)                       22(r)                       22(r)

Однако, в процессе этого в функции left_rotation

void left_rotation(node **p)
{
    node *left_son = LEFT_SON_VAR_PAR; /* (*p)->left */
    node *dad = DAD_VAR_PAR;
    node *grandpa = GRANDPA_VAR_PAR;
    grandpa->left = *p;
    (*p)->prev = grandpa;
    dad->prev = *p;
    dad->right = left_son;
    if (left_son)
        left_son->prev = dad;
    (*p)->left = dad;
}

после исполнения кода в строке left_son->prev = dad; одномоментно теряется связность сразу множества блоков памяти и дерево «перекорёживается».

Это хорошо видно при отладке в GDB:

215	        left_son->prev = dad;
5: left_son->value = 25
6: dad->value = 20
7: grandpa->value = 50
8: (*p)->prev->value = 50
9: (*p)->right->value = 40
10: (*p)->left->left->value = 22
11: (*p)->value = 30
(gdb) n
216	    (*p)->left = dad;
5: left_son->value = 25
6: dad->value = 20
7: grandpa->value = 50
8: (*p)->prev->value = 30
9: (*p)->right->value = 25
10: (*p)->left->left->value = <error: Cannot access memory at address 0x18>
11: (*p)->value = 20

Никак не могу взять в толк, с чем это связано. Может кто-то популярно объяснить?

Полный текст программы:

/* red-black_tree.c */

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <stdbool.h>

#define GREATGRANDPA_VAR_PAR (*p)->prev->prev->prev
#define GRANDPA_VAR_PAR (*p)->prev->prev
#define RIGHT_UNCLE_VAR_PAR (*p)->prev->prev->right
#define LEFT_UNCLE_VAR_PAR (*p)->prev->prev->left
#define RIGHT_UNCLE p->prev->prev->right
#define LEFT_UNCLE p->prev->prev->left
#define DAD_VAR_PAR (*p)->prev
#define DAD p->prev
#define RIGHT_BRO_VAR_PAR (*p)->prev->right
#define LEFT_BRO_VAR_PAR (*p)->prev->left
#define RIGHT_BRO p->prev->right
#define LEFT_BRO p->prev->left
#define LEFT_SON_VAR_PAR (*p)->left

typedef enum tag_node_color { red, black } node_color;

typedef struct tag_node {
    struct tag_node *left, *right, *prev;
    int value;
    node_color color;
} node;

node **find_node(int num, node **p, node **previous)
{
    if ((!*p) || ((*p)->value == num))
        return p;
    *previous = *p;
    if (num < (*p)->value)
        return find_node(num, &(*p)->left, previous);
    else
        return find_node(num, &(*p)->right, previous);
}

int tree_height(node *p)
{
    int curr_height = 0;
    if (!p)
        return 0;
    if (tree_height(p->left) >= tree_height(p->right))
        curr_height = tree_height(p->left);
    else
        curr_height = tree_height(p->right);
    return curr_height + 1;
}

node **current_root_is(node **p)
{
    return (!DAD_VAR_PAR) ? p : current_root_is(&DAD_VAR_PAR);
}

bool grandpa_is_right_son(node *p)
{
    return (p->value == RIGHT_BRO->value) ? true : false;
}

void left_rotation_and_recolor(node **p)
{
    node *dad = DAD_VAR_PAR;
    node *left_bro = LEFT_BRO_VAR_PAR;
    node *grandpa = GRANDPA_VAR_PAR;
    node *great_grandpa = GREATGRANDPA_VAR_PAR;
    if (great_grandpa) {
        if (grandpa_is_right_son(grandpa))
            great_grandpa->right = dad;
        else
            great_grandpa->left = dad;
    }
    if (left_bro)
        left_bro->prev = grandpa;
    grandpa->right = left_bro;
    dad->left = grandpa;
    dad->prev = great_grandpa;
    grandpa->prev = dad;
    dad->color = black;
    grandpa->color = red;
}

void right_rotation_and_recolor(node **p)
{
    node *dad = DAD_VAR_PAR;
    node *right_bro = RIGHT_BRO_VAR_PAR;
    node *grandpa = GRANDPA_VAR_PAR;
    node *great_grandpa = GREATGRANDPA_VAR_PAR;
    if (great_grandpa) {
        if (grandpa_is_right_son(grandpa))
            great_grandpa->right = dad;
        else
            great_grandpa->left = dad;
    }
    if (right_bro)
        right_bro->prev = grandpa;
    grandpa->left = right_bro;
    dad->right = grandpa;
    dad->prev = great_grandpa;
    grandpa->prev = dad;
    dad->color = black;
    grandpa->color = red;
}

bool dad_is_left_son(node *p)
{
    if (!LEFT_UNCLE)
        return false;
    if (LEFT_UNCLE->value == DAD->value)
        return true;
    else
        return false;
}

bool dad_is_right_son(node *p)
{
    if (!RIGHT_UNCLE)
        return false;
    if (RIGHT_UNCLE->value == DAD->value)
        return true;
    else
        return false;
}

bool im_left_son(node *p)
{
    if (!LEFT_BRO)
        return false;
    if (LEFT_BRO->value == p->value)
        return true;
    else
        return false;
}

bool im_right_son(node *p)
{
    if (!RIGHT_BRO)
        return false;
    if (RIGHT_BRO->value == p->value)
        return true;
    else
        return false;
}

bool uncle_is_black(node *p)                        /* technically I check */
{                                       /* if both parent and uncle are black */
    if ((!LEFT_UNCLE) || (!RIGHT_UNCLE))
        return true;
    if ((LEFT_UNCLE->color == black) || (RIGHT_UNCLE->color == black))
        return true;
    else
        return false;
}

void set_grandpa_color_red(node **p)
{
    if (!GREATGRANDPA_VAR_PAR)
        return;
    else
        GRANDPA_VAR_PAR->color = red;
}

void set_dad_and_uncle_colors_black(node **p)
{
    if ((!LEFT_UNCLE_VAR_PAR) || (!RIGHT_UNCLE_VAR_PAR))
        return;
    LEFT_UNCLE_VAR_PAR->color = black;
    RIGHT_UNCLE_VAR_PAR->color = black;
}

void self_balance(node **p);

void recolor(node **p)
{
    set_dad_and_uncle_colors_black(p);
    set_grandpa_color_red(p);
    self_balance(&GRANDPA_VAR_PAR);
}

bool uncle_is_red(node *p)                          /* technically I check */
{                                       /* if both parent and uncle are red */
    if ((!LEFT_UNCLE) || (!RIGHT_UNCLE))
        return false;
    if ((LEFT_UNCLE->color == red) &&
        (RIGHT_UNCLE->color == red))
    {
        return true;
    } else {
        return false;
    }
}

bool dad_is_red(node *p)
{
    return (DAD->color == red) ? true : false;
}

bool dad_is_black(node *p)
{
    return (DAD->color == black) ? true : false;
}

void left_rotation(node **p)
{
    node *left_son = LEFT_SON_VAR_PAR; /* (*p)->left */
    node *dad = DAD_VAR_PAR;
    node *grandpa = GRANDPA_VAR_PAR;
    grandpa->left = *p;
    (*p)->prev = grandpa;
    dad->prev = *p;
    dad->right = left_son;
    if (left_son)
        left_son->prev = dad;
    (*p)->left = dad;
}

void self_balance(node **p)
{
    if ((!DAD_VAR_PAR) || (dad_is_black(*p)) || ((*p)->color == black))
        return;
    if (dad_is_red(*p)) {
        if (uncle_is_red(*p)) {
            recolor(p);
            self_balance(&GRANDPA_VAR_PAR);
        } else
        if (uncle_is_black(*p) && im_right_son(*p) && dad_is_right_son(*p)) {
            left_rotation_and_recolor(p);
            self_balance(&DAD_VAR_PAR);
        } else
        if (uncle_is_black(*p) && im_left_son(*p) && dad_is_left_son(*p)) {
            right_rotation_and_recolor(p);
            self_balance(&DAD_VAR_PAR);
        } else
        if (uncle_is_black(*p) && im_right_son(*p) && dad_is_left_son(*p)) {
            left_rotation(p);
            right_rotation_and_recolor(&(*p)->left);
            self_balance(p);
        }
    }
}

void add_node(node **root, int num, int *height)
{
    node **position = NULL;
    node *previous = NULL;
    position = find_node(num, root, &previous);
    if (*position != NULL)
        printf("The node %d already exists.\n", num);
    else {
        *position = malloc(sizeof(node));
        (*position)->value = num;
        (*position)->right = NULL;
        (*position)->left = NULL;
        (*position)->prev = previous;
        if ((*position)->prev) {
            (*position)->color = red;
            self_balance(position);
            position = current_root_is(position);   /* check if root was */
            *root = *position;                  /* changed and set new root */
        } else
            (*position)->color = black;         /* it's the very 1st node */
        *height = tree_height(*root);
    }
}

void print_color_and_dad_value(node *p)
{
    if (p->color == black)
        printf(",blk(");
    else
        printf(",red(");
    if (p->prev == NULL)
        printf(" ) ");
    else
        printf("%d) ", p->prev->value);
}

void print_tree_level(node *p, int height, int curr_height)
{
    if (!p)
        return;
    if (height == curr_height) {
        printf("%d", p->value);
        print_color_and_dad_value(p);
    } else {
        print_tree_level(p->left, height, curr_height+1);
        print_tree_level(p->right, height, curr_height+1);
    }
}

void print_tree(node *p, int height)
{
    int i;
    for (i=1; i <= height; i++) {
        print_tree_level(p, i, 1);
        putchar('\n');
    }
}

void free_tree(node *p)
{
    if (!p)
        return;
    free_tree(p->left);
    free_tree(p->right);
    free(p);
}

int main()
{
    node *root = NULL;
    int i, height = 0;
    int num[] = { 50, 20, 60, 70, 10, 30, 25, 40, 22 };
    for (i=0; i < (int)(sizeof(num)/sizeof(num[0])); i++)
        add_node(&root, num[i], &height);
    putchar('\n');
    print_tree(root, height);
    free_tree(root);
    return 0;
}

LEFT_SON_VAR_PAR

Убери этот ужас и пиши напрямую выражения. Из-за этого скорее всего и запутался - в коде не видно что реально происходит.

Вот так номрально функция должна выглядеть:

void left_rotation(node **p) {
    node *left_son = (*p)->left;
    node *dad = (*p)->prev;
    node *grandpa = (*p)->prev->prev;
    grandpa->left = *p;
    (*p)->prev = grandpa;
    dad->prev = *p;
    dad->right = left_son;
    if (left_son) left_son->prev = dad;   // <----- после этого всё "портится"
    (*p)->left = dad;
}

Судя по тому, что после этого присваивания у тебя поменялось (*p)->left, видимо присваивание изменило значение *p, значит видимо p == &left_son->prev, а *p == left_son->prev. Иначе говоря, на вход left_rotation() ты подал такое p, что p == &(*p)->left->prev.

Проверяем:

dad->value=20, (*p)->value=20 - сходится.

(*p)->prev->value = 30 - видимо это left_son->prev->prev->value или оно же dad->prev->value, а в dad->prev ты раньше записал прошлое значение *p, и (*p)->value до присваивания действительно было 30 - опять сходится.

(*p)->right->value = 25 - это left_son->prev->right->value или оно же dad->right->value, а в dad->right ты записал left_son, left_son->value было 25 - опять сходится.

(*p)->left->left->value = <error> - это left_son->prev->left->left->value или оно же dad->left->left->value, ну а что там было неизвестно, видио не инициализировано.

Мне лень разбираться, что за задачу ты решаешь и что такое красно-чёрное дерево, код «всей программы» не читал (только define посмотрел чтоб расшифровать функцию), но общая проблема в данном случае в том, что ты не учитываешь, что за любым указателем может скрываться элемент, который ты уже начал обрабатывать и менять, и то, как ты его видишь через указатель, при этом тоже будет меняться.

firkax ★★★★★
()
Последнее исправление: firkax (всего исправлений: 4)

Пиши AA-дерево. Это тоже RB-дерево с дополнительной переменной - высоты вершины. Код сильно проще, функциональность и O(logN) - те же самые.

SkyMaverick ★★★★★
()
Последнее исправление: SkyMaverick (всего исправлений: 1) 
#define GREATGRANDPA_VAR_PAR (*p)->prev->prev->prev
#define GRANDPA_VAR_PAR (*p)->prev->prev
#define RIGHT_UNCLE_VAR_PAR (*p)->prev->prev->right
#define LEFT_UNCLE_VAR_PAR (*p)->prev->prev->left
#define RIGHT_UNCLE p->prev->prev->right
#define LEFT_UNCLE p->prev->prev->left
#define DAD_VAR_PAR (*p)->prev
#define DAD p->prev
#define RIGHT_BRO_VAR_PAR (*p)->prev->right
#define LEFT_BRO_VAR_PAR (*p)->prev->left
#define RIGHT_BRO p->prev->right
#define LEFT_BRO p->prev->left
#define LEFT_SON_VAR_PAR (*p)->left

в этих декларациях у тебя используется то p, то (*p)… стоит подставить такую макру в неверном контексте, как будут бага.

все такие макры надо писать с явным параметром, и правильно подставлять его при использовании:

#define GREATGRANDPA_VAR_PAR(ptr)  (*ptr)->prev->prev->prev
alysnix ★★★
()
Последнее исправление: alysnix (всего исправлений: 1)
Ответ на: комментарий от SkyMaverick

Пиши AA-дерево.

вообще не надо ничего писать. все эти деревья реализованы на си раз стопицот…

писать, если только хочешь устроить себе проверку на внимательность, поскольку массово вертеть указатели сразу и без ошибок могут не только лишь все.

alysnix ★★★
()
Ответ на: комментарий от anonymous

Когда учился программировать на Паскале, тоже самое пытался написать и на том-же самом месте споткнулся.

Тогда так и не получилось разобраться что ошибку вызывает.

Поднабрался немного опыта и переписал на Си. Надеюсь, что по Си экспертов больше и кто-нибудь что-то дельное подскажет :D

KOMMUNIST90
() автор топика
Ответ на: комментарий от alysnix

p и *p разного типа, и если их перепутать то программа просто не скомпилируется.

И не надо эти макросы с аргументами, они от этого не становятся сильно понятнее (хотя и чуть лучше), надо их вообще убрать.

firkax ★★★★★
()
Ответ на: комментарий от firkax

p и *p разного типа, и если их перепутать то программа просто не скомпилируется.

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

alysnix ★★★
()
Ответ на: комментарий от alysnix

вообще не надо ничего писать

Ну так-то да. С другой стороны, может ему в рамках чего-нибудь небанального надо. Списков тоже примерно 100500 раз написано и в каждом втором проекте то списки, то очередь, то рингбаф какой-нибудь кастомный

все эти деревья реализованы на си раз стопицот

Более того, на сайте автора алгоритма типовой пример как раз на Си висит, вполне наглядный.

SkyMaverick ★★★★★
()
Ответ на: комментарий от alysnix

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

Вовсе нет, зависит от ситуации. В .h такие макросы делать не стоит, а вот локально вполне удобны. Но не те что у автора.

firkax ★★★★★
()
Ответ на: комментарий от KOMMUNIST90

посмотри реализации других людей, вот, например, на первый взгляд неплохие варианты

  1. https://github.com/prasanthmadhavan/Red-Black-Tree
  2. https://github.com/amitbansal7/Data-Structures-and-Algorithms/blob/master/9.Red-Black-tree/RedBlackTrees.c

ещё можешь у нейросеточки спросить, в какую-нибудь современную, возможно, даже весь твой код поместится, у них там сейчас контекст по 32 тыщи токенов и больше

anonymous
()
Ответ на: комментарий от firkax

ерунда, это когда считают что, чем код неявней и запутанней, тем он лучше.

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

alysnix ★★★
()
Ответ на: комментарий от alysnix

Если макрос длиннее того кода, который из него получается - он не нужен. И это не «простыни указателей» а наглядное указание на логику программы. Макросы в данном случае её совершенно бесполезно (и вредно) прячут.

firkax ★★★★★
()
Ответ на: комментарий от firkax

Спасибо! Благодаря твоему совету наколхозил решение проблемы. В данный момент функция left_rotation выглядит вот так:

node **left_rotation(node *p)
{
    node *left_son = LEFT_SON;
    node *dad = DAD;
    node *grandpa = GRANDPA;
    grandpa->left = p;
    p->prev = grandpa;
    dad->prev = p;
    dad->right = left_son;
    if (left_son)
        left_son->prev = dad;
    p->left = dad;
    return &(p->prev->left);
}

Теперь буду думать, можно ли это переписать поизящнее.

KOMMUNIST90
() автор топика

Разбираться лень, да и особыми компетенциями в области КЧ не сильно обладаю (их не так и много обладает, если начистоту).

Несколько общих советов:

  1. Стандартный набор флагов компилятора: -Wall -Wextra -fsanitize=address -fsanitize=undefined (два последних, также, отдать компоновщику).

  2. Сделать метод, который будет проверять инварианты КЧ-дерева и использовать его после каждой значимой операции с деревом. Ошибки памяти — штука трудноуловимая, и не факт что причины ошибки на данном шаге алгоритма.

  3. Начать с более простых форм деревьев: critbit, qp-trie пока не появится необходимый опыт.

  4. Я бы начал с C++: class и набор friend-методов с передачей по указателю. На C такие вещи писать слегка уныло.

anonymous
()

в продолжении первого комента

вращения(деревья ага) понятней когда указатели(их нужно разом три четыре в зависимости от вида вращения) можно «синхронно» обновлять

в частности кортежное в python али ещё где, где есть конструирование и деконструкция агрегатов на ходу

qulinxao3 ★
()
Ответ на: комментарий от KOMMUNIST90

когда кортежно указатели меняются

вращение понятней ибо

идёт ровно как на картинке - было стало

т.е если язык не поддерживает кортежное обновление просто после формулирования как происходит обновление кортежа уже в ручную транслируешь на целевой байткод - в данном случае С-код приходится руками разносить обмены посредством временных мест

qulinxao3 ★
()

Зачем писать красно-черные деревья? Это такая лабораторная работа? Просто как сказать, красно-чёрное дерево структура известная и часто используемая, потому есть 100500 готовых реализаций под любыми лицензиями.

peregrine ★★★★★
()
Ответ на: комментарий от SkyMaverick

Не понимаю я этого. Ладно я грешу тем что логеры делаю наколенные, для отладки программы во время разработки, чтоб они мне в консольку могли цветом срать и я видел уровни критичности ошибок и предупреждений на глазок, а потом после отладки выпиливаю их/отключаю в релизе, иногда меняя на серьёзные логеры чтоб уже логи нормально делались у юзеров, как принято чтоб юзерам и админам легче жилось. Но тут только потому что когда код отлаживаю и что-то не так работает, как задумывалось (например в тело цикла или условия какого-то не попадаю потому что где-то написал не то условие или что-то не учёл, то часто удобнее и быстрее повесить какой-то log_print(«тут текст», warning/critical/error/debug/info)) чем даже отладчиком visual studio или pycharm-а ставить точки останова, тупо потому что с циклами зачастую удобнее и главное нагляднее срать в консольку, чем жать кнопки по шагам и в голове раскручивать что и как там не так работает.

peregrine ★★★★★
()
Ответ на: комментарий от SkyMaverick

Более того, на сайте автора алгоритма типовой пример как раз на Си висит, вполне наглядный.

код на си есть даже в википедии. «красно-черное дерево».

alysnix ★★★
()
Development