企业官网建设流程全解析

目录

一、红黑树的概念和性质（最长路径不超过最短路径的2倍）

二、红黑树的实现

2.1 红黑树的结构

2.2 红黑树的插入

2.2.1 大致插入

2.2.2 插入分析

1.u存在且为红

1.1 u在右子树上

1.2 u在左子树上

2.u存在且为黑

2.1 u在右子树上

2.2 u在左子树上

3.不存在

3.1 u在右子树上

3.2 u在左子树上

2.2.3 完整代码

2.3 红黑树的查询

2.4 红黑树的验证

一、红黑树的概念和性质（最长路径不超过最短路径的2倍）

概念：红黑树是⼀棵⼆叉搜索树，他的每个结点增加⼀个存储位来表示结点的颜色，可以是红色或者黑色。通过对任何⼀条从根到叶子的路径上各个结点的颜色进行约束，红黑树确保没有⼀条路径会比其他路径长出2倍，因而是接近平衡的。

性质：

关于最长路径不超过最短路径的2倍，这里主要是由红黑树中2个规则决定的，一个是所有到空结点的简单路径的黑色结点数量是相同的，还有一个是红色结点不能连续存在，这两个规则就决定了，红黑树最长路径不超过最短路径的2倍，这就是为什么能保持平衡的原因。

二、红黑树的实现

2.1 红黑树的结构

根据我们对红黑树的理解+平衡树，这里的结构主要是需要插颜色结点。

//颜色枚举 enum Color { Red, Black }; //红黑树结点 template<class K, class V> struct RBTNode { pair<K, V> _kv; Color _col = Red; RBTNode<K, V>* _parent; RBTNode<K, V>* _left; RBTNode<K, V>* _right; //初始化 RBTNode(pair<K, V> kv) :_kv(kv) , _parent(nullptr) , _left(nullptr) , _right(nullptr) { } }; //红黑树结构 template<class K, class V> class RBTree { typedef RBTNode<K, V> Node; public: //初始化 RBTree(Node* root) :_root(root) {} private: Node* _root; };

2.2 红黑树的插入

2.2.1 大致插入

因为这里我们很难控制黑色结点，所以我们这里插入红色结点会很好控制黑色结点数量，然后我们根据红色结点的规则去慢慢修改父节点/插入结点的颜色。

