C++（初階）（十九）—

紅黑樹

紅黑樹
- 概念
- 規則
- 實現
- - 結點
  - 插入
  - 變色
  - - 變色參考代碼：
  - 查找
  - - 查找參考代碼
  - 遍歷
- 紅黑樹檢查
- 完整代碼

概念

紅?樹是?棵?叉搜索樹。它的每個結點增加?個存儲位來表示結點的顏?，可以是紅色或者黑色（并不會出現第三種顏色）。

通過對結點顏色特別的規則進行約束，紅黑樹確保沒有任何?條路徑會比其他路徑長出2倍，即保證最長路徑（一黑一紅）<= 最短路徑*2（全黑），因此紅黑樹是接近平衡的。

規則

1，每個結點不是紅色就是黑色。

2，根結點是黑色的。

3，如果?個結點是紅?的，則它的兩個孩?結點必須是黑色的，也就是說任意?條路徑不會有連續的紅色結點。

4，對于任意?個結點，從該結點到其所有空結點（NULL）的簡單路徑上，均包含相同數量的黑色結點。

5，最長路徑（一黑一紅）<= 最短路徑*2（全黑）。

說明：《算法導論》等書籍上補充了?條每個葉?結點(NIL)都是黑色的規則。他這?所指的葉?結點不是傳統的意義上的葉?結點，?是我們說的空結點，有些書籍上也把NIL叫做外部結點。NIL是為了 ?便準確的標識出所有路徑，《算法導論》在后續講解實現的細節中也忽略了NIL結點，所以我們知道 ?下這個概念即可

實現

結點

// 枚舉值表?顏?
enum Colour
{RED,BLACK
};// 這?我們默認按key_value結構實現
template<class K, class V>
struct RBTreeNode
{pair<K, V> _kv;RBTreeNode<K, V>* _left;RBTreeNode<K, V>* _right;//這?更新控制平衡也要加?parent指針RBTreeNode<K, V>* _parent;Colour _col;//構造RBTreeNode(const pair<K, V>& kv):_kv(kv), _left(nullptr), _right(nullptr), _parent(nullptr), _col(BLACK){}
};

插入

首先實現最簡單的插入操作。

1，首先判斷是否是空樹，因為空樹也是紅黑樹。如果是空樹，創建新節點，顏色是黑色（根節點必須是黑色），返回即可。

2，查找我們數據應該插入的位置，查找規則和二叉搜索樹一樣。比當前結點大，再去和右孩子的結點比較；比當前結點小，再去和左孩子的結點比較；即大就向右走，小就向左走，直到找到空，執行插入操作。

3，不是空樹，創建新增結點，默認顏色是紅色。為什么不給黑色，仔細分析紅黑樹的規則發現：如果新增結點是黑色的話，那么就可能會破壞其他簡單路徑上黑色結點數量，造成簡單路徑黑色結點的數量不相等。所以默認是紅色結點，這樣更方便。

那是否可以將全部結點都設置為黑色呢？按照紅黑樹的規則來看，邏輯上沒有問題，但是這樣的紅黑樹就失去了原本意義，全部都是黑色結點和二叉搜索樹沒有區別，而且還浪費了存儲顏色的額外空間。

4，最簡單的情況是，新節點的父親結點是黑色，則插入成功后就結束。

但是如果父親結點是紅色，那么插入新節點后就需要進行變色處理，原因是紅黑樹不會存在連續的紅色結點，變色處理稍微麻煩，放到后邊位置詳細說明。

參考代碼：

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);return true;}//記錄cur的父結點Node* parent = nullptr;Node* cur = _root;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->_right = cur;}else{parent->_left = cur;}cur->_parent = parent;return true;}private:Node* _root = nullptr;
};

變色

前面分析過，如果新節點的父親結點存在且為紅色，那么需要對祖先結點進行變色。

但是變色依舊有多種情況，需要分別討論。

為了方便使用縮寫展示：g代表grandfather，p代表parent，u代表uncle，c代表cur即新結點。

1，

父親結點存在且為紅色
此時的父親結點是爺爺結點的左孩子
叔叔結點存在并且為紅色

在這里插入圖片描述

此時經過分析得到，我們需要對父親結點進行變色處理，以下是參考過程：

