红黑树在python中不推荐手写，应优先使用sortedcontainers或bisect；若必须实现，需严格按4种case修复、禁止重复key时触发旋转、用哨兵nil节点并校验黑高一致性。
红黑树在Python中不推荐手写，除非明确需要教学或定制逻辑
Python标准库没有红黑树实现，dict 和 set 底层用的是哈希表+开放寻址，不是树；sortedcontainers 第三方库用的是 AVL 变种，也不是红黑树。手写红黑树容易出错，且 Python 的 GIL 和对象开销会让它比 C 实现慢一个数量级。真要有序集合，优先用 sortedlist（来自 sortedcontainers）或 bisect 维护 list。
如果必须手写，插入后需立即调用 fix_insert 修复颜色与结构
红黑树插入节点默认为红色，之后可能违反“红-红不相邻”规则。修复不是一次旋转能搞定的，必须按父节点、叔节点、祖父节点三者颜色和位置分 4 种 case 处理：
- 叔节点是红色 → 只需变色：祖父变红，父和叔变黑，祖父设为当前节点继续向上检查
- 叔节点是黑色，且插入路径是“左-左”或“右-右” → 单旋 + 变色（父变黑，祖父变红）
- 叔节点是黑色，且插入路径是“左-右”或“右-左” → 先对父节点旋转（转成前一种情况），再同上处理
漏掉任一 case 或顺序颠倒（比如先旋转再变色），都会导致树失去红黑性质。建议把 4 个 case 写成独立函数，用 if/elif 显式分支，别试图压缩逻辑。
insert 函数里必须区分“找到空位”和“键已存在”两种返回
红黑树通常不允许重复 key。插入时若遇到相同 key，常见做法是覆盖 value 并直接返回，**不触发任何旋转或变色**。否则会破坏黑高一致性和路径性质。错误做法是继续走完插入流程再覆盖，这会导致临时违反红黑规则，后续修复可能失败。
示例关键判断：
if key == node.key:
node.value = value
return # 不做任何树结构调整
调试时重点检查 get_black_height 是否全路径一致
红黑树的核心约束之一是：从任一节点到其所有叶子（NIL）的路径上，黑色节点数相同（黑高）。手写实现最容易在旋转后漏掉更新某个子树的黑高，或在变色时没同步影响父链。建议写一个递归校验函数：
def get_black_height(node):
if not node: return 1
left_h = get_black_height(node.left)
right_h = get_black_height(node.right)
if left_h != right_h: raise AssertionError("black height mismatch")
return left_h + (0 if node.color == "red" else 1)
每次插入后运行一次，比肉眼查指针更可靠。注意 NIL 节点必须统一建模为黑色哨兵节点，不能用 None 混用。
真正难的不是旋转代码，而是边界条件——比如根节点变色、插入到空树、祖父为 None 时提前退出。这些地方不打日志很难定位。
Python免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 Python 的核心概念和高级技巧！