bool insert(const pair<K, V>& kv) { //判断根是否为空 if (_root == nullptr) { _root = new Node(kv); return true; } Node* cur = _root; Node* parent = nullptr; while (cur) { //比cur大，往右棵树走 if (cur->_kv.first < kv.first) { parent = cur; cur = cur->_right; } //比cur小，往左课树走 else if (cur->_kv.first > kv.first) { parent = cur; cur = cur->_left; } //相同 else { return false; } } //找到空位置了 Node* node = new Node(kv); //判断和父节点的大小 if (parent->_kv.first < kv.first) { parent->_right = node; } else { parent->_left = node; } //更新父节点 Node* child = node; child->_parent = parent; //更改颜色维持平衡 }

2.2.2 插入分析

这里g表示爷爷结点，u表示叔叔结点，p表示父节点，c表示插入结点/移动后的孩子结点

如果一个结点是红色的，则它的两个孩子结点必须是黑色的，也就是说任意一条路径不会有连续的
红色结点。
黑色结点难控制，插入黑色结点违反规则，取解决就很难处理每条路径黑色结点数量相同情况，所
以这里用红色结点插入较为合适，违反规则后向上进行调整黑色结点会更容易。
非空树插入后，新增结点必须红色结点，如果父亲结点是红色的，则违反性质3。进一步分析，c是
红色，p为红，g必为黑，这三个颜色都固定了，关键的变化看u的情况，需要根据u分为以下几种
情况分别处理。

1.u存在且为红

1.1 u在右子树上

u在右子树上的第一种：

对于第一种情况我们无需任何处理，因为此时满足红黑树性质。

u在右子树上的第二种：

对于第二种我们就需要对p和u的颜色修改为黑色，为了根结点到每个null结点的黑色结点相同，这里还需要把g变为红。

if (uncle && uncle->_col == Red) { parent->_col = Black; uncle->_col = Black; grandfather->_col = Red;//为了平衡根结点到null的黑色结点数量 //继续往上修改 child = parent; parent = parent->_parent; }

1.2 u在左子树上

和u在右子树上的大致逻辑是一样的，只需要改变p和u的颜色为黑，g改为红就好了。

2.u存在且为黑

2.1 u在右子树上

u在右子树上的第三种：

对于第三种情况对应的u存在且为黑情况此时g为红，不需要做任何处理，此时g为红，p和u必须为黑，c为红满足红黑树的性质。

u在右子树上的第四种：

对于第四种情况对应的u存在且为黑，g也为黑，p为红（p为黑也不用考虑，和第三种情况一样），这时候修改颜色就不行了（BH表示黑色结点的高度），这个时候就需要结合右单转来解决问题。

u在右子树上的第五种：

第五种情况也是属于第四种情况一样，不能通过直接改变颜色来解决问题，这需要通过旋转来旋平衡，这里和第四种旋转方式和改变颜色方式就不一样了，需要右左双旋，然后再把child变为黑色，把grandfather变为红色维持平衡。

//2.uncle存在且为黑 else if (uncle && uncle->_col == Black) { //右单旋 // g(黑) 右单旋 p(黑) // p(红) u(黑) -----> c(红) g(红) // c u(黑) if (parent->_left == child) { RotateR(grandfather); //变色 parent->_col = Black; grandfather->_col = Red; } //左右双旋 // g(黑) 左单旋 g(黑) 右单旋 c(黑) // p(红) u(黑) ----> c(红) u(黑) ---> p(红) g(红) // c p(红) u(黑) else { RotateL(parent); RotateR(grandfather); child->_col = Black; grandfather->_col = Red; } }

2.2 u在左子树上

u在左子树上的第三种：

u在左子树中的第三种，通过左单旋，然后改变p为黑，g为红，就能平衡了，和u在右子树是一样的（旋转方式不一样）。

u在左子树上的第四种：

不需要变化

u在左子树上的第五种：

对于这种情况就和我们在u存在且为黑的第五种情况类似，都是双旋，只不过双旋顺序不一样，这里是先右单旋，然后再左单旋，改变颜色顺序也是一样的，修改child为黑色，grandfather为红色。

//2.uncle存在且为黑 else if (uncle && uncle->_col == Black) { //左单旋 // g(黑) 左单旋+变色 p(黑) // u(黑) p(红) -----> c(红) g(红) // c u(黑) if (parent->_right == child) { RotateL(grandfather); //变色 parent->_col = Black; grandfather->_col = Red; } //右左双旋 // g(黑) 右单旋 g(黑) 左单旋+变色 c(黑) // u(黑) p(红) ----> u(黑) c(红) ---> g(红) p(红) // c p(红) u(黑) else { RotateR(parent); RotateL(grandfather); child->_col = Black; grandfather->_col = Red; } }

3.不存在

3.1 u在右子树上

6和7这些情况u不存在和u存在且为黑旋转+变色是一样的，所以这里我们可以把他们综合在一起。

3.2 u在左子树上

同理也和u存在且为黑的旋转+变色相同。

2.2.3 完整代码

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) { //比cur大，往右棵树走 if (cur->_kv.first < kv.first) { parent = cur; cur = cur->_right; } //比cur小，往左课树走 else if (cur->_kv.first > kv.first) { parent = cur; cur = cur->_left; } //相同 else { return false; } } //找到空位置了 Node* node = new Node(kv); //判断和父节点的大小 if (parent->_kv.first < kv.first) { parent->_right = node; } else { parent->_left = node; } //更新父节点 Node* child = node; child->_parent = parent; //更改颜色维持平衡 while (parent && parent->_parent && parent->_col == Red)//parent颜色为黑就不需要改变了，因为黑色可以连续，后面也有可能把parent变为红的情况，但是都是旋转，旋转后都会跳出循环（因为已经平衡了） { //判断uncle是grand的左/右结点 Node* grandfather = parent->_parent; if (grandfather->_left == parent)//说明右子树是uncle { Node* uncle = grandfather->_right; //1.uncle存在且为红 // g // p u // c if (uncle && uncle->_col == Red) { parent->_col = Black; uncle->_col = Black; grandfather->_col = Red;//为了平衡根结点到null的黑色结点数量 //继续往上修改 child = grandfather parent = child->_parent; } //2.uncle存在且为黑 else if (uncle == nullptr || uncle->_col == Black) { //右单旋 // g(黑) 右单旋+变色 p(黑) // p(红) u(黑) -----> c(红) g(红) // c u(黑) if (parent->_left == child) { RotateR(grandfather); //变色 parent->_col = Black; grandfather->_col = Red; } //左右双旋 // g(黑) 左单旋 g(黑) 右单旋+变色 c(黑) // p(红) u(黑) ----> c(红) u(黑) ---> p(红) g(红) // c p(红) u(黑) else { RotateL(parent); RotateR(grandfather); child->_col = Black; grandfather->_col = Red; } break; } } else//左子树是uncle { Node* uncle = grandfather->_left; //1.uncle存在且为红 // g // p u // c if (uncle && uncle->_col == Red) { parent->_col = Black; uncle->_col = Black; grandfather->_col = Red;//为了平衡根结点到null的黑色结点数量 //继续往上修改 child = grandfather; parent = child->_parent; } //2.uncle存在且为黑 else if (uncle == nullptr || uncle->_col == Black) { //左单旋 // g(黑) 左单旋+变色 p(黑) // u(黑) p(红) -----> c(红) g(红) // c u(黑) if (parent->_right == child) { RotateL(grandfather); //变色 parent->_col = Black; grandfather->_col = Red; } //右左双旋 // g(黑) 右单旋 g(黑) 左单旋+变色 c(黑) // u(黑) p(红) ----> u(黑) c(红) ---> g(红) p(红) // c p(红) u(黑) else { RotateR(parent); RotateL(grandfather); child->_col = Black; grandfather->_col = Red; } break; } } } _root->_col = Black; return true; } //左单旋 void RotateL(Node* parent) { Node* Rchild = parent->_right; //右孩子 Node* parentparent = parent->_parent; //父节点的父节点 Node* RchildLchild = Rchild->_left; //Rchild左孩子 //先处理parent与RchildLchild连接关系 if (RchildLchild)//可能为空，导致空指针解引用问题 RchildLchild->_parent = parent; parent->_right = RchildLchild; //处理Rchild与parent的关系 Rchild->_left = parent; parent->_parent = Rchild; //然后处理parentparent与Rchild的连接关系 //判断是否为根节点 if (parent == _root) { _root = Rchild; Rchild->_parent = nullptr;//可读性，明确为空 } else { //衔接Rchild与parentparent的关系 //判断Rchild是parentparent的左右孩子 if (parentparent->_left == parent) { parentparent->_left = Rchild; } else { parentparent->_right = Rchild; } Rchild->_parent = parentparent;//最后更新Rchild的父节点 } } //右单旋 void RotateR(Node* parent) { Node* Lchild = parent->_left; Node* LchildRchild = Lchild->_right; Node* parentparent = parent->_parent; //先连接与parent与LchildRchild的连接关系 if (LchildRchild)//可能为空，避免空指针解引用 LchildRchild->_parent = parent; parent->_left = LchildRchild; //再连接parent与Lchild的连接关系 Lchild->_right = parent; parent->_parent = Lchild; //最后连接parentparent与Lchild的关系 if (parent == _root)//为根 { _root = Lchild; Lchild->_parent = nullptr;//明确为空 } else//不为根 { //判断是parentparent的左右孩子 if (parentparent->_left == parent) { parentparent->_left = Lchild; } else { parentparent->_right = Lchild; } Lchild->_parent = parentparent; } }

2.3 红黑树的查询

查询也和AVL树一样

//查询 Node* Find(const K& key) { Node* cur = _root; while (cur) { if (cur->_kv.first > key) { cur = cur->_left; } else if (cur->_kv.first < key) { cur = cur->right; } else { return cur; } return nullptr; } }

2.4 红黑树的验证

这里我们需要验证左右到null路径的黑色结点数量相同、红色结点不能连续存在这两个难啃的规则就行了，根结点为黑，可以直接判断。

针对判断黑色结点数量是否相同，我们这里可以用递归判断结点黑色结点数量，而对于红色结点也是如此。

bool IsBalance() { if (_root == nullptr) { return true; } //判断根结点是否为黑色结点 if (_root->_col == Red) { return false; } Node* leftMost = _root; int Blacknum = 0; while (leftMost) { //统计根结点左棵树黑色结点,并以参考判断根结点到各个null空指针的简单路径相同 if (leftMost->_col == Black) { Blacknum++; } leftMost = leftMost->_left; } return Check(_root,Blacknum,0); } bool Check(Node* cur, int Blacknum, int num) { //递归结束条件 if (cur == nullptr) { if (Blacknum != num) { return false; cout << "黑色结点数量异常" << cur->_kv.first << endl; } return true; } //判断红色结点是否连续 if (cur->_col == Red && cur->_parent && cur->_parent->_col == Red) { cout << "红色结点连续" << cur->_kv.first << endl; return false; } //累加黑色结点 if (cur->_col == Black) { num++; } return Check(cur->_left, Blacknum, num) && Check(cur->_right, Blacknum, num); }