企业官网建设流程全解析

1 红黑树的概念

红黑树是一棵二叉搜索树，每个节点额外存储颜色标识，颜色分为红色、黑色两种。

红黑树通过约束根到叶子路径上的节点颜色，保证任意一条路径的长度不会超过其他路径的2倍，属于近似平衡二叉树。

1.1 红黑树五大规则

1. 每个节点的颜色只能是红色或黑色。
2. 根节点必须为黑色。
3. 若一个节点为红色，则其两个子节点都必须是黑色（路径中不存在连续红色节点）。
4. 对于任意节点，从该节点出发到所有空（NIL）节点的每条路径，包含的黑色节点数量相同。
5. 所有空节点（NIL/外部节点）均为黑色。

补充说明：此处的叶子特指空NIL节点（外部节点），并非传统意义上的实际叶子节点；部分代码实现中会省略对NIL节点的显性处理，了解概念即可。

这里给几个红黑树图例帮助理解：

1.2 最长路径不超过最短路径 2 倍

红黑树依靠自身五大约束保证最长路径≤最短路径的2倍：

1. 所有根到空节点的路径黑节点数量一致（黑高bh），全黑路径即为最短路径，长度等于bh。
2. 规则禁止连续红节点，路径中红节点必须与黑节点相间排列。极限情况下每条黑节点后搭配一个红节点，最长路径长度为2bh。
3. 综上，任意路径长度介于bh与2bh之间，因此最长路径不会超过最短路径的2倍。

2. 红黑树的底层实现

2.1 初始框架

// 枚举值表示颜色enumColour{RED,BLACK};// 这里我们默认按key/value结构实现template<class K,class V>structRBTreeNode{// 这里更新控制平衡也要加入parent指针pair<K,V>_kv;RBTreeNode<K,V>*_left;RBTreeNode<K,V>*_right;RBTreeNode<K,V>*_parent;Colour _col;RBTreeNode(constpair<K,V>&kv):_kv(kv),_left(nullptr),_right(nullptr),_parent(nullptr){}};template<class K,class V>class RBTree{typedefRBTreeNode<K,V>Node;public:private:Node*_root=nullptr;};

2.2 红黑树的插入

红黑树的插入分三种情况，我们需要在每次插入式考虑红黑树的4条规则。
大概有以下内容：
1.空树插入：新增结点为黑色结点。
2.非空树插入：新增结点必须为红色结点；若插入黑色结点，会直接破坏红黑树规则 4（每条路径黑结点数量相同），该规则极难维护，因此非空插入默认染红。
3.非空树插入后：
新增结点为红色，若父结点是黑色，未违反任何红黑树规则，插入直接结束。
4.非空树插入后：
新增结点为红色，若父结点是红色，违反红黑树规则 3（红色结点不能有红色子结点，即无连续红结点）；
此时可确定固定颜色：当前结点（红）、父结点（红）、祖父结点（黑）；
最终调整方案，完全由叔叔结点（u） 的颜色决定，需分情况处理。

2.2.1 情况一：仅变色

只要叔叔节点 u 是红色，就只变色、不旋转！
这其实很好理解。
为什么这种情况只变色、不旋转？
因为：
叔叔 u 是红色 → 变色就能直接修复连续红，还能保持黑高不变。

完整逻辑链：

1. c红、p红、g黑、u红
   出现了连续红（c-p），违反规则。

2. p 和 u 都是红色、且都是 g 的孩子
   把p、u 同时变黑
   → 两条子树的黑高各 +1

3. 为了保持整棵树黑高不变
   把g 变红
   → g 所在路径黑高 -1
   → 整体黑高恢复平衡

4. 连续红消失了，黑高也没变
   →完全不需要旋转！
   这里给出图例：
   
   代码实现：

if(uncle&&uncle->_col==RED)// 修改8：= RED -> == RED{parent->_col=uncle->_col=BLACK;grandfather->_col=RED;//继续往上处理cur=grandfather;parent=cur->_parent;}

2.2.2 情况二：单旋+变色

情况：叔叔 u 为黑 / 不存在；

前提条件

• 当前节点c：红色
• 父节点p：红色
• 祖父节点g：黑色
• 叔叔节点u：不存在或存在且为黑色

关键推论

1. u不存在 → c一定是新增节点
2. u存在且为黑 → c一定不是新增节点，是之前变色后向上更新上来的

核心分析

• 存在连续红色节点（c-p）违规
• 单纯变色无法修复黑高平衡
• 必须采用：旋转 + 变色组合处理

