C语言 分割错误红黑树

egdjgwm8  于 2022-12-22  发布在  其他
关注(0)|答案(1)|浏览(126)

我目前正在尝试实现一个程序,评估我的RBT(红黑树)的计算时间:

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

#define RED 'R'
#define BLACK 'B'

typedef struct rbtNode{
    int key;
    char color; //this time i also added the color since its an rbt
    struct rbtNode *leftChild;
    struct rbtNode *rightChild;
    struct rbtNode *parent;
} rbtNode;

struct rbtNode T_Nil_rbtNode; //defining the T_Nil node
rbtNode* t_nil = &T_Nil_rbtNode; //using it as the sentinel

//function for creating a new node
struct rbtNode* newNodeRBT(int key){
    rbtNode *temp =(rbtNode*)malloc(sizeof(rbtNode));
    temp->key = key;
    temp->color = 'R';
    temp->leftChild = NULL;
    temp->rightChild = NULL;
    temp->parent = NULL;

    return temp;
}

//function for performing a left side rotation
void TreeLeftRotate(struct rbtNode* root, struct rbtNode* x){
    struct rbtNode* y = x->rightChild; //y is initialize
    x->rightChild = y->leftChild; //y's left subtree are turning into x's right subtree

    if(y->leftChild != t_nil){
        y->leftChild->parent = x; //y's left subtree's parent is x
    }

    y->parent = x->parent; //y's parent is x's parent

    if(x->parent == t_nil){
        root = y;
    }else if (x->parent != t_nil && x == x->parent->leftChild){
        x->parent->leftChild = y;
    }else{
        x->parent->rightChild = y;
    }
    y->leftChild = x; //x is turning into y's left subtree
    x->parent = y; //x's parent is y
}

//function for performing a right side rotation
void TreeRightRotate(struct rbtNode* root, struct rbtNode* y){
    struct rbtNode* x = y->leftChild; //x is initialize
    y->leftChild = x->rightChild; //x's right subtree is turning into y's left subtree

    if(x->rightChild != t_nil){
        x->rightChild->parent = y; //x's right subtree's parent is y
    }

    x->parent = y->parent; //x's parent is y's parent

    if(y->parent == t_nil){
        root = x;
    }else if (y->parent != t_nil && y == y->parent->rightChild){
        y->parent->rightChild = x;
    }else{
        y->parent->leftChild = x;
    }
    x->rightChild = y; //y is turning into x's right subtree
    y->parent = x; //y's parent is x
}

//function for implementing the fixup for the left side, this function is needed for performing the insert fixup
void RBTreeInsertFixUpLeft(struct rbtNode* root, struct rbtNode* z){
    struct rbtNode* y = z->parent->parent->rightChild; //y is initialize
    if(y->color == 'R'){
        z->parent->color = 'B';
        y->color = 'B';
        z->parent->parent->color = 'R';
        z = z->parent->parent;
    }else{
        if(z == z->parent->rightChild){
            z = z->parent;
            TreeLeftRotate(root,z);
        }
        z->parent->color = 'B';
        z->parent->parent->color = 'R';
        TreeRightRotate(root,z->parent->parent);
    }
}

//function for implementing the fixup for the right side, this function is needed for performing the insert fixup
void RBTreeInsertFixUpRight(struct rbtNode* root,struct rbtNode* z){
    struct rbtNode* y = z->parent->parent->leftChild; //y is initialize
    if(y->color == 'R'){
        z->parent->color = 'B';
        y->color = 'B';
        z->parent->parent->color = 'R';
        z = z->parent->parent;
    }else{
        if(z == z->parent->leftChild){
            z = z->parent;
            TreeRightRotate(root,z);
        }
        z->parent->color = 'B';
        z->parent->parent->color = 'R';
        TreeLeftRotate(root,z->parent->parent);
    }
}

//function for performing a fixup of the RBT (necessary for pergorming an insertion)
void RBTreeInsertFixup(struct rbtNode* root, struct rbtNode* z){
    while(z->parent->color == 'R'){
        if(z->parent == z->parent->parent->leftChild){
            RBTreeInsertFixUpLeft(root,z); //calling the function for the left side
        }else{
            RBTreeInsertFixUpRight(root,z); //calling the function for the right side
        }
    }
    root->color = 'B';
}


