Red Black Tree节点插入覆盖旧节点问题排查求助

1. 节点内存分配与初始化检查 #

• 必须为每个新节点独立调用malloc分配内存，禁止复用同一指针或使用栈上局部变量（函数返回后栈内存会被覆盖）。
• 新节点的所有字段（key、color、left、right、parent）必须显式初始化，尤其是left和right要设为你定义的NIL哨兵节点（或NULL，保持统一），避免野指针导致的逻辑混乱。

2. 插入遍历逻辑排查 #

• 遍历寻找插入位置时，务必正确跟踪父节点：
  错误示例：遍历过程中未更新父节点指针，导致所有新节点被重复挂到同一父节点的同一侧，直接覆盖原有子节点。
  正确的遍历框架参考：

  struct Node *parent = NULL;
  struct Node *current = root;
  while (current != NIL) {
      parent = current; // 保存当前节点为父节点
      current = (new_node->key < current->key) ? current->left : current->right;
  }
  new_node->parent = parent;
  if (parent == NULL) {
      root = new_node; // 空树，设为根节点
  } else if (new_node->key < parent->key) {
      parent->left = new_node;
  } else {
      parent->right = new_node;
  }
  

• 检查是否存在错误直接将root赋值为新节点的情况，这会导致每次插入都覆盖根节点，丢弃之前的树结构。

3. NIL哨兵节点一致性检查 #

• 如果采用《算法导论》中的全局NIL哨兵节点方案，要确保所有空指针（节点的left、right、未初始化的parent）都指向该NIL，禁止混用NULL和NIL。不一致的空指针会导致遍历逻辑误判节点位置，进而覆盖已有节点。
• 确认NIL节点的color字段设为BLACK，避免修复逻辑出错。

4. 插入修复（insert_fix）逻辑排查 #

• 检查旋转（左旋、右旋）函数的指针赋值是否完整，严格对应伪代码步骤，避免遗漏父节点、子节点的指针更新，导致原有节点被从树中断开。
• 修复过程中修改节点颜色或指针时，确保没有误改父节点的left/right指针，将原有子节点覆盖为新节点。

5. 调试技巧 #

• 在插入前后打印节点地址、父节点地址及树的结构（比如中序遍历输出），直观验证新节点是否正确挂载，旧节点是否仍在树中。
• 使用GDB断点跟踪每次插入时的指针变化，重点查看父节点的left/right赋值操作是否正确。

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