Go语言红黑树黑高度计算与插入逻辑问题排查

1. 黑高校验函数正确性 #

你写的blackHeight和IsBalanced逻辑本身是准确的：

• blackHeight递归校验左右子树黑高是否相等，不等直接返回0，相等则累加当前节点的黑色计数，完全符合红黑树黑高不变量的校验要求
• IsBalanced判断根节点的blackHeight返回值非0即合法，逻辑没问题

所以测试失败的问题不在校验函数，出在插入逻辑中。

2. 插入逻辑的Bug修复 #

2.1 旋转节点传参错误（最核心问题） #

你在insertFixup的case3分支中，旋转操作传入的节点完全错误：

• 父节点在祖父左孩子侧（side=RIGHT）的case3，应该右旋祖父节点，你当前传的是node，应该改成tree.rightRotate(node.grandparent())
• 父节点在祖父右孩子侧（side=LEFT）的case3，应该左旋祖父节点，你当前传的是node，应该改成tree.leftRotate(node.grandparent())

2.2 Case2处理后未接续Case3逻辑 #

当前代码把Case2和Case3做成了互斥分支，而Case2的作用只是把结构旋转成Case3的结构，需要继续执行Case3的变色+旋转逻辑。你需要调整分支结构：Case2处理完之后不要直接结束分支，要继续走Case3的逻辑，避免旋转后没有完成后续的变色、祖父节点旋转操作。

2.3 空节点颜色兼容 #

uncle()可能返回nil（对应红黑树的黑哨兵节点），你需要在getColor()方法中做兼容：如果调用对象是nil，直接返回BLACK，避免空指针panic。

修复后测试建议 #

可以先固定插入序列而不是用随机数，比如先插入1-7的有序序列，手动跟踪每一步的旋转和变色，确认符合红黑树规则后再换随机测试。

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