//Function for inserting a new key in the RBT
void RBTreeInsert(struct rbtNode* root, struct rbtNode* z){
    struct rbtNode* y = t_nil;
    struct rbtNode* x = root;

    while(x != t_nil){
        y = x;
        if(z->key <x->key){
            x = x->leftChild;
        }else{
            x = x->rightChild;
        }
    }
    z->parent = y;
    if(y == t_nil){
        root = z;
    }if(y != t_nil && z->key < y->key){
        y->leftChild = z;
    }if(y != t_nil && z->key >= y->key){
        y->rightChild = z;
    }

    z->leftChild = t_nil;
    z->rightChild = t_nil;
    z->color = 'R';
    RBTreeInsertFixup(root,z);
}

//Function for searching a key in the RBT
void RBTreeSearch(struct rbtNode* root, int k){
    if(root == t_nil || root->key == k){
        return;
    }
    if(k <= root->key){
        RBTreeSearch(root->leftChild,k);
        RBTreeSearch(root->rightChild,k);
    }
}

//Function for emptying a RBT
void RBTreeDeallocate(struct rbtNode *root){
    if(root == NULL){
        return;
    }
    RBTreeDeallocate(root->leftChild);
    RBTreeDeallocate(root->rightChild);
    free(root);
}

//Function which executes the Single Experiment in regards to the RBT
double SingleExperimentRBT(int max_keys,double max_search,int max_instances){
    double t_tot = 0;
    int i;
    int key;
    double search;

    for(i= 1; i<=max_instances;i++){
        clock_t start_t, end_t;

        srand(0);
        struct rbtNode* root = newNodeRBT(rand()); //initialize the root

        start_t = clock();
        for(key = 1; key <= max_keys;key++){
            RBTreeInsert(root,newNodeRBT(rand())); //inserting the keys
        }
        for(search = 1; search <= max_search; search++){
            RBTreeSearch(root,rand()); //searching the keys
        }
        end_t = clock();
        double t_elapsed = (double)(end_t - start_t); //calculating the time elapsed
        t_tot += t_elapsed;

        RBTreeDeallocate(root); //Emptying the RBT

    }
    return t_tot/max_keys;
}

int main(void){
    int min_keys = 100000;
    int max_keys = 1000000;
    int max_instances = 5;
    int percentage_search = 60;
    int keys;
    int seed = 0;
    //setting up the main parameters for the experiments

    for(keys = min_keys; keys <= max_keys; keys += 100000){
        srand(seed);
        double max_search = (double)keys * (double)percentage_search / 100.0;
        double max_delete = keys - max_search;

        double timeRBT = SingleExperimentRBT(keys,max_search,max_instances);
        printf("Number of keys: %d -- timeRBT: %f\n",keys,timeRBT);

        seed = seed + 1;
    }
}

出于某种原因,我确实一启动就收到分段故障消息:(我的假设是,每当程序试图进入函数“SingleExperimentRBT”时就会发生。
这在哪里发生,为什么发生?

cnh2zyt3

cnh2zyt31#

问题出在RBTreeInsert函数中:特别是,在while (x != t_nil)循环中,您将x设置为leftChildrightChild,但在newNodeRBT中,这些值默认为NULL,因此循环中的if (z->key < x->key)语句可能当x为null时,(并且确实)解引用了它。我对您的代码了解不够,无法为您修复它,但是也许你想把leftChildrightChild设置为t_nil,这似乎是你在代码中使用的另一个null值?
您应该习惯于使用调试器单步调试代码;这在调试器中很容易发现,但是当你的程序崩溃时,就很难确定了。如果你在Linux或Mac上,那么看看gdb,这是一个非常强大的调试工具。网上有很多关于如何使用它的信息,如果你需要,我会添加一些链接。如果你在Windows上,那么Visual Studio包含内置的调试器。

相关问题