具体处理规则
1.左左情况（p是g的左孩子，c是p的左孩子）

• 操作：以g为支点执行右单旋
• 变色：p变黑，g变红
• 结果：p成为子树根节点，黑高不变，无连续红节点，无需向上更新

2. 右右情况（p是g的右孩子，c是p的右孩子）

• 操作：以g为支点执行左单旋
• 变色：p变黑，g变红
• 结果：p成为子树根节点，黑高不变，无连续红节点，无需向上更新
  给个示例：
  
  代码分享：

//在左边if(cur==parent->_left){// g// p u// cRotateR(grandfather);//将g右旋，p为父，p变黑，g变红（这里P肯定是红的,循环条件）parent->_col=BLACK;grandfather->_col=RED;}

左右旋代码后面给出。

2.2.3 双旋+变色

父子节点呈折线、叔叔节点为空或黑色时，执行双旋。

前提条件

• 当前节点c：红色
• 父节点p：红色
• 祖父节点g：黑色
• 叔叔节点u：不存在或存在且为黑色

关键推论

1. u不存在 → c 一定是新增节点
2. u存在且为黑 → c 一定不是新增节点，是子树插入后经变色向上更新而来

核心分析

• 存在c-p连续红色节点违规
• 单纯变色无法修复黑高，必须旋转+变色

1. 左右情况（p是g的左孩子，c是p的右孩子）

1. 以p为支点执行左单旋
2. 以g为支点执行右单旋
3. 变色：c变黑，g变红
4. 结果：c成为子树根，黑高不变，无连续红节点，无需向上更新

2. 右左情况（p是g的右孩子，c是p的左孩子）

1. 以p为支点执行右单旋
2. 以g为支点执行左单旋
3. 变色：c变黑，g变红
4. 结果：c成为子树根，黑高不变，无连续红节点，无需向上更新

核心：叔叔红只变色，叔叔黑/无则旋转加变色。
示例：

代码分享：

else//在右边{// g// p u// cRotateL(parent);//先左旋，再右旋，将parent右边节点与parent左旋，再一g右旋// g// c u// pRotateR(grandfather);// c// p g// ucur->_col=BLACK;grandfather->_col=RED;}

2.3 左右旋代码分享

//右旋voidRotateR(Node*parent){//subl是子节点，subl右节点放parent左边，parent的父节点换为subl,subl的右节点换为parent//如果parent为root，则subl的父节点为null,不为root就换为parent之前的父节点Node*subl=parent->_left;Node*sublR=subl->_right;parent->_left=sublR;if(sublR){sublR->_parent=parent;}Node*pParent=parent->_parent;// 修改11：保存祖父节点subl->_right=parent;parent->_parent=subl;if(parent==_root){_root=subl;subl->_parent=nullptr;}else{if(pParent->_left==parent){pParent->_left=subl;// 修改12：subL -> subl}else{pParent->_right=subl;// 修改13：subL -> subl}subl->_parent=pParent;// 修改14：subL -> subl}}//左转，和右转差不多voidRotateL(Node*parent){Node*subR=parent->_right;Node*subRL=subR->_left;parent->_right=subRL;if(subRL)subRL->_parent=parent;Node*parentParent=parent->_parent;subR->_left=parent;parent->_parent=subR;if(parentParent==nullptr){_root=subR;subR->_parent=nullptr;}else{if(parent==parentParent->_left){parentParent->_left=subR;}else{parentParent->_right=subR;}subR->_parent=parentParent;}}

3. 整体代码

