c - 尝试在 C 中实现红黑树

我需要帮助实现红黑树它似乎在我的 malloc 调用中保持段错误。我不知道如何解决它。任何建议将不胜感激。这些函数似乎在工作，我唯一遇到的问题是分配内存。

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

typedef struct Node {
    int data;
    char color;
    struct Node *left;
    struct Node *right;
    struct Node *parent;
} Node;

Node **Root = NULL;

// A utility function to create a new BST node
Node *newNode(int data) {
    Node *temp = (Node*)malloc(sizeof(Node));
    temp->data = data;
    temp->color = 'R';
    temp->left = NULL;
    temp->right = NULL;
    temp->parent = NULL;

    return temp;
}

void rotateLeft(Node **Root, Node *New) {
    Node *lPtr = New->right;
    New->right = lPtr->left;

    if (lPtr->left != NULL)
        lPtr->left->parent = New;
    lPtr->parent = New->parent;
    if (New->parent == NULL)
        *Root = lPtr;
    else if (New->data == New->parent->left->data)
        New->parent->left = lPtr;
    else
        New->parent->right = lPtr;
    lPtr->left = New;
    New->parent = lPtr;
}

void rotateRight (Node**Root, Node *New) {
    Node *rPtr = New->left;
    New->left = rPtr->right;

    if (rPtr->right != NULL)
        rPtr->right->parent = New;
    rPtr->parent = New->parent;
    if (New->parent == NULL)
        *Root = rPtr;
    else if (New->data == New->parent->left->data)
        New->parent->left = rPtr;
    else
        New->parent->right = rPtr;
    rPtr->right = New;
    New->parent = rPtr;
}

void redBlackInsertFixup(Node **Root, Node *New) {
    Node* temp;
    while (New->parent->color == 'R') {
        if (New->parent->data == New->parent->parent->data) {
            temp = New->parent->parent->right;
            if (temp->color == 'R') {
                New->parent->color = 'B';
                temp->color = 'B';
                New->parent->parent->color = 'R';
                New = New->parent->parent;
            } else
            if (New->data == New->parent->right->data) {
                New = New->parent;
                rotateLeft(Root,New);
            }
            New->parent->color = 'B';
            New->parent->parent->color = 'R';
            rotateRight(Root, New->parent->parent);
        } else {
            temp = New->parent->parent->left;
            if (temp->color == 'R') {
                New->parent->color = 'B';
                New->color = 'B';
                New->parent->parent->color = 'R';
                New = New->parent->parent;
            } else
            if (New->data == New->parent->left->data) {
                New = New->parent;
                rotateRight(Root, New);
            }
            New->parent->color = 'B';
            New->parent->parent->color = 'R';
            rotateLeft(Root, New->parent->parent);
        }
    }
    Root[0]->color = 'B';
}

void redBlackInsert(Node **Root, int data) {
    Node *New = (Node *)malloc(sizeof(Node));
    New->data = data;
    New->left = NULL;
    New->right = NULL;
    New->color = 'R';
    Node *Yp = NULL;
    Node *Xp = *Root;
    if (*Root != NULL) {
        New->color = 'B';
        *Root = New;
        return;
    }
    while (Xp != NULL) {
        Yp = Xp;
        if (data < Xp->data)
            Xp = Xp->left;
        Xp = Xp->right;
    }
    New->parent = Yp;
    if (Yp == NULL) {
        *Root = New;
        if (data < Yp->data)
            Yp->left = New;
        else
            Yp->right = New;
    }
    New->left = NULL;
    New->right = NULL;
    New->color = 'R';
    redBlackInsertFixup(Root, New);
}

void redBlackTreePrint(Node *Root) {
    Node* temp = Root;
    if (temp != NULL) {
        redBlackTreePrint(temp->left);
        printf(" %d - %c,", temp->data, temp->color == 'B' ? 'B' : 'R');
        redBlackTreePrint(temp->right);
    }
    return;
}

int main(int argc, char *argv[]) {
    redBlackInsert(Root, 7);
    redBlackInsert(Root, 9);
    redBlackTreePrint(*Root);

    return 0;
}

谢谢!

最佳答案

用 -g 标志编译它，并用 gdb 运行，你会发现它在第 120 行的 redBlackInsert 处陷入困境，因为 *Root 是 NULL。

scott > gcc -O0 -g redblack.c -o redblack
scott > redblack
Segmentation fault (core dumped)
scott > gdb redblack
(gdb) run
Starting program: /home/scott/stackOverflow/redblack/redblack
Program received signal SIGSEGV, Segmentation fault.
0x000000000040098c in redBlackInsert (Root=0x0, data=7) at redblack.c:120
120     Node* Xp = *Root;
(gdb) bt
#0  0x000000000040098c in redBlackInsert (Root=0x0, data=7) at redblack.c:120
#1  0x0000000000400af5 in main (argc=1, argv=0x7fffffffded8) at redblack.c:164
(gdb)

我将全局根修改为“Node *Root”而不是“**Root”，因为这更直观。它在 main() 中的三个用途必须修改以匹配:

 int main(int argc, char* argv[])
 {
     redBlackInsert(&Root, 7);
     redBlackInsert(&Root, 9);
     redBlackTreePrint(Root);
     return 0;
 }

在 138 上，检查是否 yp==NULL，然后取消引用它，这会导致 139 上的段错误:

(gdb) run
Starting program: /home/scott/stackOverflow/redblack/redblack

Program received signal SIGSEGV, Segmentation fault.
0x0000000000400a0f in redBlackInsert (Root=0x601050 <Root>, data=7) at redblack.c:139
139         if(data < Yp->data)
(gdb) bt
#0  0x0000000000400a0f in redBlackInsert (Root=0x601050 <Root>, data=7) at redblack.c:139
#1  0x0000000000400af2 in main (argc=1, argv=0x7fffffffded8) at redblack.c:165
(gdb)

抱歉，就我所知。

关于c - 尝试在 C 中实现红黑树，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/42800462/