【C++】红黑树

🌈个人主页：秦jh_-CSDN博客
🔥 系列专栏：https://blog.csdn.net/qinjh_/category_12575764.html?spm=1001.2014.3001.5482

前言

红黑树的概念

红黑树的性质

节点的定义

红黑树的插入操作

检测操作：

情况一: cur为红，p为红，g为黑，u存在且为红

情况二: cur为红，p为红，g为黑，u不存在/u存在且为黑

Insert 代码

红黑树的验证

红黑树与AVL树的比较

完整代码

前言

💬 hello! 各位铁子们大家好哇。

今日更新了红黑树的相关内容
🎉 欢迎大家关注🔍点赞👍收藏⭐️留言📝

红黑树的概念

红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或 Black。通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出俩倍，因而是接近平衡的。

红黑树的性质

每个结点不是红色就是黑色
根节点是黑色的
如果一个节点是红色的，则它的两个孩子结点是黑色的。(不存在连续的红节点)
对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点(每条路径都存在相同数量的黑色节点)
每个叶子结点都是黑色的(此处的叶子结点指的是空结点)

注意：这里的叶子节点指的是空节点，也就是上图中的NIL节点。NIL节点也方便我们数路径，有几个NIL节点，就有几条路径。

最长路径<=最短路径*2 （最长路径就是一红一黑间隔，最短路径就是全黑）

节点的定义

红黑树的插入操作

红黑树是在二叉搜索树的基础上加上其平衡限制条件，因此红黑树的插入可分为两步：

按照二叉搜索的树规则插入新节点
检测新节点插入后，红黑树的性质是否造到破坏

新节点的默认颜色是红色，因此：如果其父亲节点的颜色是黑色，没有违反红黑树任何性质，则不需要调整；但当新插入节点的父亲节点颜色为红色时，就违反了性质三不能有连在一起的红色节点，此时需要对红黑树分情况来讨论。

检测操作：

约定:cur为当前节点，p为父节点，g为祖父节点，u为叔叔节点

情况一: cur为红，p为红，g为黑，u存在且为红

上图是抽象图，a/b/c/d/e代表每条路径有x个黑色节点的红黑子树，且x>=0。

注意：这里所看到的树，可能是一棵完整的树，也可能是一棵子树。

假设此时x==0，cur就是新增节点。

解决方式：将p,u改为黑，g改为红，然后把g当成cur，继续向上调整。

如果g是根节点，调整完成后，将g改成黑色。

如果g是子树，g一定有父亲，如果父亲是红色，就继续往上调整，如果父亲是黑，就结束。

如果x==1，c/d/e就是m/n/p/q四种组合之一。此时新增节点的位置就是a和b的孩子之一。

方法跟上面x==0的情况一样。

情况二: cur为红，p为红，g为黑，u不存在/u存在且为黑

说明：u的情况有两种：

若u不存在，则cur就是新插入节点。因为如果cur不是新插入节点，cur和p一定有一个节点是黑色的，就不满足性质4：每条路径的黑色节点个数相同。
若u存在且为黑，则 cur原来的颜色一定是黑的，现在看到是红色是因为cur子树在调整过程中将cur的颜色由黑色改成红色，如下图：

解决方式：

p为g的左孩子，cur为p的左孩子，则进行右单旋转；

相反， p为g的右孩子，cur为p的右孩子，则进行左单旋转

p、g变色--p变黑，g变红

情况二的双旋情况：

解决方法：

p为g的左孩子，cur为p的右孩子，则针对p做左单旋转；

相反， p为g的右孩子，cur为p的左孩子，则针对p做右单旋转。则转换成了情况2的单旋情况，再按照情况2单旋的方法解决。

Insert 代码

bool Insert(const pair<K, V>& kv)
{if (_root == nullptr){_root = new Node(kv);_root->_col = BLACK;  //根节点默认黑色return true;}Node* cur = _root;Node* parent = nullptr;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);cur->_col = RED;  //新增节点给红色if (parent->_kv.first > kv.first){parent->_left = cur;}else{parent->_right = cur;}cur->_parent = parent;// 检测新节点插入后，红黑树的性质是否造到破坏//父亲的颜色是黑色也结束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){//      g//   p     u// c//单旋RotateR(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{//     g//  p     u//    c//双旋RotateL(parent);RotateR(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}else{Node* uncle = grandfather->_left; //如果叔叔存在也为红->变色即可if (uncle && uncle->_col == RED) {parent->_col = uncle->_col = BLACK; grandfather->_col = RED; //继续往上处理cur = grandfather; parent = cur->_parent; }else  //叔叔不存在，或者存在且为黑{//    g//  u   p//        cif (cur == parent->_right){RotateL(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{//      g//   u      p//        cRotateR(parent);RotateL(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}}//始终保持根为黑_root->_col = BLACK;return true;
}

红黑树的验证

红黑树的检测分为两步：

检测其是否满足二叉搜索树(中序遍历是否为有序序列）
检测其是否满足红黑树的性质

	bool IsBalance(){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);}private: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->_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);}

