C++ 14 红黑树：高效平衡的奥秘

Ne0inhk

15 Mar 2026 — 12 min read

红黑树的概念

红⿊树是⼀棵⼆叉搜索树，他的每个结点增加⼀个存储位来表⽰结点的颜⾊，可以是红⾊或者⿊⾊。通过对任何⼀条从根到叶⼦的路径上各个结点的颜⾊进⾏约束，红⿊树确保没有⼀条路径会⽐其他路径⻓出2倍，因⽽是接近平衡的。

规则

1. 每个结点不是红⾊就是⿊⾊2. 根结点是⿊⾊的3. 如果⼀个结点是红⾊的，则它的两个孩⼦结点必须是⿊⾊的，也就是说任意⼀条路径不会有连续的红⾊结点。4. 对于任意⼀个结点，从该结点到其所有NULL结点的简单路径上，均包含相同数量的⿊⾊结点

为上面的红黑树,有多少条路径

答案是10条,因为要走到空才算一条

在上面的规则与图中我们发现,根节点一定为黑,那么最短路径就是全黑,最长路径就是黑红黑红相间,这就实现了最短路径与最长路径是二倍的关系

红黑树的效率

假设N是红⿊树树中结点数量，h最短路径的⻓度，那么 , 由此推出2 h − 1 <= N < 2 2∗h − 1 ,h ≈ logN 2 ∗ logN，也就是意味着红⿊树增删查改最坏也就是⾛最⻓路径，那么时间复杂度还是O(logN)红⿊树的表达相对AVL树要抽象⼀些，AVL树通过⾼度差直观的控制了平衡。红⿊树通过4条规则的颜⾊约束，间接的实现了近似平衡，他们效率都是同⼀档次，但是相对⽽⾔，插⼊相同数量的结点，红⿊树的旋转次数是更少的，因为他对平衡的控制没那么严格。

红黑树的实现

红黑树实现的大致思路与前面的AVL类似,只不过前面的bf变成了此处的color

红黑树的大致框架

 // 枚举值表⽰颜⾊ enum Colour { RED, BLACK }; // 这⾥我们默认按key/value结构实现 template<class K, class V> struct RBTreeNode { // 这⾥更新控制平衡也要加⼊parent指针 pair<K, V> _kv; RBTreeNode<K, V>* _left; RBTreeNode<K, V>* _right; RBTreeNode<K, V>* _parent; Colour _col; RBTreeNode(const pair<K, V>& kv) :_kv(kv) , _left(nullptr) , _right(nullptr) , _parent(nullptr) {} }; template<class K, class V> class RBTree { typedef RBTreeNode<K, V> Node; public: private: Node* _root = nullptr; };

红黑树插入

插入一个值大概过程

1.先按照二叉搜索树的规则,插入一个值,看看是否符合红黑树的四条规则

2.如果是空树插入,那么新增节点必须是黑色(规则要求根节点必须是黑色)

3.如果非空树插入,新增节点必须是红色(如果为黑,有很大的可能会破坏每条路径黑节点相等的规则)

如果此处父节点也为红色,那么就需要根据情况进行变色旋转这些操作了

变色/旋转

一个点记住,如果孩子与父亲节点都为红色,把父亲变为黑色(规则可得)

取45为爷爷节点,40为父亲节点,37为为孩子节点,48为叔叔节点

叔叔节点存在且为红(变色)

上面这图的每条路径,黑色节点为2,我们又要先把父亲变为黑色节点,那么父亲这条就成为了3个黑色节点,那么再把爷爷的黑色节点变为红色,父亲这条符合,但叔叔的这条的黑色节点就成为了1,最后我们再把叔叔节点变黑即可

叔叔节点不存在或者为黑(单旋+变色)

叔叔节点不存在

叔叔节点为黑

上面我们讲了,父亲一定要变为黑,所以将父亲变黑,然后再把爷爷往右旋,即可完成符合红黑树定义的树

双旋

当父亲是爷爷的左子树,而孩子却是父亲的右子树时,先把父亲变为黑色,再把孩子往左旋,确保爷孙三代在同一条直线上,最后才可对爷爷进行右旋,并将爷爷变为红色

