c - 红黑树程序崩溃

Question

我正在尝试用 C 语言编写红黑树算法的实现，但在执行函数 insert() 后，我崩溃了，程序停止工作。该函数首先找到应添加新值的位置，然后执行另一个名为 Correct_Tree 的函数，该函数负责以正确的顺序和颜色纠正节点。

我收到的警告很少，但不知道如何修复它们，以相同方式构建的其他函数工作正常。

|69|warning: conflicting types for 'correct_tree' [enabled by default]|

|40|note: previous implicit declaration of 'correct_tree' was here|

同样的警告指向函数Rot_L，我不知道这个警告是否会导致我的崩溃。我将感谢您的每一个答案，如果您需要更多信息，请告诉我。抱歉我的英语不好，我不是母语人士。

以下是这些函数:http://ideone.com/hsYyES 结构如下:

struct node {
    int value;
    int key_amounts;
    char color;
    struct node *parent;
    struct node *left;
    struct node *right;
} *root;

int insert(int n, struct node *start) {
    //if node doesnt exist then add it to the tree otherwise increase amount of    keys

    //if tree is empty add root
    if (root == NULL) {
        root = (struct node*)malloc(sizeof *root);
        root->value = n;
        root->keys_amount = 0;
        root->left = NULL;
        root->right = NULL;
        root->up = NULL;
    } else
    if (search(root, n) != NULL) {
        struct node *tmp = search(root, n);
        tmp->keys_amount += 1;
        return 0;
    } else
    //if value is lower than root val then go to left son
    if (n < start->value) {
        //if left son exist then apply function insert for it
        if (start->left != NULL) {
            insert(n, start->left);
        } else {
            //if it doesnt exist then create 
            struct node *new = (struct node*)malloc(sizeof *root);
            new->value = n;
            new->keys_amount = 0;
            new->left = NULL;
            new->right = NULL;
            new->up = start;
            start->left = new;
            correct_tree(new);
        }
    } else {
        //if new value is higher than root
        //if right son exist then apply function for it
        if (start->right != NULL) {
            insert(n, start->right);
        } else {
            //if it doesnt exist create new one
            struct node *new = (struct node*)malloc(sizeof *root);
            new->value = n;
            new->keys_amount = 0;
            new->left = NULL;
            new->right = NULL;
            new->up = start;
            start->right = new;
            correct_tree(new);
        }
    }
    return 0;
}

//////////////////////////////////////////////////////////////////

void correct_tree(struct node *start) {
    struct node *tmp = (struct node*)malloc(sizeof *root);
    start->color = 'R';
    while ((start != root) && (start->up->color == 'R')) {
        if (start->up == start->up->up->left) {
            tmp = start->up->up->right; //uncle of start for tmp
            if (tmp->color == 'R') { //case 1
                start->up->color = 'B';
                tmp->color = 'B';
                start->up->up->color='R';
                start = start->up->up;
                continue;
            }
            if (start == start->up->right) { //case 2
                start = start->up;
                rot_L(start);
            }
            start->up->color = 'B'; //case3
            start->up->up->color = 'R';
            rot_R(start->up->up);
            break;
        } else { //mirror cases
            tmp = start->up->up->left;
            if (tmp->color == 'R') { //case 1
                start->up->color = 'B';
                tmp->color = 'B';
                start->up->up->color = 'R';
                start = start->up->up;
                continue;
            }
            if (start == start->up->left) { //case 2
                start = start->up;
                rot_R(start);
            }
            start->up->color = 'B'; //case3
            start->up->up->color = 'R';
            rot_L(start->up->up);
            break;
        }
    }
    root->color = 'B';
}

//////////////////////////////////////////////////////////////

void rot_L(struct node *start) {
    struct node *tmp = (struct node*)malloc(sizeof *root);
    struct node *tmp2 = (struct node*)malloc(sizeof *root);
    tmp = start->right;
    if (tmp != NULL) {
        tmp2 = start->up;
        start->right = tmp->left;
        if (start->right != NULL)
            start->right->up = start;
        tmp->left = start;
        tmp->up = tmp2;
        start->up = tmp;
        if (tmp2 != NULL) {
            if (tmp2->left == start)
                tmp2->left = tmp;
            else
                tmp2->right = tmp;
        } else
            root = tmp;
    }
}

Answer 1

编译器发出的警告告诉您，您没有声明或定义 correct_node在调用它之前。编译器从调用中推断出的原型(prototype)是 int correct_tree(struct node *start);这与稍后遇到的实际定义不兼容: void correct_tree(struct node *start) 。 rot_L() 同样的问题。在调用之前声明所有函数。

函数correct_node肯定会失败，因为您取消引用 up链接而不首先检查它们不是 NULL 。例如您第一次调用 correct_node on the左or右child of the root` 节点，你有:

start->color = 'R';
while ((start != root) && (start->up->color == 'R')) {
    if (start->up == start->up->up->left) {

您没有初始化 color root的由 malloc() 分配的节点。有很小的机会root->color可能等于'R' ，这将导致start->up->up->left具有未定义的行为 start->up->up是 NULL .

另一个问题是:

struct node *tmp = (struct node*)malloc(sizeof *root);

为 tmp 分配的对象从未使用过，从未释放过并且 tmp在循环中被覆盖。这是一个公然的内存泄漏案例。

同一问题在 rot_L 中出现两次，对于tmp和tmp2 .