红黑树与AVL树的比较

红黑树和AVL树都是高效的平衡二叉树，增删改查的时间复杂度都是O(logN)，红黑树不追求绝对平衡，其只需保证最长路径不超过最短路径的2倍，相对而言，降低了插入和旋转的次数，所以在经常进行增删的结构中性能比AVL树更优，而且红黑树实现比较简单，所以实际运用中红黑树更多。

完整代码

#pragma once enum Colour
{RED,BLACK
};template<class K,class V>
struct RBTreeNode
{RBTreeNode<K, V>* _left;RBTreeNode<K, V>* _right;RBTreeNode<K, V>* _parent;pair<K, V> _kv; Colour _col;RBTreeNode(const pair<K, V>& kv):_left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv), _col(RED){}
};template<class K,class V>
class RBTree
{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* cur = _root;Node* parent = nullptr;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);cur->_col = RED;  //新增节点给红色if (parent->_kv.first > kv.first){parent->_left = cur;}else{parent->_right = cur;}cur->_parent = parent;// 检测新节点插入后，红黑树的性质是否造到破坏//父亲的颜色是黑色也结束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){//      g//   p     u// c//单旋RotateR(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{//     g//  p     u//    c//双旋RotateL(parent);RotateR(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}else{Node* uncle = grandfather->_left; //如果叔叔存在也为红->变色即可if (uncle && uncle->_col == RED) {parent->_col = uncle->_col = BLACK; grandfather->_col = RED; //继续往上处理cur = grandfather; parent = cur->_parent; }else  //叔叔不存在，或者存在且为黑{//    g//  u   p//        cif (cur == parent->_right){RotateL(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{//      g//   u      p//        cRotateR(parent);RotateL(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}}//始终保持根为黑_root->_col = BLACK;return true;}void RotateR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;if (subLR) //节点可能为空subLR->_parent = parent;subL->_right = parent; //旧父节点变成subL的右节点Node* ppNode = parent->_parent;  //该不平衡节点可能不是根节点，所以要找到它的父节点parent->_parent = subL;if (parent == _root)   //如果该节点是根节点{_root = subL;_root->_parent = nullptr;}else  //不平衡节点只是一棵子树{if (ppNode->_left == parent)  //如果旧父节点等于爷爷节点的左节点，新父节点为爷爷节点的左节点{ppNode->_left = subL;}else{ppNode->_right = subL;}subL->_parent = ppNode;	//新父节点指向爷爷节点。}}void RotateL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;if (subRL)subRL->_parent = parent;subR->_left = parent;Node* ppNode = parent->_parent;parent->_parent = subR;if (parent == _root){_root = subR;_root->_parent = nullptr;}else{if (ppNode->_right == parent){ppNode->_right = subR;}else{ppNode->_left = subR;}subR->_parent = ppNode;}}void InOrder(){_InOrder(_root);cout << endl;}bool IsBalance(){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);}private: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->_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);}void _InOrder(Node* root){if (root == nullptr)return;_InOrder(root->_left);cout << root->_kv.first << ":" << root->_kv.second << endl;_InOrder(root->_right);}private:Node* _root = nullptr;size_t _size = 0;
};void RBTreeTest1()
{//int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14,8, 3, 1, 10, 6, 4, 7, 14, 13 };RBTree<int, int> t1;for (auto e : a){t1.Insert({ e,e });//cout << "Insert:" << e << "->" << t1.IsBalance() << endl;}t1.InOrder();cout << t1.IsBalance() << endl; 
}

【C++】红黑树

前言

红黑树的概念

红黑树的性质

节点的定义

红黑树的插入操作

检测操作：

情况一: cur为红，p为红，g为黑，u存在且为红

情况二: cur为红，p为红，g为黑，u不存在/u存在且为黑

Insert 代码

红黑树的验证

红黑树与AVL树的比较

完整代码

最新新闻

热搜词