將父親和叔叔結點顏色變黑，爺爺結點顏色變紅
注意：為了防止此處將根結點也變為紅色，所以在最后一處_root->_col = RED
如果此時符合紅黑樹的規則，那么即可結束，反之向上更新結點，直到結束。

//更新結點位置，向上更新
cur = grandfather;
parent = cur->_parent;

2，

父親結點存在且為紅色
此時的父親結點是爺爺結點的左孩子
叔叔結點不存在或者存在且為黑色

此時需要進行變色+旋轉處理。

但是旋轉時又有所差異：如果cur是parent的左孩子（如下圖），需要以grandfather為旋轉點進行右單旋；

如果cur是parent的右孩子（如下圖），需要先以parent為旋轉點左單旋，再以grandfather為旋轉點進行右單旋的左右雙旋，最后要記得將旋轉后的cur改為黑色，grandfather改為紅色。

3，

父親結點存在且為紅色
此時的父親結點是爺爺結點的右孩子
叔叔結點存在且為紅色

與情況1類似不再贅述。

4，

父親結點存在且為紅色
此時的父親結點是爺爺結點的右孩子
叔叔結點不存在或者存在且為黑色

與情況2類似不再贅述。

變色參考代碼：

		//變色處理while (parent && parent->_col == RED){Node* grandfather = parent->_parent;//  g//p   uif (parent == grandfather->_left){Node* uncle = grandfather->_right;//叔叔結點存在，并且為紅色if (uncle && uncle->_col == RED){//將父親和叔叔結點顏色變黑，爺爺結點顏色變紅//為了防止此處將根結點也變為紅色，所以在最后一處_root->_col = REDparent->_col = uncle->_col = BLACK;grandfather->_col = RED;//更新結點位置，向上更新cur = grandfather;parent = cur->_parent;}//叔叔結點不存在，或者存在并且為黑色//變色+旋轉else{//    g//  p   u//cif (cur == parent->_left){RotateR(grandfather);parent->_col = BLACK;grandfather->_col = RED;}//cur == parent->_rightelse{//    g//  p   u//    c//雙旋RotateL(parent);RotateR(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}//    g//  u   p//parent == grandfather->_rightelse{Node* uncle = grandfather->_left;//叔叔結點存在，并且為紅色if (uncle && uncle->_col == RED){//將父親和叔叔結點顏色變黑，爺爺結點顏色變紅//為了防止此處將根結點也變為紅色，所以在最后一處_root->_col = REDparent->_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;}//cur == parent->_leftelse{//    g//  p   u//    c//雙旋RotateR(parent);RotateL(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}}_root->_col = BLACK;

查找

查找很簡單，與二叉搜索樹的查找規則一樣。

即要查找的cur結點的值大于根結點就向右走，比當前結點小就向左走，直到查找到或者走到空為止。

查找參考代碼

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

遍歷

因為紅黑樹是二叉搜索樹，所以使用中序遍歷即可。

//中序遍歷
void _InOrder(Node* root)
{if (root == nullptr){return;}_InOrder(root->_left);cout << root->_kv.first << " ";_InOrder(root->_right);
}

紅黑樹檢查

對紅黑樹檢查時，可以從紅黑樹的規則入手。

1，每個結點不是紅色就是黑色。

2，根結點是黑色的。

3，如果?個結點是紅?的，則它的兩個孩?結點必須是??的，也就是說任意?條路徑不會有連續的紅色結點。

4，對于任意?個結點，從該結點到其所有NULL結點的簡單路徑上，均包含相同數量的??結點。

對于規則1，我們在實現時，使用的就是紅色和黑色的枚舉，不可能出現其他顏色。

對于規則2，也很好判斷，加一句判斷語句即可。

對于規則3，前序遍歷檢查，遇到紅?結點查孩?不太?便，因為孩?有兩個，且不?定存在，反過來檢查?親的顏?就?便多了。

對于規則4，前序遍歷，遍歷過程中?形參記錄跟到當前結點的blackNum(??結點數量)，前序遍歷遇到??結點就++blackNum，?到空就計算出了?條路徑的??結點數量。再任意?條路徑??結點數量作為參考值，依次?較即可。

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);
}bool IsBalance()
{//首先，如果是空樹也是紅黑樹if (_root == nullptr){return true;}//再者，如果根結點是紅色，不是紅黑樹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);
}