当前位置：首页 > web >正文

C++红黑树实现

web 2025/7/17 18:35:59

1.红黑树的概念

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

1.1红黑树的规则

1.每个节点不是红色就是黑色的。

2.根节点是黑色的。

3.如果一个节点是红色的，那么它的两个孩子一定是黑色的，也就是说任意一条路径不会有连续的红节点。

4.对于任意⼀个结点，从该结点到其所有NULL结点的简单路径上，均包含相同数量的⿊⾊结点

2.红黑树的实现

2.1红黑树的结构

enum colour
{RED,BLACK
};template <class K,class V>
struct RBTreeNode
{pair<K, V>_kv;RBTreeNode<K, V>* _left;RBTreeNode<K, V>* _right;RBTreeNode<K, V>* _parent;Colour _clo;RBTreeNode(const pair<K,V>kv):_left(nullptr),_right(nullptr),_parent(nullptr),_kv(kv){}
};template <class K, class V>
class RBTree
{typedef RBTreeNode<K, V> Node;
private:Node* _root=nullptr;
};

2.2红黑树的插入

1. 插⼊⼀个值按⼆叉搜索树规则进⾏插⼊，插⼊后我们只需要观察是否符合红⿊树的4条规则。
2. 如果是空树插⼊，新增结点是⿊⾊结点。如果是⾮空树插⼊，新增结点必须红⾊结点，因为⾮空树插⼊，新增⿊⾊结点就破坏了规则4，规则4是很难维护的。
3. ⾮空树插⼊后，如果⽗亲结点是⿊⾊的，则没有违反任何规则，插⼊结束
4. ⾮空树插⼊后，如果⽗亲结点是红⾊的，则违反规则3。进⼀步分析，c是红⾊，p为红，g必为⿊，这三个颜⾊都固定了，关键的变化看u的情况，需要根据u分为以下⼏种

说明：下图中假设我们把新增结点标识为c (cur)，c的⽗亲标识为p(parent)，p的⽗亲标识为

g(grandfather)，p的兄弟标识为u（uncle）

2.2.2 情况1:变色

这里的c,p,g,的颜色是固定的,因为如果p为黑则不会发生变色,g一定为黑否则走不到这一步,所以u是变量.情况1时c为红,p为红,u为红,g为黑.因为p和u都是红色的,把它们都变成黑色以后,这两条路径会增加一个黑色节点,需要把g变红,保持路径黑色节点数量一致,然后再判断g的父亲节点是否为黑色,黑色则结束,红色则继续向上变色,如果g是根节点,那么需要将g再变成黑色,因为根节点需要为黑色.

2.2.3 情况2：单旋+变⾊

c为红，p为红，g为⿊，u不存在或者u存在且为⿊，u不存在，则c⼀定是新增结点，u存在且为⿊，则 c⼀定不是新增，c之前是⿊⾊的，是在c的⼦树中插⼊，符合情况1，变⾊将c从⿊⾊变成红⾊，更新上来的。

分析：p必须变⿊，才能解决，连续红⾊结点的问题，u不存在或者是⿊⾊的，这⾥单纯的变⾊⽆法解决问题，需要旋转+变⾊。

2.2.4 情况2：双旋+变⾊

需要双旋是因为插入当前cur在的parent的相反方向,形成折线。

如果p是g的左，c是p的右，那么先以p为旋转点进⾏左单旋，再以g为旋转点进⾏右单旋，再把c变

⿊，g变红即可。c变成课这颗树新的根，这样⼦树⿊⾊结点的数量不变，没有连续的红⾊结点了，且不需要往上更新，因为c的⽗亲是⿊⾊还是红⾊或者空都不违反规则。

如果p是g的右，c是p的左，那么先以p为旋转点进⾏右单旋，再以g为旋转点进⾏左单旋，再把c变

⿊，g变红即可。c变成课这颗树新的根，这样⼦树⿊⾊结点的数量不变，没有连续的红⾊结点了，且不需要往上更新，因为c的⽗亲是⿊⾊还是红⾊或者空都不违反规则

2.2.5插入代码的实现

