C++ 红黑树：从规则到实现，手把手带你写一棵红黑树

红黑树是二叉搜索树家族中重要的一员在 C STL 的map和set底层、Linux 内核的调度器、Java 的TreeMap等地方都能看到它的身影。它通过一套精妙的颜色规则在频繁的插入删除中维持着近似平衡既保证了O(log N)的时间复杂度又比 AVL 树拥有更少的旋转次数。一、什么是红黑树红黑树本质上是一棵二叉搜索树但它的每个结点都增加了一个颜色属性只能是红色或黑色。通过下面四条严格的规则红黑树能够保证没有任何一条从根到叶子的路径会比其他路径长出 2 倍从而实现近似平衡。1.1 红黑树的四条铁律结点非红即黑— 每个结点的颜色要么是红色要么是黑色。根结点必为黑色— 树的根结点始终是黑色的。不连续红色— 如果一个结点是红色的那么它的两个孩子都必须是黑色的。也就是说任意一条从根到叶子的路径上不会出现连续的两个红色结点。黑高相同— 对于任意一个结点从它到其所有后代叶子结点NIL 或 NULL 结点的简单路径上黑色结点的数量必须相同。补充在一些经典教材如《算法导论》中会把叶子结点NIL也视为外部结点并强制为黑色这主要是为了让“路径”的定义更加一致。在实际编码中我们通常用 NULL 作为结束标志并假设它也符合黑色规则不影响平衡的判断。1.2 为什么最长路径不会超过最短路径的 2 倍这是红黑树最核心的平衡保证。我们可以从下图中的极端情况来理解根据规则 4每条路径上的黑色结点数量相同记作bhblack height。根据规则 2 和规则 3红色结点不能连续出现因此路径中最多的红色结点就是和黑色结点交替排列即最长路径由“黑—红—黑—红……”组成长度最多为2 * bh。最短路径则全是黑色结点长度为bh。因此任意一条路径长度h满足bh h 2 * bh。这就保证了整棵树的高度始终被控制在对数级别从而保证了增删查改的时间复杂度都是O(log N)。1.3 红黑树 vs AVL 树AVL 树通过记录每个结点的平衡因子左右子树高度差不超过 1来严格控制平衡因此查询性能非常极致但插入和删除时可能需要更多的旋转来恢复平衡。红黑树的设计更“宽容”一些它不追求绝对平衡而是保证最长路径不超过最短路径的 2 倍。这使得红黑树在插入相同数量结点时旋转次数通常比 AVL 树少也因此更适合插入、删除操作非常频繁的场景。二、红黑树的结构定义在代码实现中我们采用 key-value 结构的泛型模板同时为每个结点增加颜色枚举以及指向父亲的_parent指针方便后续调整。// 颜色枚举 enum Colour { RED, BLACK }; // 红黑树结点 templateclass K, class V struct RBTreeNode { pairK, V _kv; RBTreeNodeK, V* _left; RBTreeNodeK, V* _right; RBTreeNodeK, V* _parent; Colour _col; RBTreeNode(const pairK, V kv) : _kv(kv), _left(nullptr), _right(nullptr), _parent(nullptr), _col(RED) { } }; // 红黑树类 templateclass K, class V class RBTree { typedef RBTreeNodeK, V Node; public: // 插入、查找、验证等接口 bool Insert(const pairK, V kv); Node* Find(const K key); bool IsBalance(); private: Node* _root nullptr; // 旋转函数与 AVL 树相同只是不更新平衡因子 void RotateL(Node* parent); void RotateR(Node* parent); // 验证辅助函数 bool Check(Node* root, int blackNum, const int refNum); };三、红黑树的插入 —— 核心难点插入操作可以概括为以下几步按照二叉搜索树的规则将新结点插入到正确位置。新结点默认染成红色。这是因为如果是黑色一定会破坏规则 4改变路径上的黑高维护起来代价巨大而插入红色结点只有可能破坏规则 3连续红色相对更容易修正。如果父亲结点是黑色直接结束不需要任何调整。如果父亲结点是红色违反规则 3则需要根据“叔叔结点”即父结点兄弟的颜色和状态分三种情况处理。我们约定c 当前结点curp 父结点g 祖父结点u 叔叔结点。3.1 情况一叔叔存在且为红色 —— 变色就能解决当p红、u红、g黑时我们只需将p和u染黑将g染红将当前处理结点c移动到g继续往上检查。理解p和u变黑相当于在各自子树增加一个黑色结点g变红相当于维持原路径黑高不变。但g变红后可能与更上层的红结点冲突因此需要循环向上更新。如果最后g是根我们再强行把它染回黑色。无论p位于g的左边还是右边c是p的左还是右处理方式完全一样只涉及变色不需要旋转。// 情况一叔叔存在且为红 if (uncle uncle-_col RED) { parent-_col uncle-_col BLACK; grandfather-_col RED; // 继续向上调整 cur grandfather; parent cur-_parent; }3.2 情况二 情况三叔叔不存在或为黑色 —— 旋转变色若u不存在或颜色为黑单纯的变色已经无法解决连续红色问题这时候必须借助旋转。根据p和c的相对位置又细分为单旋和双旋两种3.2.1 单旋场景直线型p是g的左孩子c是p的左孩子→ 对g进行右单旋p是g的右孩子c是p的右孩子→ 对g进行左单旋旋转完毕后将p染黑、g染红。此时p成为新子树的根整体黑高不变且解决了连续红色问题不需要再向上迭代。// 情况二单旋p 为 g 的左c 为 p 的左 if (cur parent-_left) { RotateR(grandfather); parent-_col BLACK; grandfather-_col RED; } // p 为 g 的右c 为 p 的右 if (cur parent-_right) { RotateL(grandfather); parent-_col BLACK; grandfather-_col RED; }3.2.2 双旋场景折线型p是g的左孩子c是p的右孩子→ 先对p左单旋再对g右单旋p是g的右孩子c是p的左孩子→ 先对p右单旋再对g左单旋旋转后将c染黑、g染红。此时c变成了新子树的根同样黑高不变且不需要继续向上调整。// 情况三双旋p 为 g 的左c 为 p 的右 else { RotateL(parent); RotateR(grandfather); cur-_col BLACK; grandfather-_col RED; } // p 为 g 的右c 为 p 的左 else { RotateR(parent); RotateL(grandfather); cur-_col BLACK; grandfather-_col RED; }3.3 插入操作完整代码结合以上所有情况插入函数的伪代码框架如下bool Insert(const pairK, V kv) { // 1. 空树新建黑结点作为根 if (_root nullptr) { _root new Node(kv); _root-_col BLACK; return true; } // 2. 二叉搜索树查找插入位置 Node* parent nullptr; Node* cur _root; while (cur) { parent cur; if (kv.first cur-_kv.first) cur cur-_left; else if (kv.first cur-_kv.first) cur cur-_right; else return false; // 已存在 } // 3. 新建红色结点挂在父结点下 cur new Node(kv); cur-_col RED; if (kv.first parent-_kv.first) parent-_left cur; else parent-_right cur; cur-_parent parent; // 4. 调整红黑树 while (parent parent-_col RED) { Node* grandfather parent-_parent; if (parent grandfather-_left) { Node* uncle grandfather-_right; // 情况一叔叔红 - 变色 if (uncle uncle-_col RED) { parent-_col uncle-_col BLACK; grandfather-_col RED; cur grandfather; parent cur-_parent; } else { // 叔叔黑或不存在 if (cur parent-_left) { // 单旋右 RotateR(grandfather); parent-_col BLACK; grandfather-_col RED; } else { // 双旋左右 RotateL(parent); RotateR(grandfather); cur-_col BLACK; grandfather-_col RED; } break; // 旋转后结构稳定可退出 } } else { // 对称情况parent 是祖父的右孩子 Node* uncle grandfather-_left; if (uncle uncle-_col RED) { parent-_col uncle-_col BLACK; grandfather-_col RED; cur grandfather; parent cur-_parent; } else { if (cur parent-_right) { RotateL(grandfather); parent-_col BLACK; grandfather-_col RED; } else { RotateR(parent); RotateL(grandfather); cur-_col BLACK; grandfather-_col RED; } break; } } } // 5. 强制根为黑 _root-_col BLACK; return true; }旋转函数与 AVL 树完全一致只需要改变指针指向即可这里不再赘述。3.4 为什么“旋转变色”后就可以直接退出因为经过单旋或双旋后新的子树根结点被染黑的那个代替了原来的g它的颜色一定是黑色。这样一来新根与上层的颜色连接断然不会再出现“连续红色”整棵树的平衡已经恢复所以可以break不再继续向上调整。四、红黑树的查找查找操作完全沿用二叉搜索树的特性复杂度O(log N)。Node* Find(const K key) { Node* cur _root; while (cur) { if (key cur-_kv.first) cur cur-_left; else if (key cur-_kv.first) cur cur-_right; else return cur; } return nullptr; }五、红黑树的验证 —— 你的树真的“红黑”吗写完插入后我们需要一套可靠的验证工具而不是凭感觉判断。直接套用四条规则颜色只能为红或黑 → 枚举保证了这一点。根是黑色。不能有连续红色结点 → 可以用前序遍历检查反向检查父亲颜色更方便若当前结点为红且父亲也为红则违规。每条路径黑高相同 → 先通过最左边一条路径统计出一个参考黑高refNum然后在前序遍历每条路径时累计黑色结点数走到空时对比。bool Check(Node* root, int blackNum, const int refNum) { if (root nullptr) { // 一条路径走完比较黑高 if (blackNum ! refNum) { cout 存在黑色结点数量不相等的路径 endl; return false; } return true; } // 检查连续红色 if (root-_col RED root-_parent-_col RED) { cout root-_kv.first 存在连续红色结点 endl; return false; } if (root-_col BLACK) blackNum; return Check(root-_left, blackNum, refNum) Check(root-_right, blackNum, refNum); } bool IsBalance() { if (_root nullptr) return true; if (_root-_col RED) return false; // 根非黑 // 计算最左路径的黑高作为参考 int refNum 0; Node* cur _root; while (cur) { if (cur-_col BLACK) refNum; cur cur-_left; } return Check(_root, 0, refNum); }只要IsBalance()返回true就意味着我们的红黑树完全遵守了所有规则平衡性自然就得到了保证。六、红黑树的删除了解红黑树的删除比插入更加复杂涉及更多颜色的互换、兄弟结点的多重判断以及可能的二次调整。本文暂不作深入展开感兴趣的同学可以阅读《算法导论》或《STL 源码剖析》中的相关章节。七、总结红黑树通过简单的颜色规则以“不连续红”“黑高相等”为约束保证树的高度始终在log N2log N之间从而获得稳定的O(log N)增删查改性能。它的实现核心在插入调整叔叔红色只变色向上迭代叔叔黑色/不存在 直线单旋 变色调整结束叔叔黑色/不存在 折线双旋 变色调整结束。与 AVL 树相比红黑树的平衡条件更宽松旋转次数更少特别适合写多读多或频繁插入删除的场景。掌握红黑树不仅加深了对自平衡搜索树的理解更是窥见了许多工业级数据结构的底层设计哲学。如果你觉得这篇文章对你有帮助欢迎点赞、收藏也欢迎在评论区交流你的理解与困惑我们一起进步