Красно-чёрное дерево. Потеря связности блоков памяти
Пишу красно-чёрное дерево на Си.
В данный момент в коде уже реализованы функции перекрашивания 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;
}