插入完全代码

 bool Insert(const pair<K, V>& kv) { if (_root == nullptr) { _root = new Node(kv); //根节点为黑 _root->_col = BLACK; return true; } 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为空 cur = new Node(kv); cur->_col = RED; if (parent->_kv.first < kv.first) { parent->_right = cur; } else { parent->_left = cur; } // 链接父亲 cur->_parent = parent; //变色情况 //连续红色, //1.父亲为红色,连续红色(记住,父亲都要变黑) 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 = grandfather->_parent; } else { //单旋+变色(叔叔不存在或为黑,两种情况对应的cur是插入还是变色为红不一样,不过处理都一样) if (cur == parent->_left) { RotateL(grandfather); parent->_col = BLACK; grandfather->_col = RED; } //双旋 else if (cur == parent->_right) { RotateR(parent); RotateL(grandfather); parent->_col = BLACK; grandfather->_col = RED; } else break; } } else { //叔叔存在且为红 Node* uncle = grandfather->_left; if (uncle && uncle->_col == RED) { parent->_col = uncle->_col = BLACK; grandfather->_col = RED; //继续往上找 cur = grandfather; parent = grandfather->_parent; } else { //单旋+变色(叔叔不存在或为黑,两种情况对应的cur是插入还是变色为红不一样,不过处理都一样) if (cur == parent->_right) { RotateR(grandfather); parent->_col = BLACK; grandfather->_col = RED; } //双旋 孩子与父亲在与自己相对父亲的不同子树上 else if (cur == parent->_left) { RotateL(parent); RotateR(grandfather); parent->_col = BLACK; cur->_col = BLACK; grandfather->_col = RED; } else break; } } } _root->_col = BLACK; return true; }

红黑树的查找

按照前面二叉搜索树一样,时间效率为logN

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; }

红黑树的验证

验证也很简单,前面规则已经定好,每条路径的黑色节点个数相同,因此我们只需统计每条路径的黑色节点个数是否相同即可

 bool IsBalance() { if (_root == nullptr) return true; if (_root == RED) return false; //参考值 int num = 0; Node* cur = _root; while (cur) { if (cur->_col == BLACK) ++num; cur = cur->_left; } return Check(_root, 0, num); } bool Check(Node* root, int blacknum, int num) { if (root == nullptr) { //前序遍历到空,走完 if (num != blacknum) return false; return true; } // 检查孩子不太方便，因为孩子有两个，且不一定存在，反过来检查父亲就方便多了 if (root->_col == RED && root->_parent->_col == RED)//第一个判断条件root为红节点排除了root为根节点,出现父节点为空指针的情况 { cout << root->_kv.first << "存在连续的红节点" << endl; } if (root->_col == BLACK) ++blacknum; return Check(root->_left, blacknum, num) && Check(root->_left, blacknum, num); }

总结

红黑树和AVL树都是高效的平衡二叉树，增删改查的时间复杂度都是O（logN），但红黑树不追求绝对平衡，因此减少了插入和旋转的次数，在增删的结构中比AVL树性能更优。因为红黑树实现起来也比较简单，所以实际运用红黑树较多

完整代码

#pragma once #include <assert.h> #include <iostream> using namespace std; enum Colour { RED, BLACK }; template<class K, class V> struct RBTreeNode { // 这里更新控制平衡也要加入parent指针 pair<K, V> _kv; RBTreeNode<K, V>* _left; RBTreeNode<K, V>* _right; RBTreeNode<K, V>* _parent; Colour _col; RBTreeNode(const pair<K, V>& kv) :_kv(kv) , _left(nullptr) , _right(nullptr) , _parent(nullptr) {} }; template<class K,class V> class BRTree { typedef RBTreeNode<K, V> Node; public: bool Insert(const pair<K, V>& kv) { if (_root == nullptr) { _root = new Node(kv); //根节点为黑 _root->_col = BLACK; return true; } 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为空 cur = new Node(kv); cur->_col = RED; if (parent->_kv.first < kv.first) { parent->_right = cur; } else { parent->_left = cur; } // 链接父亲 cur->_parent = parent; //变色情况 //连续红色, //1.父亲为红色,连续红色(记住,父亲都要变黑) 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 = grandfather->_parent; } else { //单旋+变色(叔叔不存在或为黑,两种情况对应的cur是插入还是变色为红不一样,不过处理都一样) if (cur == parent->_left) { RotateL(grandfather); parent->_col = BLACK; grandfather->_col = RED; } //双旋 else if (cur == parent->_right) { RotateR(parent); RotateL(grandfather); parent->_col = BLACK; grandfather->_col = RED; } else break; } } else { //叔叔存在且为红 Node* uncle = grandfather->_left; if (uncle && uncle->_col == RED) { parent->_col = uncle->_col = BLACK; grandfather->_col = RED; //继续往上找 cur = grandfather; parent = grandfather->_parent; } else { //单旋+变色(叔叔不存在或为黑,两种情况对应的cur是插入还是变色为红不一样,不过处理都一样) if (cur == parent->_right) { RotateR(grandfather); parent->_col = BLACK; grandfather->_col = RED; } //双旋 else if (cur == parent->_left) { RotateL(parent); RotateR(grandfather); parent->_col = BLACK; cur->_col = BLACK; grandfather->_col = RED; } else break; } } } _root->_col = BLACK; return true; } void RotateR(Node * parent) { //已经确定好是右旋了 Node* subL = parent->_left; Node* subLR = subL->_right; //存起,防止出现下面parent为子树 Node* tmpparent = parent->_parent; parent->_parent = subL; parent->_left = subLR; subL->_right = parent; //subLR是否空 if (subLR) subLR->_parent = parent; //parent也可能为根 if (parent == _root) { _root = subL; subL->_parent = nullptr; } //parent为子树 else { //再判断parent为左子树还是右子树 if (tmpparent->_left == parent) { tmpparent->_left = subL; } else if (tmpparent->_right == parent) { tmpparent->_right = subL; } //最后链接父亲 subL->_parent = tmpparent; } } //左旋 与右旋类似 void RotateL(Node * parent) { Node* subR = parent->_right; Node* subRL = subR->_left; //存起,防止出现下面parent为子树 Node* tmpparent = parent->_parent; parent->_parent = subR; parent->_right = subRL; subR->_left = parent; //subRL是否空 if (subRL) subRL->_parent = parent; //parent也可能为根 if (parent == _root) { _root = subR; subR->_parent = nullptr; } //parent为子树 else { //再判断parent为左子树还是右子树 if (tmpparent->_left == parent) { tmpparent->_left = subR; } else if (tmpparent->_right == parent) { tmpparent->_right = subR; } //最后链接父亲 subR->_parent = tmpparent; } } void InOrder() { _InOrder(_root); cout << endl; } int Height() { return _Height(_root); } int Size() { return _Size(_root); } 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; } private: void _InOrder(Node* root) { if (root == nullptr) { return; } _InOrder(root->_left); cout << root->_kv.first << ":" << root->_kv.second << endl; _InOrder(root->_right); } bool IsBalance() { if (_root == nullptr) return true; if (_root == RED) return false; //参考值 int num = 0; Node* cur = _root; while (cur) { if (cur->_col == BLACK) ++num; cur = cur->_left; } return Check(_root, 0, num); } private: bool Check(Node* root, int blacknum, int num) { if (root == nullptr) { //前序遍历到空,走完 if (num != blacknum) return false; return true; } // 检查孩子不太方便，因为孩子有两个，且不一定存在，反过来检查父亲就方便多了 if (root->_col == RED && root->_parent->_col == RED)//第一个判断条件root为红节点排除了root为根节点,出现父节点为空指针的情况 { cout << root->_kv.first << "存在连续的红节点" << endl; } if (root->_col == BLACK) ++blacknum; return Check(root->_left, blacknum, num) && Check(root->_left, blacknum, num); } int _Height(Node* root) { if (root == nullptr) return 0; int left = _Height(root->_left); int right = _Height(root->_right); return left > right ? left + 1 : right + 1; } int _Size(Node* root) { return _Size(root->_left) + _Size(root->_right) + 1; } private: Node* _root = nullptr; };