如何在Python中实现红黑树的自平衡逻辑_详细编写左旋右旋与变色逻辑
红黑树旋转必须同步更新节点颜色，否则立即破坏红黑性质；旋转仅改拓扑，颜色与结构共同维持约束；每次旋转需重设参与的三个节点颜色，且旋转须封装在insert_fixup/delete_fixup中按case绑定变色与旋转。
红黑树的旋转操作必须绑定节点颜色更新
单纯实现 left_rotate 或 right_rotate 而不调整颜色，会导致红黑性质立即破坏。旋转本身只改变拓扑结构，但红黑树的约束（如“红节点子节点必为黑”“每条路径黑节点数相同”）依赖颜色与结构共同维持。
实操建议：
- 每次旋转后，必须显式重设参与旋转的三个节点（原父、原子、新父）的颜色，不能假设它们保持原色
-
left_rotate中，原y（新父）继承原x（旧父）的颜色；x则强制设为RED或BLACK，取决于后续插入/删除上下文 - 旋转函数不应独立调用，而应封装在
insert_fixup或delete_fixup内部，由修复逻辑决定何时旋转+如何变色
变色不是独立步骤，而是旋转的前置或后置条件
常见错误是把“变色”写成一个单独的 recolor 函数，然后在修复逻辑里随意调用——这极易漏掉关键约束。比如插入后若叔节点为红，正确做法是先将父和叔都涂黑、祖父涂红，再以祖父为新当前节点继续向上修复；此时变色是修复分支的入口动作，不是可选优化。
实操建议：
- 变色永远和具体 case 绑定：
case 1（叔红）只变色不旋转；case 2/3（叔黑）才触发旋转+再变色 - 所有变色操作必须成对检查：改一个节点颜色前，确认它父/子/兄弟节点的颜色是否因此违反性质
- 避免直接写
node.color = BLACK，而应通过辅助函数如set_color(node, color)，便于后期加入断言或日志
Python 实现中 nil 节点必须是单例且不可变
几乎所有 Python 红黑树实现崩溃的根源，是把 None 当作 nil 节点，然后在旋转中执行 nil.parent = x —— 这会抛出 AttributeError。红黑树定义中 nil 是黑色叶子，必须支持赋值属性。
Python 3.14.3
微软官方的 Python 扩展，是 VS Code 安装量最高的扩展（209M+）。集成 IntelliSense（通过 Pylance）、调试（通过 Python Debugger）、代码检查、格式化、重构和单元测试等功能。支持 Jupyter Notebook、虚拟环境管理和多 Python 版本切换。
实操建议：
- 定义全局单例
NIL = Node(color=BLACK)，所有叶节点、空子节点均指向它 -
NIL的left/right/parent均设为自身（或NIL），避免判空分支爆炸 - 在
left_rotate中，若x.right is NIL，直接返回，不进入旋转体——否则会把NIL.parent改成非NIL，污染全局状态
insert_fixup 的 while 循环终止条件容易写错
标准写法是 while current is not root and current.parent.color == RED，但很多实现漏掉 current is not root，导致根节点被误处理（根必须为黑，且无父节点）。更隐蔽的问题是：未在循环末尾更新 current 指针，造成无限循环。
实操建议：
- 循环内每个分支（case 1/2/3）结束时，必须明确设置
current = current.parent或current = current.parent.parent，取决于是否已修复该层 - 退出循环后，**必须**执行
root.color = BLACK—— 因为插入可能把根临时涂红（case 1 向上传导），这是唯一强制重刷根颜色的地方 - 不要依赖“根节点初始化即为黑”就省略这步；修复过程可能多次触及根，且 Python 对象引用不保证初始状态全程不变
真正难的不是写出左旋右旋函数，而是让每一次颜色变更和指针重连，都刚好卡在红黑性质断裂的临界点上。稍有延迟或超前，整棵树就退化成普通二叉搜索树——而这种退化在测试用例里往往不报错，只在特定插入序列下性能骤降。