#pragmaonce#include<iostream>using namespace std;// 枚举值表示颜色enumColour{RED,BLACK};// 这里我们默认按key/value结构实现template<class K,class V>structRBTreeNode{// 这里更新控制平衡也要加入parent指针pair<K,V>_kv;RBTreeNode<K,V>*_left;RBTreeNode<K,V>*_right;RBTreeNode<K,V>*_parent;Colour _col;RBTreeNode(constpair<K,V>&kv):_kv(kv),_left(nullptr),_right(nullptr),_parent(nullptr){}};template<class K,class V>class RBTree{typedefRBTreeNode<K,V>Node;public:boolInsert(constpair<K,V>&kv){//先来个根节点if(_root==nullptr){// 修改1：null -> nullptr_root=newNode(kv);//这里是指针_root->_col=BLACK;returntrue;}Node*parent=nullptr;// 修改2：NULL -> nullptrNode*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还是空，这里实例化cur=newNode(kv);cur->_col=RED;//因为之前cur是空指针，所以需要重新关联父节点if(parent->_kv.first<kv.first){// 修改3：parent->kv.first -> parent->_kv.firstparent->_right=cur;}else{parent->_left=cur;}cur->_parent=parent;// 修改4：插入后设置父节点指针//这里已经插入节点，但还需要通过旋转来维护红黑树规则while(parent&&parent->_col==RED){//定义个爷，便于找Node*grandfather=parent->_parent;// 修改5：parent->_right -> parent->_parent//parent在g左边if(parent==grandfather->_left)// 修改6：grandfather->_right -> grandfather->_left{Node*uncle=grandfather->_right;// 修改7：grandfather->_right -> grandfather->_right（保持，但上面条件改了）//叔节点在且为红，与parent节点一样if(uncle&&uncle->_col==RED)// 修改8：= RED -> == RED{parent->_col=uncle->_col=BLACK;grandfather->_col=RED;//继续往上处理cur=grandfather;parent=cur->_parent;}//uncle为空或为黑，这个时候为了维护规则//需要以g右旋，g,u,p均变色else{//在左边if(cur==parent->_left){// g// p u// cRotateR(grandfather);//将g右旋，p为父，p变黑，g变红（这里P肯定是红的,循环条件）parent->_col=BLACK;grandfather->_col=RED;}else//在右边{// g// p u// cRotateL(parent);//先左旋，再右旋，将parent右边节点与parent左旋，再一g右旋// g// c u// pRotateR(grandfather);// c// p g// ucur->_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// cif(cur==parent->_right){RotateL(grandfather);parent->_col=BLACK;grandfather->_col=RED;}else{RotateR(parent);RotateL(grandfather);cur->_col=BLACK;grandfather->_col=RED;}break;}}}_root->_col=BLACK;// 修改9：确保根节点为黑色returntrue;// 修改10：添加返回值}//右旋voidRotateR(Node*parent){//subl是子节点，subl右节点放parent左边，parent的父节点换为subl,subl的右节点换为parent//如果parent为root，则subl的父节点为null,不为root就换为parent之前的父节点Node*subl=parent->_left;Node*sublR=subl->_right;parent->_left=sublR;if(sublR){sublR->_parent=parent;}Node*pParent=parent->_parent;// 修改11：保存祖父节点subl->_right=parent;parent->_parent=subl;if(parent==_root){_root=subl;subl->_parent=nullptr;}else{if(pParent->_left==parent){pParent->_left=subl;// 修改12：subL -> subl}else{pParent->_right=subl;// 修改13：subL -> subl}subl->_parent=pParent;// 修改14：subL -> subl}}//左转，和右转差不多voidRotateL(Node*parent){Node*subR=parent->_right;Node*subRL=subR->_left;parent->_right=subRL;if(subRL)subRL->_parent=parent;Node*parentParent=parent->_parent;subR->_left=parent;parent->_parent=subR;if(parentParent==nullptr){_root=subR;subR->_parent=nullptr;}else{if(parent==parentParent->_left){parentParent->_left=subR;}else{parentParent->_right=subR;}subR->_parent=parentParent;}}void_InOrder(Node*root){if(root==nullptr){return;}_InOrder(root->_left);cout<<root->_kv.first<<" ";_InOrder(root->_right);}// 前序递归遍历boolCheck(Node*root,intblackNum,constintrefNum){if(root==nullptr){// 前序遍历走到空时，意味着一条路径走完了//cout << blackNum << endl;if(refNum!=blackNum){cout<<"存在黑色结点的数量不相等的路径"<<endl;returnfalse;}returntrue;}// 检查孩子不太方便，因为孩子有两个，且不一定存在，反过来检查父亲就方便多了if(root->_col==RED&&root->_parent&&root->_parent->_col==RED){cout<<root->_kv.first<<"存在连续的红色结点"<<endl;returnfalse;}if(root->_col==BLACK){blackNum++;}returnCheck(root->_left,blackNum,refNum)&&Check(root->_right,blackNum,refNum);}boolIsBalanceTree(){if(_root==nullptr)returntrue;if(_root->_col==RED)returnfalse;// 参考值intrefNum=0;Node*cur=_root;while(cur){if(cur->_col==BLACK){++refNum;}cur=cur->_left;}returnCheck(_root,0,refNum);}Node*getroot(){return_root;}private:Node*_root=nullptr;};