C语言实现红黑树插入搜索计时功能触发Segmentation fault求助

核心问题列表 #

• 哨兵节点实现错误
  你每次调用TNIL()都会动态分配新的内存节点，红黑树的哨兵节点要求全局共用同一个实例，所有节点 == t_nil的判断才会生效，你当前的实现中所有哨兵判断逻辑完全失效。
• 根节点修改无法回传
  旋转、插入等操作中你通过值传递struct rbtNode* root，函数内对root的修改仅作用于局部变量，外部的根指针不会被更新，树结构会被直接破坏。
• 搜索函数逻辑错误
  当前RBTreeSearch实现中无论查找值和当前节点的大小关系，都会递归遍历左右两棵子树，完全不符合二叉搜索树的查找逻辑，不仅效率极低，还会引发栈溢出风险，同时每次调用还会生成新的TNIL节点造成严重内存泄漏。
• 随机数种子设置错误
  SingleExperimentRBT中每次循环都调用srand(0)，导致每次实验生成的随机序列完全一致，测试结果没有任何参考价值。
• 计时单位错误
  clock()返回值是CPU时钟周期数，需要除以CLOCKS_PER_SEC才能转换为秒单位，你当前的计算结果单位完全错误。
• 未定义行为
  TNIL()函数中temp->key;是无意义的表达式，没有赋值属于未定义行为，可能引发不可预知的错误。

修复建议 #

1. 全局共用同一个TNIL实例，避免重复分配：

// 全局定义唯一哨兵节点
static rbtNode* t_nil = NULL;
void init_TNIL() {
    if (t_nil == NULL) {
        t_nil = (rbtNode*)malloc(sizeof(rbtNode));
        t_nil->key = 0;
        t_nil->color = 'B';
        t_nil->leftChild = t_nil;
        t_nil->rightChild = t_nil;
        t_nil->parent = t_nil;
    }
}

所有用到TNIL的地方直接使用这个全局实例即可，不要重复调用分配函数。
2. 修改根节点传递方式：改用二级指针或者你已经定义但未使用的struct tree封装根节点：

// 示例：修改插入函数为二级指针传参，保证根节点修改可回传
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;
    }
    // 后续插入逻辑不变
}

3. 修正搜索函数逻辑，符合二叉搜索树的查找规则：

rbtNode* RBTreeSearch(struct rbtNode* root, int k){
    if(root == t_nil || root->key == k){
        return root;
    }
    if(k < root->key){
        return RBTreeSearch(root->leftChild, k);
    } else {
        return RBTreeSearch(root->rightChild, k);
    }
}

4. 修正计时计算逻辑，转换为标准秒单位：

double t_elapsed = (double)(end_t - start_t) / CLOCKS_PER_SEC;

5. 移除SingleExperimentRBT循环内的srand(0)调用，仅在程序初始化阶段设置一次随机种子即可。

内容的提问来源于stack exchange，提问作者Topo1717