企业官网建设流程全解析

🌈个人主页：@ꪔ小林Y
✨个人专栏：《C++小白闯关日记》，《C语言小白闯关日记》，《数据结构入门——从原理到实战》,《拾光Linux》，《网络安全》
🍀代码信条：每一行代码都是成长的脚印👣，每一次调试成功都是对坚持的回应

红黑树

1.红黑树定义及规则

• 定义：红黑树是一颗二叉搜索树，他的每个结点增加一个存储位来表示结点的颜色（红/黑）。通过对任何一条从根到叶子的路径上各个节点的颜色进行约束，红黑树确保没有一条路径会比其他路径长出2倍，因而接近平衡。
  

• 规则：
  （1）每个节点不是红色就是黑色
  （2）根节点是黑色（注意红黑树可以是空树）
  （3）如果一个节点是红色，则他的两个孩子节点必须是黑色，也就是说任意一条路径不会有连续的红色节点
  （4）对于任意一个节点，从该节点到其所有NULL节点的简单路径上，均包含相同数量的黑色节点
• 红黑树增删查改时间复杂度O(logN)

2.红黑树的实现

1）红黑树的基本结构

//枚举表示颜色enumColour{RED,BLACK};//key/value实现template<classK,classV>structRETreeNode{pair<K,V>_kv;RETreeNode<K,V>*_left;RETreeNode<K,V>*_right;RETreeNode<K,V>*_parent;Colour _col;RETreeNode(constpatr<K,v>&kv):_kv(kv),_left(nullptr),_right(nullptr),_parent(nullptr){}};template<classK,classV>classRBTree{typedefRBTreeNode<K,V>Node;public:private:Node*_root=nulptr;};

2）红黑树的插入

插入一个值按照二叉搜索树的规则进行插入，须符合以下规则：

1. 空树插入，新增节点为黑色；非空树插入，新增节点必须为红色。否则破坏规则4。
2. 非空树插入后，新增为红，如果父亲节点是黑色，没有违反任何规则，插入结束。
3. 非空树插入后，新增为红，如果父亲节点是红色，违反规则3，进一步分析： (假设新增节点c(cur),父亲节点p，爷爷节点g，叔叔节点u)

3.1情况一：变色
叔叔存在且为红即：c为红，p为红，u存在且为红，则将p和u变黑，g变红。把g当做新的c继续向上处理。若g就是根，则再变为黑

3.2情况二：单旋+变色
叔叔不存在或者存在且为黑：c为红，p为红，g为黑，u不存在或者存在且为黑。u不存在，则c一定是新增节点，u存在且为黑，则c一定不是新增，c之前是黑色的，是在c的子树中插入，符合情况一，变色将c从黑色变成红色，更新上来的。这里单纯的变色无法解决问题，需要变色+旋转：

• 如果p是g的左，c是p的左，那么先以g为旋转点进行右单旋，再把p变黑，g变红即可。p变成课这颗树新的根，这样子树黑色结点的数量不变，没有连续的红色结点了，且不需要往上更新，因为c的父亲是黑色还是红色或者空都不违反规则。
  
• 如果p是g的右，c是p的右，那么先以g为旋转点进行左单旋，再把p变黑，g变红即可。p变成课这颗树新的根。
  
  例：

3.3情况三：双旋+变色

• 如果p是g的左，c是p的右，那么先以p为旋转点进行左单旋，再以g为旋转点进行右单旋，再把c变黑，g变红即可。c变成课这颗树新的根。
  
• 如果p是g的右，c是p的左，那么先以p为旋转点进行右单旋，再以g为旋转点进行左单旋，再把c变黑，g变红即可。c变成课这颗树新的根。
  
  例：
  
  

红黑树插入代码实现

boolInsert(constpair<K,V>&kv){//空树插入黑色节点if(_root==nullptr){_root=newNode(kv);_root->_col=BLACK;returntrue;}Node*parent=nullptr;Node*cur=_root;while(cur){if(cur->_kv.first<kv.first){parent=cur;cur=cur->_right;}elseif(cur->_kv.first>kv.first){parent=cur;cur=cur->_left;}else{returnfalse;}}//新增红色cur=newNode(kv);cur->_col=RED;if(parent->_kv.first<kv.first){parent->_right=cur;}else{parent->_left=cur;}cur->_parent=parent;//父亲存在且为红while(parent&&parent->_col==RED){Node*grandfather=parent->_parent;if(grandfather->_left=parent){// g// p u//cNode*uncle=grandfather->_right;//情况一：叔叔存在且为红,变色即可if(uncle&&uncle->_col==RED){//变色+继续往上处理parent->_col=uncle->_col=BLACK;grandfather->_col=RED;cur=grandfather;parent=cur->_parent;}else// 叔叔不存在或者叔叔存在且为黑{// g// p u//c// 情况二：单旋+变色if(cur==parent->_left){RotateR(geandfather);parent->_col=BLACK;grandfather->_col=RED;}else{// g// p u// c//情况三：双旋+变色RotateL(parent);RotateR(grandfather);cur->_col=BLACK;grandfather->_col=RED;}break;}}else{// g// u pNode*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// c// 情况二：单旋+变色if(cur==parent->_right){RotateL(geandfather);parent->_col=BLACK;grandfather->_col=RED;}else{// g// u p// c//情况三：双旋+变色RotateR(parent);RotateL(grandfather);cur->_col=BLACK;grandfather->_col=RED;}break;}}}//不存在父亲_root->_col=BLACK;returntrue;}

🎊到这儿，本期C++——【红黑树】定义及其实现的内容就结束了。如果文中有表述不准的地方，或是你有更清晰的理解思路，强烈欢迎在评论区留言交流——技术路上多碰撞，才能更快进步

觉得内容对你有帮助的话，别忘了点赞❤️➕收藏🌟，方便后续回顾复习；想跟着一起系统学习数据结构的朋友，也可以点击关注，下一期我们会聚焦更进一步的学习。不见不散✌️