(*p)->left->prev means *p

Question

I wrote a red-black tree program implementation. I ran into a problem in the left_rotation function.

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;
}

It turned out that the left_son->prev = dad; part equivalent to *p = (*p)->prev;.

Here is the programs minimal reproducible example:

/* 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;

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

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 **p, int num, int *height)
{
    node *previous = NULL;
    node **position = NULL;
    find_node(num, p, &previous, &position);
    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 the root was */
            *p = *position;                     /* changed and set a new root */
        } else 
            (*position)->color = black;         /* it's the very 1st node */
        *height = tree_height(*p);
    }
}

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);
    printf("Current tree height is %d.\n", height);
    free_tree(root);
    return 0;
}

I see that in the line 228 self_balance(&GRANDPA_VAR_PAR); I myself passed to the function the very address which I can't edit later in the left_rotation function.

I know that one way to fix the problem is to change the left_rotation function argument from node ** to node *. But I wonder if there is a way to fix the function in it's current state.

I tried to rewrite the part starting with the line 226

        if (uncle_is_red(*p)) {
            recolor(p);
            self_balance(&GRANDPA_VAR_PAR);
        } else

as

        if (uncle_is_red(*p)) {
            node *tmp = GRANDPA_VAR_PAR;
            recolor(p);
            self_balance(&tmp);
        } else

but it didn't help.

I would appreciate any advice :)

Answer 1

What I learned while fixing this bug:

When working with an address like node **p, always remember:

• The address in the p variable can be accessed not only through p.
• Allowing its accidental change may cause severe distortion in the data structure.
• To protect the address in the p variable, you can pass it to a function as node *const *p or just as node *p.

In the end, I chose the latter option (passing the value to the function as node *p). Indeed, the left_rotation function doesn't have the task of altering the address stored in the p variable. Therefore, it's entirely possible to pass its value to the function as a local copy, and it won't affect anything.

The left_rotation function is specifically designed to alter connections in a data structure, and it will successfully achieve this goal by using the local address copy to access the data structure.