红黑树Red-Black Tree是一种自平衡的二叉搜索树在许多编程语言的底层库中都能看到它的身影比如 C STL 的std::map、std::setJava 的TreeMap、TreeSet。与 AVL 树相比红黑树对平衡的要求不那么严格但依然能保证最坏情况下的操作时间复杂度为 O(logN)O(logN)。本文将从零开始详细讲解红黑树的设计思想、规则、插入操作以及代码实现帮助读者彻底理解这一经典数据结构。一、红黑树的概念与规则红黑树本质上是一棵二叉搜索树每个结点额外存储一个颜色位红色或黑色。通过对颜色进行约束红黑树保证任何一条从根到叶子NULL的路径不会比其他路径长出两倍从而维持了近似平衡。1.1 红黑树的四条规则每个结点不是红色就是黑色。根结点是黑色的。如果一个结点是红色的则它的两个孩子结点必须是黑色的即不存在两个连续的红色结点。对于任意一个结点从该结点到其所有后代 NULL 结点的简单路径上均包含相同数量的黑色结点这条规则也称为“黑色高度一致”。注一些教材如《算法导论》会补充一条“每个叶子结点NIL都是黑色的”。这里的叶子结点指的是空结点外部结点引入 NIL 是为了统一路径的终点。在具体实现中我们通常直接用nullptr表示空只要逻辑上遵守规则即可。1.2 为什么红黑树能保证“最长路径不超过最短路径的2倍”利用规则 4每条路径上的黑色结点数相同记这个数目为bhblack height。利用规则 3红色结点不能连续所以一条路径上红色结点最多和黑色结点一样多最坏情况就是一黑一红交替。因此最短路径 全为黑色长度为bh最长路径 黑红交替长度为2*bh。于是最长路径 ≤ 2 × 最短路径。虽然实际存在的树不一定同时出现这两种极端路径但这个上界保证了红黑树的高度始终在 O(logN)O(logN) 级别。1.3 红黑树的效率设红黑树结点数为 N黑色高度为 h则有2h−1≤N≤22h−12h−1≤N≤22h−1因此 h≈logNh≈logN树的高度约为 O(logN)O(logN)。最坏情况下查找次数不超过 2logN2logN时间复杂度依然是 O(logN)O(logN)。与 AVL 树相比红黑树的旋转次数更少因为 AVL 树要求高度差严格 ≤1而红黑树只要求近似平衡所以插入和删除时平衡调整的频率较低。因此红黑树在插入删除频繁的场景下性能更优这也是 STL 选择红黑树的原因之一。二、红黑树的结点定义我们采用 key-value 模型并引入父指针方便向上调整和颜色枚举。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: // 插入、查找等接口 private: Node* _root nullptr; };三、插入操作详解插入是红黑树最复杂的操作分为几个阶段BST 插入、颜色调整、旋转。我们约定以下记号ccur当前新插入的结点pparentc的父结点ggrandfatherp的父结点uunclep的兄弟结点3.1 插入流程概览按照二叉搜索树的规则找到插入位置建立新结点并将其颜色设为红色。若插入前树为空则将根结点改为黑色满足规则 2结束。若p是黑色则插入一个红色结点不会破坏任何规则结束。若p是红色此时g必为黑色则出现连续红色结点需要根据u的情况进行变色和旋转调整。3.2 为什么新结点必须是红色如果插入黑色结点一定会破坏规则 4因为新结点所在的那条路径多了一个黑色结点其他路径没有而修复规则 4 非常麻烦。插入红色结点只可能破坏规则 3当p也是红色时而规则 3 可以通过局部变色和旋转修复代价较小。所以新结点一律红色。3.3 情况一叔叔结点存在且为红色只变色条件p为红g为黑u存在且为红。处理将p和u变为黑色g变为红色。然后以g为新的c继续向上检查因为g变红后可能与其父结点再次形成连续红色。为什么可行将p和u变黑使得这两条路径各增加一个黑色但g变红又抵消了g所在路径黑色数的变化整体黑色数量不变。连续红色结点c和p被消灭。如果g是根最后会强制变回黑色。抽象表示下图中的a/b/c/d/e表示具有相同黑色高度的子树具体形态不限只要u为红色无论c是p的左还是右处理方式都一样变色 继续向上。https://your-image-host.com/rbt_case1.png3.4 情况二叔叔结点不存在或为黑色 单旋条件p为红g为黑u不存在或为黑并且c和p在同一侧即p是g的左且c是p的左或者p是g的右且c是p的右。处理若p是g的左孩子对g进行右单旋然后p变黑g变红。若p是g的右孩子对g进行左单旋然后p变黑g变红。为什么这样可行旋转后p成为新子树的根并且是黑色其左右孩子的颜色c和g一个红一个黑不再有连续红色。子树黑色数量不变且由于新的根p是黑色不会与上层产生冲突因此调整结束。3.5 情况三叔叔结点不存在或为黑色 双旋条件p为红g为黑u不存在或为黑但c和p不在同一侧即p是g的左且c是p的右或者p是g的右且c是p的左。处理若p是g的左c是p的右先以p为轴左单旋再以g为轴右单旋最后将c变黑g变红。若p是g的右c是p的左先以p为轴右单旋再以g为轴左单旋最后将c变黑g变红。为什么双旋因为c在p的内侧单旋无法直接让p成为根所以需要两次旋转将c提升到顶部然后改变颜色。双旋后c成为新子树的根且为黑色所以不会与上层冲突调整结束。四、旋转代码实现旋转操作与 AVL 树完全一致只是不需要更新平衡因子红黑树用颜色控制。我们给出左单旋和右单旋的实现。4.1 左单旋void RotateL(Node* parent) { Node* subR parent-_right; Node* subRL subR-_left; parent-_right subRL; if (subRL) subRL-_parent parent; Node* parentParent parent-_parent; subR-_left parent; parent-_parent subR; if (parentParent nullptr) { _root subR; subR-_parent nullptr; } else { if (parent parentParent-_left) parentParent-_left subR; else parentParent-_right subR; subR-_parent parentParent; } }4.2 右单旋void RotateR(Node* parent) { Node* subL parent-_left; Node* subLR subL-_right; parent-_left subLR; if (subLR) subLR-_parent parent; Node* parentParent parent-_parent; subL-_right parent; parent-_parent subL; if (parentParent nullptr) { _root subL; subL-_parent nullptr; } else { if (parent parentParent-_left) parentParent-_left subL; else parentParent-_right subL; subL-_parent parentParent; } }五、插入的完整代码根据上述三种情况实现Insert函数bool Insert(const pairK, V kv) { // 1. 空树直接创建黑色根结点 if (_root nullptr) { _root new Node(kv); _root-_col BLACK; return true; } // 2. BST 插入寻找位置 Node* parent nullptr; Node* cur _root; while (cur) { if (cur-_kv.first kv.first) { parent cur; cur cur-_right; } else if (cur-_kv.first kv.first) { parent cur; cur cur-_left; } else { return false; // 键重复插入失败 } } cur new Node(kv); // 新结点默认红色 if (parent-_kv.first kv.first) parent-_right cur; else parent-_left cur; cur-_parent parent; // 3. 颜色调整parent 为红色时需处理 while (parent parent-_col RED) { Node* grandfather parent-_parent; // 情况 Aparent 是 grandfather 的左孩子 if (parent grandfather-_left) { Node* uncle grandfather-_right; // 情况1叔叔存在且红色 - 变色 if (uncle uncle-_col RED) { parent-_col BLACK; uncle-_col BLACK; grandfather-_col RED; // 继续向上调整 cur grandfather; parent cur-_parent; } else // 叔叔不存在或黑色 { // 情况2cur 是 parent 的左孩子 - 右单旋 if (cur parent-_left) { RotateR(grandfather); parent-_col BLACK; grandfather-_col RED; } // 情况3cur 是 parent 的右孩子 - 左右双旋 else { RotateL(parent); RotateR(grandfather); cur-_col BLACK; grandfather-_col RED; } break; // 调整结束 } } else // 情况 Bparent 是 grandfather 的右孩子对称 { Node* uncle grandfather-_left; if (uncle uncle-_col RED) { parent-_col BLACK; 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; } } } // 确保根结点为黑色可能被情况1的变色染红 _root-_col BLACK; return true; }注意旋转函数RotateL、RotateR内部已经处理了父指针和根节点更新调用时传入需要旋转的结点。六、查找与验证6.1 查找实现查找与普通 BST 相同Node* Find(const K key) { Node* cur _root; while (cur) { if (cur-_kv.first key) cur cur-_right; else if (cur-_kv.first key) cur cur-_left; else return cur; } return nullptr; }6.2 验证红黑树正确性验证一棵树是否为红黑树不能只检查“最长路径 ≤ 2×最短路径”因为这种条件满足时仍可能违反颜色规则。正确的方法是逐条检查四个规则根结点是否为黑色是否有连续的红色结点所有路径的黑色结点数是否相同验证思路先遍历最左路径计算出一条参考路径的黑色结点数refNum。再递归检查每个结点遇到红色结点时检查其父结点是否为红色遇到黑色结点时计数器加一。递归到空结点时比较当前累计的黑色结点数与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); }七、红黑树的删除简述红黑树的删除比插入更复杂但核心思想类似先按 BST 规则删除结点然后针对可能破坏的红黑树性质进行颜色调整和旋转。删除操作主要面临以下几个问题如果删除的是红色结点不影响黑色高度通常不需要调整。如果删除的是黑色结点会导致经过该结点的路径少了一个黑色需要从兄弟子树“借”一个黑色或通过旋转重新染色。具体处理分为多种情况兄弟结点为红/黑兄弟的孩子为红/黑等使用变色和双旋来恢复平衡。由于篇幅所限本文不展开删除的详细实现有兴趣的读者可以参考《算法导论》或《STL源码剖析》。八、总结红黑树是一种优雅的平衡二叉搜索树它通过颜色的约束实现了近似平衡并保证了增删查改的 O(logN)O(logN) 复杂度。相对于 AVL 树红黑树在插入和删除时的旋转次数更少因此在工程实践中应用更广泛。本文重点介绍了红黑树的核心规则、插入操作的三种调整情景以及旋转与变色的配合并给出了完整的 C 实现代码。希望读者能通过动手编码和画图模拟进一步加深对红黑树的理解。红黑树不仅是一种数据结构更是一种设计哲学的体现用简单的颜色标记和局部调整换取全局的平衡。掌握它你将能更深刻地理解 STL 容器底层的工作原理也能在需要手写平衡树时多一个可靠的选择。参考资料Cormen, T. H. et al.Introduction to Algorithms(3rd ed.). MIT Press.侯捷.STL 源码剖析. 华中科技大学出版社.本文插图参考自原教学文档。
红黑树实现详解：从原理到代码
红黑树Red-Black Tree是一种自平衡的二叉搜索树在许多编程语言的底层库中都能看到它的身影比如 C STL 的std::map、std::setJava 的TreeMap、TreeSet。与 AVL 树相比红黑树对平衡的要求不那么严格但依然能保证最坏情况下的操作时间复杂度为 O(logN)O(logN)。本文将从零开始详细讲解红黑树的设计思想、规则、插入操作以及代码实现帮助读者彻底理解这一经典数据结构。一、红黑树的概念与规则红黑树本质上是一棵二叉搜索树每个结点额外存储一个颜色位红色或黑色。通过对颜色进行约束红黑树保证任何一条从根到叶子NULL的路径不会比其他路径长出两倍从而维持了近似平衡。1.1 红黑树的四条规则每个结点不是红色就是黑色。根结点是黑色的。如果一个结点是红色的则它的两个孩子结点必须是黑色的即不存在两个连续的红色结点。对于任意一个结点从该结点到其所有后代 NULL 结点的简单路径上均包含相同数量的黑色结点这条规则也称为“黑色高度一致”。注一些教材如《算法导论》会补充一条“每个叶子结点NIL都是黑色的”。这里的叶子结点指的是空结点外部结点引入 NIL 是为了统一路径的终点。在具体实现中我们通常直接用nullptr表示空只要逻辑上遵守规则即可。1.2 为什么红黑树能保证“最长路径不超过最短路径的2倍”利用规则 4每条路径上的黑色结点数相同记这个数目为bhblack height。利用规则 3红色结点不能连续所以一条路径上红色结点最多和黑色结点一样多最坏情况就是一黑一红交替。因此最短路径 全为黑色长度为bh最长路径 黑红交替长度为2*bh。于是最长路径 ≤ 2 × 最短路径。虽然实际存在的树不一定同时出现这两种极端路径但这个上界保证了红黑树的高度始终在 O(logN)O(logN) 级别。1.3 红黑树的效率设红黑树结点数为 N黑色高度为 h则有2h−1≤N≤22h−12h−1≤N≤22h−1因此 h≈logNh≈logN树的高度约为 O(logN)O(logN)。最坏情况下查找次数不超过 2logN2logN时间复杂度依然是 O(logN)O(logN)。与 AVL 树相比红黑树的旋转次数更少因为 AVL 树要求高度差严格 ≤1而红黑树只要求近似平衡所以插入和删除时平衡调整的频率较低。因此红黑树在插入删除频繁的场景下性能更优这也是 STL 选择红黑树的原因之一。二、红黑树的结点定义我们采用 key-value 模型并引入父指针方便向上调整和颜色枚举。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: // 插入、查找等接口 private: Node* _root nullptr; };三、插入操作详解插入是红黑树最复杂的操作分为几个阶段BST 插入、颜色调整、旋转。我们约定以下记号ccur当前新插入的结点pparentc的父结点ggrandfatherp的父结点uunclep的兄弟结点3.1 插入流程概览按照二叉搜索树的规则找到插入位置建立新结点并将其颜色设为红色。若插入前树为空则将根结点改为黑色满足规则 2结束。若p是黑色则插入一个红色结点不会破坏任何规则结束。若p是红色此时g必为黑色则出现连续红色结点需要根据u的情况进行变色和旋转调整。3.2 为什么新结点必须是红色如果插入黑色结点一定会破坏规则 4因为新结点所在的那条路径多了一个黑色结点其他路径没有而修复规则 4 非常麻烦。插入红色结点只可能破坏规则 3当p也是红色时而规则 3 可以通过局部变色和旋转修复代价较小。所以新结点一律红色。3.3 情况一叔叔结点存在且为红色只变色条件p为红g为黑u存在且为红。处理将p和u变为黑色g变为红色。然后以g为新的c继续向上检查因为g变红后可能与其父结点再次形成连续红色。为什么可行将p和u变黑使得这两条路径各增加一个黑色但g变红又抵消了g所在路径黑色数的变化整体黑色数量不变。连续红色结点c和p被消灭。如果g是根最后会强制变回黑色。抽象表示下图中的a/b/c/d/e表示具有相同黑色高度的子树具体形态不限只要u为红色无论c是p的左还是右处理方式都一样变色 继续向上。https://your-image-host.com/rbt_case1.png3.4 情况二叔叔结点不存在或为黑色 单旋条件p为红g为黑u不存在或为黑并且c和p在同一侧即p是g的左且c是p的左或者p是g的右且c是p的右。处理若p是g的左孩子对g进行右单旋然后p变黑g变红。若p是g的右孩子对g进行左单旋然后p变黑g变红。为什么这样可行旋转后p成为新子树的根并且是黑色其左右孩子的颜色c和g一个红一个黑不再有连续红色。子树黑色数量不变且由于新的根p是黑色不会与上层产生冲突因此调整结束。3.5 情况三叔叔结点不存在或为黑色 双旋条件p为红g为黑u不存在或为黑但c和p不在同一侧即p是g的左且c是p的右或者p是g的右且c是p的左。处理若p是g的左c是p的右先以p为轴左单旋再以g为轴右单旋最后将c变黑g变红。若p是g的右c是p的左先以p为轴右单旋再以g为轴左单旋最后将c变黑g变红。为什么双旋因为c在p的内侧单旋无法直接让p成为根所以需要两次旋转将c提升到顶部然后改变颜色。双旋后c成为新子树的根且为黑色所以不会与上层冲突调整结束。四、旋转代码实现旋转操作与 AVL 树完全一致只是不需要更新平衡因子红黑树用颜色控制。我们给出左单旋和右单旋的实现。4.1 左单旋void RotateL(Node* parent) { Node* subR parent-_right; Node* subRL subR-_left; parent-_right subRL; if (subRL) subRL-_parent parent; Node* parentParent parent-_parent; subR-_left parent; parent-_parent subR; if (parentParent nullptr) { _root subR; subR-_parent nullptr; } else { if (parent parentParent-_left) parentParent-_left subR; else parentParent-_right subR; subR-_parent parentParent; } }4.2 右单旋void RotateR(Node* parent) { Node* subL parent-_left; Node* subLR subL-_right; parent-_left subLR; if (subLR) subLR-_parent parent; Node* parentParent parent-_parent; subL-_right parent; parent-_parent subL; if (parentParent nullptr) { _root subL; subL-_parent nullptr; } else { if (parent parentParent-_left) parentParent-_left subL; else parentParent-_right subL; subL-_parent parentParent; } }五、插入的完整代码根据上述三种情况实现Insert函数bool Insert(const pairK, V kv) { // 1. 空树直接创建黑色根结点 if (_root nullptr) { _root new Node(kv); _root-_col BLACK; return true; } // 2. BST 插入寻找位置 Node* parent nullptr; Node* cur _root; while (cur) { if (cur-_kv.first kv.first) { parent cur; cur cur-_right; } else if (cur-_kv.first kv.first) { parent cur; cur cur-_left; } else { return false; // 键重复插入失败 } } cur new Node(kv); // 新结点默认红色 if (parent-_kv.first kv.first) parent-_right cur; else parent-_left cur; cur-_parent parent; // 3. 颜色调整parent 为红色时需处理 while (parent parent-_col RED) { Node* grandfather parent-_parent; // 情况 Aparent 是 grandfather 的左孩子 if (parent grandfather-_left) { Node* uncle grandfather-_right; // 情况1叔叔存在且红色 - 变色 if (uncle uncle-_col RED) { parent-_col BLACK; uncle-_col BLACK; grandfather-_col RED; // 继续向上调整 cur grandfather; parent cur-_parent; } else // 叔叔不存在或黑色 { // 情况2cur 是 parent 的左孩子 - 右单旋 if (cur parent-_left) { RotateR(grandfather); parent-_col BLACK; grandfather-_col RED; } // 情况3cur 是 parent 的右孩子 - 左右双旋 else { RotateL(parent); RotateR(grandfather); cur-_col BLACK; grandfather-_col RED; } break; // 调整结束 } } else // 情况 Bparent 是 grandfather 的右孩子对称 { Node* uncle grandfather-_left; if (uncle uncle-_col RED) { parent-_col BLACK; 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; } } } // 确保根结点为黑色可能被情况1的变色染红 _root-_col BLACK; return true; }注意旋转函数RotateL、RotateR内部已经处理了父指针和根节点更新调用时传入需要旋转的结点。六、查找与验证6.1 查找实现查找与普通 BST 相同Node* Find(const K key) { Node* cur _root; while (cur) { if (cur-_kv.first key) cur cur-_right; else if (cur-_kv.first key) cur cur-_left; else return cur; } return nullptr; }6.2 验证红黑树正确性验证一棵树是否为红黑树不能只检查“最长路径 ≤ 2×最短路径”因为这种条件满足时仍可能违反颜色规则。正确的方法是逐条检查四个规则根结点是否为黑色是否有连续的红色结点所有路径的黑色结点数是否相同验证思路先遍历最左路径计算出一条参考路径的黑色结点数refNum。再递归检查每个结点遇到红色结点时检查其父结点是否为红色遇到黑色结点时计数器加一。递归到空结点时比较当前累计的黑色结点数与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); }七、红黑树的删除简述红黑树的删除比插入更复杂但核心思想类似先按 BST 规则删除结点然后针对可能破坏的红黑树性质进行颜色调整和旋转。删除操作主要面临以下几个问题如果删除的是红色结点不影响黑色高度通常不需要调整。如果删除的是黑色结点会导致经过该结点的路径少了一个黑色需要从兄弟子树“借”一个黑色或通过旋转重新染色。具体处理分为多种情况兄弟结点为红/黑兄弟的孩子为红/黑等使用变色和双旋来恢复平衡。由于篇幅所限本文不展开删除的详细实现有兴趣的读者可以参考《算法导论》或《STL源码剖析》。八、总结红黑树是一种优雅的平衡二叉搜索树它通过颜色的约束实现了近似平衡并保证了增删查改的 O(logN)O(logN) 复杂度。相对于 AVL 树红黑树在插入和删除时的旋转次数更少因此在工程实践中应用更广泛。本文重点介绍了红黑树的核心规则、插入操作的三种调整情景以及旋转与变色的配合并给出了完整的 C 实现代码。希望读者能通过动手编码和画图模拟进一步加深对红黑树的理解。红黑树不仅是一种数据结构更是一种设计哲学的体现用简单的颜色标记和局部调整换取全局的平衡。掌握它你将能更深刻地理解 STL 容器底层的工作原理也能在需要手写平衡树时多一个可靠的选择。参考资料Cormen, T. H. et al.Introduction to Algorithms(3rd ed.). MIT Press.侯捷.STL 源码剖析. 华中科技大学出版社.本文插图参考自原教学文档。
