C++实现红黑树插入逻辑 _ 节点变色与旋转平衡【源码】

红黑树的插入操作，看起来步骤繁多，但核心逻辑其实可以拆解成几个清晰的问题。掌握了这些问题的答案，代码写起来就会顺畅很多。下面，我们就从最关键的修复方向讲起。

红黑树插入后为什么必须从新节点开始向上修复？

这背后的逻辑其实很直接：因为新插入的 node 默认涂红，它唯一可能违反的规则就是“不能出现连续两个红节点”。而这个冲突，只可能沿着父链向上传播——你的祖父、曾祖父是否失衡，完全取决于当前局部的结构调整。所以，从叶子节点向上修正，是唯一能覆盖所有传播路径的方式。

有些初学者容易犯的错误是试图“从根开始重平衡”，这既没有理论依据，效率也低。还有人会漏掉对 parent == nullptr 的边界判断，直接导致空指针解引用，这在调试时相当头疼。

记住几个关键点：

• 新节点初始颜色必须为 RED，否则必然破坏黑高性质。
• 修复循环的终止条件是：当前节点为根，或父节点为 BLACK。
• 若父节点为 nullptr，说明当前就是根，直接涂黑并跳出。

什么时候该左旋？什么时候该右旋？关键看叔节点颜色和插入路径

旋转不是一个独立操作，它总是嵌套在“叔节点为黑”的分支里。旋转方向由当前节点与其父节点的相对位置决定：如果 node 是 parent 的右孩子，就先左旋 parent，再把 node 指向 parent（即角色互换）；反之亦然。本质上，这是把“之字形”拉直成“直线形”，为后续的变色和单旋铺路。

这里有个常见的坑：混淆了旋转对象。记住，不是旋转祖父，而是旋转父节点。另外，在双红冲突时，必须先变色再旋转，否则颜色逻辑会彻底乱掉。

总结一下判断逻辑：

• 叔节点 uncle != nullptr && uncle->color == RED → 只变色（父/叔涂黑，祖父涂红），然后 node = grandparent 继续向上。
• 叔节点为 nullptr 或为 BLACK → 进入旋转分支。
• 若 node == parent->right && parent == grandparent->left，先左旋 parent，再把 node 设为原 parent。

rotate_left 和 rotate_right 实现中哪些指针必须提前保存？

以 rotate_left 为例：如果不提前保存 root->right（即新根），后续修改 root->right->left 时，就会丢失原左子树。旋转的本质是三节点关系的重连，任何一步覆盖都是不可逆的。

典型的错误包括：忘记更新 parent 指针（尤其是当 root 原来是某子树的左/右孩子时），或者漏掉对 root->right->left 的父指针修正。这些细微的错误往往要花很多时间用 valgrind 去排查。

必须提前保存的指针：

• new_root = root->right
• new_root->left（即原右子树的左孩子）

在 root->right = new_root->left 之后，必须补上 if (new_root->left) new_root->left->parent = root。如果 root 原有父节点，还需更新其对应子指针：if (root->parent) { if (root == root->parent->left) root->parent->left = new_root; else root->parent->right = new_root; }。

插入后根节点颜色必须强制设为 BLACK 吗？

是的，这是红黑树定义的硬性要求（性质2：根为黑）。不过，不必在每次插入后单独写一句 root->color = BLACK——只要修复循环正确退出（即 node 成为根），在循环末尾统一涂黑即可。否则，可能会覆盖掉本该保持红色的中间节点。

还有一个更隐蔽的问题：如果使用哨兵节点（NIL），必须确保所有空指针访问都路由到该哨兵，且哨兵颜色恒为 BLACK；否则 uncle->color 可能会读到随机值，导致无法预料的错误。

需要注意的边界：

• 修复循环结束时，node 必定指向某个节点（可能是原新节点，也可能是向上跳转后的祖父节点等）。
• 仅当 node == root 时才执行 node->color = BLACK，不能无条件执行。
• 哨兵节点的 parent、left、right 都应指向自身或置空，避免野指针。

实际写代码时，最容易被忽略的就是父指针的维护和哨兵的一致性。颜色错了还能调，指针断了调试起来可就费劲多了。