修复红黑树删除操作后deleteFixup阶段出现的无限循环问题

你没有实现红黑树标准实现里的哨兵NIL节点，直接用Go的nil空指针代表空节点，是导致无限循环的核心原因。

CLRS的红黑树伪代码逻辑基于统一哨兵实现：所有空叶子节点都指向同一个预定义的NIL节点，它的颜色固定为黑色，parent、left、right属性均为可访问的有效值，不会出现空指针问题。你当前的实现用nil代替哨兵，会触发以下两类问题：

1. 当待删除节点z是叶子节点（左右子节点均为空）时，x会被赋值为nil，传入deleteFixup后，循环条件x.getColor() == BLACK、分支判断x == x.getParent().leftChild()以及后续调用x.getParent()等逻辑都无法正常执行。你没有触发空指针panic反而出现无限循环，大概率是你的getColor方法对nil receiver默认返回了BLACK，导致循环条件一直成立，无法退出。
2. 你的replaceSubTree方法最后一行调用replacement.setParent(toDelete.getParent())，如果replacement是nil也会触发空指针异常。

方案1：实现统一哨兵节点（推荐，和CLRS逻辑完全对齐，改造成本最低） #

1. 定义全局唯一的哨兵节点，初始化时颜色设为BLACK，left、right、parent属性均指向自身
2. 所有原本赋值为nil的节点位置（新建节点的左右孩子、根节点的父节点等），统一替换为指向该哨兵节点
3. 代码中所有判断空节点的逻辑，从node == nil改为node == NIL

改造完成后x永远不会是nil，即使是原逻辑中的空节点，也是合法的NIL对象，可以正常调用所有节点方法，不需要修改删除、修正逻辑的主体代码。

方案2：适配nil指针逻辑（不推荐，改造成本高易出错） #

如果你不想引入哨兵结构，需要在现有逻辑中补充nil特殊处理：

1. 在Delete方法中除了记录x，还要额外记录x的父节点、以及x属于父节点的左孩子还是右孩子
2. 在deleteFixup中所有访问x属性的位置，都要先判断x是否为nil，用提前记录的父节点、左右属性代替对应方法调用
3. 在replaceSubTree方法中补充replacement为nil的判断，跳过setParent调用

你现有代码中当y.getParent() == z分支下的x.setParent(y)调用，当x为nil时也会触发空指针，引入哨兵节点后该问题会自动解决。

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