Red Black Tree - fixTree реализация не работает правильно

Question

У меня возникла проблема с отображением RedBlack Tree после вставки нескольких цифр. Вероятно, функция fixTree содержит некоторые ошибки (после ввода чисел отображается только первое число = 38).

Есть ли у кого-нибудь идеи, что не так?

#include <stdio.h> 
#include <stdlib.h> 
#define swap(type, i, j) {type t = i; i = j; j = t;} 

typedef enum COLOR{ 
    RED, 
    BLACK 
} NodeColor; 

typedef struct BST{ 
    struct BST *up, *left, *right; 
    int key, color; 
} RedBlackTree; 

RedBlackTree *tree = NULL; 

RedBlackTree *createNode(int key){ 
    RedBlackTree *temp; 
    temp = (RedBlackTree*) malloc(sizeof(RedBlackTree)); 
    temp->left = NULL; 
    temp->right = NULL; 
    temp->key = key; 
    temp->color = RED; 
    return temp; 
} 

void rotateLeft(RedBlackTree *root, RedBlackTree *temp){ 
    RedBlackTree *rightSon = temp->right; 
    temp->right = rightSon->left; 
    if (temp->right != NULL){ 
    temp->right->up = temp; 
    } 
    rightSon->up = temp->up; 
    if (temp->up == NULL){ 
    root = rightSon; 
    } 
    else if (temp == temp->up->left){ 
    temp->up->left = rightSon; 
    } 
    else{ 
    temp->up->right = rightSon; 
    } 
    rightSon->left = temp; 
    temp->up = rightSon; 
} 

void rotateRight(RedBlackTree *root, RedBlackTree *temp){ 
    RedBlackTree *leftSon = temp->left; 
    temp->left = leftSon->right; 
    if (temp->left != NULL){ 
    temp->left->up = temp; 
    } 
    leftSon->up = temp->up; 
    if (temp->up == NULL){ 
    root = leftSon; 
    } 
    else if (temp == temp->up->left){ 
    temp->up->left = leftSon; 
    } 
    else{ 
    temp->up->right = leftSon; 
    } 
    leftSon->right = temp; 
    temp->up = leftSon; 
} 

void fixTree(RedBlackTree *root, RedBlackTree *temp){ 
    RedBlackTree *parent = NULL; 
    RedBlackTree *grandparent = NULL; 
    while ((temp != root) && (temp->color != BLACK) && (temp->up->color == RED)){ 
    parent = temp->up; 
    grandparent = temp->up->up; 
    if (parent == grandparent->left){ 
     RedBlackTree *uncle = grandparent->right; 
     if (uncle != NULL && uncle->color == RED){ 
     grandparent->color = RED; 
     parent->color = BLACK; 
     uncle->color = BLACK; 
     temp = grandparent; 
     } 
     else{ 
     if (temp == parent->right){ 
      rotateLeft(root, parent); 
      temp = parent; 
      parent = temp->up; 
     } 
     rotateRight(root, grandparent); 
     swap(int, parent->color, grandparent->color); 
     temp = parent; 
     } 
    } 
    else{ 
     RedBlackTree *uncle = grandparent->left; 
     if ((uncle != NULL) && (uncle->color == RED)){ 
     grandparent->color = RED; 
     parent->color = BLACK; 
     uncle->color = BLACK; 
     temp = grandparent; 
     } 
     else{ 
     if (temp == parent->left){ 
      rotateRight(root, parent); 
      temp = parent; 
      parent = temp->up; 
     } 
     rotateLeft(root, grandparent); 
     swap(int, parent->color, grandparent->color); 
     temp = parent; 
     } 
    } 
    } 
    root->color = BLACK; 
} 

RedBlackTree *insertNode(RedBlackTree *root, RedBlackTree *temp){ 
    if (root == NULL){ 
    return temp; 
    } 
    if (temp->key < root->key){ 
    root->left = insertNode(root->left, temp); 
    root->left->up = root; 
    } 
    else if (temp->key > root->key){ 
    root->right = insertNode(root->right, temp); 
    root->right->up = root; 
    } 
    return root; 
} 

void insert(int key){ 
    RedBlackTree *temp = createNode(key); 
    tree = insertNode(tree, temp); 
    fixTree(tree, temp); 
} 

void printTree(RedBlackTree *root){ 
    if (root){ 
    printTree(root->left); 
    printf("%d %s\n", root->key, root->color == 0 ? "RED" : "BLACK"); 
    printTree(root->right); 
    } 
} 

int main(){ 
    insert(38); 
    insert(31); 
    insert(22); 
    insert(8); 
    insert(20); 
    insert(5); 
    insert(10); 
    insert(9); 
    insert(21); 
    insert(27); 
    insert(29); 
    insert(25); 
    insert(28); 
    printTree(tree); 
    return 0; 
} 

Answer 1

void fixTree(RedBlackTree *root, RedBlackTree *temp) 

Вы передаете адрес корня по значению, так что любое изменение rootвнутриfixTree не будет виден в вызывающем коде. В частности, rotateLeft и rotateRight, где вы снова копия адрес, не будет изменять переменную в вызывающем коде.

Вам необходимо передать указатель на указатель корня. Значение ваш прототип должен быть

void fixTree(RedBlackTree **p_root, RedBlackTree *temp) 

естественно операция регулируется таким образом, они предварительно на *p_root. Например, следующая строка в rotateLeft:

*p_root = rightSon;