void RotateL(Node* parent)//左单选{Node* subR = parent->_right;Node* subRL = subR->_left;Node* Pparent = parent->_parent;parent->_right = subRL;if (subRL)subRL->_parent = parent;subR->_left = parent;parent->_parent = subR;if (Pparent == nullptr){_root = subR;subR->_parent = nullptr;}else{if (parent == Pparent->_left){Pparent->_left = subR;}else{Pparent->_right = subR;}subR->_parent = Pparent;}parent->_bf = subR->_bf = 0;}void RotateR(Node* parent)//右单旋{Node* subL = parent->_left;Node* subLR = subL->_right;Node* Pparent = parent->_parent;parent->_left = subLR;if (subLR)subLR->_parent = parent;subL->_right = parent;parent->_parent = subL;if (Pparent == nullptr){_root = subL;subL->_parent = nullptr;}else{if (parent == Pparent->_left){Pparent->_left = subL;}else{Pparent->_right = subL;}subL->_parent = Pparent;}parent->_bf = subL->_bf = 0;}bool insert(const &pair<K,V>kv){if (_root == nullptr){_root = new Node(kv);_root->_clo = BLACK;return true;}Node* cur = _root;Node* parent = nullptr;while (cur){if (cur->_kv.first < kv.first){parent = cur;cur = cur->_right;}else if (kv.first < cur->_kv.first){parent = cur;cur = cur->_left;}elsereturn false;}cur = new Node(kv);cur->_clo = RED;if (parent->_kv.first < kv.first){parent->_right = cur;}else{parent->_left = cur;}cur->_parent = parent;while (parent && parent->_clo == RED){Node* grandfather = parent->_parent;if (parent == grandfather->_left){Node* uncle = grandfather->_right;if (uncle && uncle-> _clo == RED)//情况1{uncle->_clo = parent->_clo = BLACK;if (grandfather->_parent)grandfather->_clo = RED;}else if (uncle == nullptr||(uncle && uncle->_clo == BLACK))//情况2{if (cur == parent->_left)//单旋加变色{RotateR(grandfather);parent->_clo = BLACK;grandfather->RED;}else//双旋加变色{RotateL(parent);RotateR(grandfather);cur->_clo = BLACK;grandfather->_clo = RED;}}else{assert(false);}}else{Node* uncle = grandfather->_left;if (uncle && uncle->_clo == RED)//情况1{uncle->_clo = parent->_clo = BLACK;if (grandfather->_parent)grandfather->_clo = RED;}else if (uncle == nullptr || (uncle && uncle->_clo == BLACK))//情况2{if (cur == parent->_right)//单旋加变色{RotateL(grandfather);parent->_clo = BLACK;grandfather->RED;}else//双旋加变色{RotateR(parent);RotateL(grandfather);cur->_clo = BLACK;grandfather->_clo = RED;}}else{assert(false);}}cur = grandfather;parent = grandfather->_parent;}

2.3红黑树的查找

红黑树的查找与AVL树的一致

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

2.4红黑树的验证

这⾥获取最⻓路径和最短路径，检查最⻓路径不超过最短路径的2倍是不可⾏的，因为就算满⾜这个条件，红⿊树也可能颜⾊不满⾜规则，当前暂时没出问题，后续继续插⼊还是会出问题的。所以我们还是去检查4点规则，满⾜这4点规则，⼀定能保证最⻓路径不超过最短路径的2倍。

1. 规则1枚举颜⾊类型，天然实现保证了颜⾊不是⿊⾊就是红⾊。

2. 规则2直接检查根即可

3. 规则3前序遍历检查，遇到红⾊结点查孩⼦不太⽅便，因为孩⼦有两个，且不⼀定存在，反过来检查⽗亲的颜⾊就⽅便多了。

4. 规则4前序遍历，遍历过程中⽤形参记录跟到当前结点的blackNum(⿊⾊结点数量)，前序遍历遇到⿊⾊结点就++blackNum，⾛到空就计算出了⼀条路径的⿊⾊结点数量。再任意⼀条路径⿊⾊点

数量作为参考值，依次⽐较即可

bool Check(Node* root, int blackNum, const int refNum){if (root == nullptr){// 前序遍历⾛到空时，意味着⼀条路径⾛完了//cout << blackNum << endl;if (refNum != blackNum){cout << "存在⿊⾊结点的数量不相等的路径" << endl;return false;}return true;}// 检查孩⼦不太⽅便，因为孩⼦有两个，且不⼀定存在，反过来检查⽗亲就⽅便多了if (root->_clo == RED && root->_parent->_clo == RED){cout << root->_kv.first << "存在连续的红⾊结点" << endl;return false;}if (root->_clo == BLACK){blackNum++;}return Check(root->_left, blackNum, refNum)&& Check(root->_right, blackNum, refNum);}bool IsBalance(){if (_root == nullptr)return true;if (_root->_clo == RED)return false;// 参考值int refNum = 0;Node* cur = _root;while (cur){if (cur->_clo == BLACK){++refNum;}cur = cur->_left;}return Check(_root, 0, refNum);}

2.6测试代码以及结果

RBTree<int, int> t;int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };for (auto e : a){t.insert({ e,e });}t.InOrder();if (t.IsBalance())cout << "这颗红黑树符合规则且平衡";