红黑树的概念
红黑树,是一种二叉搜索树,但在每个结点上增加一个存储位表示结点的颜色,可以是red或black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制,红黑树确保没有一条路径会比其他路径长出俩倍,因而是接近平衡的
概念总结:
红黑树是二叉搜索树的升级,结点里面存放的成员col标记当前结点的颜色,它的最长路径最多是最短路径的二倍,红黑树通过各个结点着色方式的限制接近平衡二叉树,但是不同于avl的是avl是一颗高度平衡的二叉树,红黑树只是接近平衡
红黑树的性质
- 每个结点不是红色就是黑色
- 根节点是黑色的
- 如果一个节点是红色的,则它的两个孩子结点是黑色的
- 对于每个结点,从该结点到其所有后代叶结点的简单路径上,均 包含相同数目的黑色结点
- 每个叶子结点都是黑色的(此处的叶子结点指的是空结点)
红黑树性质总结:
1、红黑树结点的颜色只能是红色或者黑色
2、红黑树根节点必须是黑色
3、红黑树并没有连续的红色结点
4、红黑树中从根到叶子的每一条路径都包含相同的黑色结点
5、叶子是黑色,表示空的位置
最长路径和最短路径概念:
最短路径:从根结点到叶子结点每一条路径的结点颜色都是黑色的不包含红色
最长路径:红黑交替,黑色结点和红色结点的个数相等
思考:为什么满足上面的性质,红黑树就能保证:其最长路径中节点个数不会超过最短路径节点个数的两倍?
假设结点个数为n,那么最短路径就是logn,最长路径就是2 * logn,所有并不存在最长路径超过最短路径2倍的情况
红黑树的定义与树结构
//枚举红黑颜色 enum colour { red, black, }; //定义红黑树结点结构 template<class k,class v> struct rbtreenode { //构造 rbtreenode(const pair<k, v>& kv = {0,0}) :_left(nullptr) , _right(nullptr) , _parent(nullptr) , _kv(kv) ,_col(black) { } //定义三叉链 rbtreenode<k, v>* _left; //左孩子 rbtreenode<k, v>* _right;//右孩子 rbtreenode<k, v>* _parent; //父亲 pair<k, v> _kv; //pair对象 //节点的颜色 colour _col; //定义枚举变量 }; //定义红黑树 template<class k, class v> class rbtree { typedef rbtreenode<k, v> node; public: //构造 rbtree() :_root(nullptr) {} private: node* _root; //定义树的根节点 };
插入
插入过程类似搜索树的插入,重要的是维护红黑树的性质
pair<node*, bool> insert(const pair<k, v>& kv) { if (!_root) //空树处理 { _root = new node(kv); _root->_col = black; return { _root, true }; } //二叉搜索树的插入逻辑 node* cur = _root, * 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 { cur, false }; //插入失败 } } cur = new node(kv); cur->_col = red; //新增结点颜色默认设置为red //判断插入结点是否在parent的左边或者右边 if (parent->_kv.first > kv.first) //左边 { parent->_left = cur; cur->_parent = parent; } else //右边 { parent->_right = cur; cur->_parent = parent; } /* 红黑树性质处理: 如果这棵树一开始是符合红黑树的性质,但在新增结点之后, 导致失去了红黑树的性质,这里需要控制结点的颜色和限制 每条路径上黑色结点的个数,以上情况都要处理 */ while (parent && parent->_col == red) //父亲存在且父亲为红色 { node* grandfather = parent->_parent; //祖父 //父亲出现在祖父的左边需要考虑的情况 if(parent == grandfather ->left) { //1、uncle存在,uncle为红色 /* 如果parent和uncle都存在并且都为红色这是情况一, 需要将parent和uncle的颜色变成红色,祖父颜色变成黑色 更新cur、parent、grandfather、uncle 继续向上调整 */ //2、uncle不存在 /* 这里考虑两种旋转情况,直线单旋转,折线双旋 /* cur出现在parent的左边 ,右单旋转 经过右单旋后,parent去做树的根,祖父做为右子树 //调节结点颜色 parent->_col = black; grandfather->_col = red; */ /* cur出现在parent的右边,左右双旋 经过双旋后,cur作为树的根,grandfather为右子树 调节结点颜色 cur->_col = black; grandfather->_col = red; */ */ } else //父亲出现在祖父的右边 { node* uncle = grandfather->_left; //叔叔在左子树 /* 情况一:叔叔存在,且叔叔和父亲都是红色,那么就需要将父亲 和叔叔结点的颜色变成黑色,再将祖父的颜色变成红色, 继续向上调整,更新孩子、父亲、祖父、叔叔的位置 */ /* 情况二:叔叔不存在 /* 1、新增结点出现在父亲的右边,直线情况,左单旋处理 旋转完后parent去做父亲的根,grandfather做父亲 的左子树 //调节颜色,根为黑,左右孩子为红 2、新增结点出现在父亲的左边,会出现折现的情况, 引发双旋,旋转完后,cur变成根, parent和grandfaher去做cur的左右孩子 //调节颜色,根结点为黑,左右孩子为红 */ */ } } //如果父亲不存在为了保证根结点是黑色的,这里一定得将根结点处理为黑色 _root->_col = black; }
新增结点插入后维护红黑树性质的主逻辑
//1、父亲一定存在的情况,叔叔存在/不存在 父亲叔叔结点颜色为红色 while (parent && parent->_col == red) //父亲存在且父亲为红色 { node* grandfather = parent->_parent; //祖父 //如果父亲和叔叔结点颜色都是红色 if (parent == grandfather->_left) { node* uncle = grandfather->_right; if (uncle && uncle->_col == red) //对应情况:uncle存在且为红 { //处理:父亲和叔叔变成黑色,祖父变成红色,继续向上调整 uncle->_col = parent->_col = black; grandfather->_col = red; //向上调整 cur = grandfather; //调整孩子 parent = cur->_parent;//调整父亲 } else //uncle不存在,uncle存在且为黑 { //直线情况(cur在parent的左边):只考虑单旋,以grandfather为旋转点进行右单旋转, //旋转完后将祖父的颜色变成红色,将父亲的颜色变成黑色 if (parent->_left == cur) { rotater(grandfather); parent->_col = black; grandfather->_col = red; } else //parent->_right == cur { //折线情况(cur在parent的右边):这里会引发双旋 rotatel(parent); //以parent为旋转点进行左单旋 rotater(grandfather); //以grandfather为旋转点进行右单旋转 //旋转完后cur会去做树的根,那么设置为黑色, //为了保证每条路径的黑色结点个数相同,grandfather结点颜色设置为红 cur->_col = black; grandfather->_col = red; //黑色 结点个数相同 } } } else //父亲在右子树 { node* uncle = grandfather->_left; //叔叔在左子树 if (uncle&& uncle->_col == red) //情况一处理:叔叔存在,且叔叔的颜色是红色的(包含了父亲的颜色是红色的情况) { //根据情况一处理即可:叔叔和父亲变黑, //祖父变红(目的是为了每条路径的黑色结点个数相同),继续向上 cur = grandfather; //孩子 parent = cur->_parent;//父亲 } else //叔叔不存在 { if (cur == parent->_right) //新增结点在父亲的右边,直线情况左单旋处理 { //左单旋转,以grandfather为旋转点,旋转完后parent去做新的根,grandfather去做左子树 rotatel(grandfather); //调节颜色 grandfather->_col = red; parent->_col = black; } else //新增结点在父亲的左边,折线情况,引发双旋 { //处理:以parenrt为旋转点做右单旋,再以grandfather为旋转点做左单旋 rotater(parent); //右旋 rotatel(grandfather); //左旋 parent->_col = grandfather->_col = red; cur->_col = black; } break; } } _root->_col = black; }
拆解讨论:
以下只列举parent在grandfather左边的情况,而parent在grandfather右边的情况处理方式只是反过来的,读者可以自行画图,这里仅留参考代码
node* uncle = grandfather->_right; if (uncle && uncle->_col == red) //对应情况:uncle存在且为红 { //处理:父亲和叔叔变成黑色,祖父变成红色,继续向上调整 uncle->_col = parent->_col = black; grandfather->_col = red; //向上调整 cur = grandfather; //调整孩子 parent = cur->_parent;//调整父亲 }
else //uncle不存在,uncle存在且为黑 { //直线情况(cur在parent的左边):只考虑单旋,以grandfather为旋转点进行右单旋转, //旋转完后将祖父的颜色变成红色,将父亲的颜色变成黑色 if (parent->_left == cur) { rotater(grandfather); parent->_col = black; grandfather->_col = red; } else //parent->_right == cur { //双旋转 } }
//折线情况(cur在parent的右边):这里会引发双旋 rotatel(parent); //以parent为旋转点进行左单旋 rotater(grandfather); //以grandfather为旋转点进行右单旋转 //旋转完后cur会去做树的根,那么设置为黑色, //为了保证每条路径的黑色结点个数相同,grandfather结点颜色设置为红 cur->_col = black; grandfather->_col = red;
旋转
void rotater(node* parent) //右单旋 { node* subl = parent->_left; node* sublr = subl->_right; parent->_left = sublr; if (sublr) sublr->_parent = parent; //防止sublr为nullptr subl->_right = parent; node* parent_parent = parent->_parent; //指针备份 parent->_parent = subl; if (_root == parent) //如果parent就是树的根 { _root = subl; //subl取代parent _root->_parent = nullptr; } else //如果parent并不是树的根 { if (parent_parent->_left == parent) parent->_left = subl; else parent_parent->_right = subl; subl->_parent = parent_parent; //subl去做parent_parent的孩子 } } //左单旋 void rotatel(node* parent) { node* subr = parent->_right; node* subrl = subr->_left; parent->_right = subrl; if (subrl) subrl->_parent = parent; subr->_left = parent; node* parent_parent = parent->_parent; parent->_parent = subr; if (_root == parent) { _root = subr; _root->_parent = nullptr; } else { if (parent_parent->_left == parent) parent_parent->_left = subr; else parent_parent->_right = subr; subr->_parent = parent_parent; } }
验证
/* 红黑树的几点性质在于: 1、根结点必须是红色的 2、不会出现连续的红色结点 3、所有路径的黑色结点个数是相同的 */ bool _checkblance(node* root, int isblacknum, int count) { if (!root) { if (isblacknum != count) { printf("黑色结点个数不均等n"); return false; } return true; //遍历完整棵树,如果以上列举的非法情况都不存在就返回true } //检查是否出现连续的红色结点 if (root->_col == red && root->_parent->_col == red) { printf("出现了连续的红色结点n"); return false; } //走前序遍历的过程中记录每一条路径黑色结点的个数 if (root->_col == black) count++; //递归左右子树 return _checkblance(root->_left, isblacknum, count) && _checkblance(root->_right, isblacknum, count); } //验证红黑树 bool checkblance() { if (!_root) return true; //树为null //根结点是黑色的 if (_root->_col != black) { printf("根结点不是黑色的n"); return false; } //每一条路径黑色结点的个数必须是相同的, int isblcaknum = 0; node* left = _root; while (left) { if (left->_col == black) isblcaknum++; // 统计某一条路径的所以黑色结点个数 left = left->_left; } //检查连续的红色结点,检查每一条路径的黑色结点个数是否相等 return _checkblance(_root, isblcaknum ,0); }
红黑树与avl树的比较
红黑树与avl树的比较
红黑树和avl树都是高效的平衡二叉树,增删改查的
时间复杂度都是o( log n),红黑树不追求绝对平衡,其只需保证最长路径不超过最短路径的2倍,相对而言,降低了插入和旋转的次数,所以在经常进行增删的结构中性能比avl树更优,而且红黑树实现比较简单,所以实际运用中红黑树更多。
红黑树的应用
- c++ stl库 – map/set、mutil_map/mutil_set
- java 库
- linux内核
- 其他一些库
完整代码博主已经放在git上了,读者可以参考
红黑树实现.
到此这篇关于c++详细实现红黑树流程详解的文章就介绍到这了,更多相关c++红黑树内容请搜索<计算机技术网(www.ctvol.com)!!>以前的文章或继续浏览下面的相关文章希望大家以后多多支持<计算机技术网(www.ctvol.com)!!>!
需要了解更多c/c++开发分享C++详细实现红黑树流程详解,都可以关注C/C++技术分享栏目—计算机技术网(www.ctvol.com)!
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/1237997.html