紅黑樹介紹

1 問題引入

為什么有AVL樹，還要引入紅黑樹？
在進行多次的插入和刪除時：
??????? 1）AVL樹會存在大量的旋轉操作，追求的是嚴格平衡；
??????? 2）紅黑樹通過為節點增加顏色來換取增刪節點時旋轉次數的降低，任何不平衡都會在三次旋轉之內解決，追求的是部分平衡；
因此，在增刪節點時，根據不同的情況，AVL樹旋轉的次數比紅黑樹多。

2 紅黑樹的概念

1）是一種二叉搜索樹，但在每個節點上增加一個存儲位表示節點的顏色(紅色/黑色)；
2）通過對任何一條從根到葉子的路徑上各個結點著色方式的限制，紅黑樹確保沒有一條路徑會比其他路徑長出倆倍，因而是接近平衡。即最長路徑不會超過最短路徑的2倍；比如，假設最短路徑是h,最長就是2h，其他路徑的長度則為[h,2h]。

2.1 紅黑樹的性質

1）每個節點不是紅色就是黑色；
2）根節點是黑色的；
3）如果一個節點是紅色的，則它的倆個孩子節點必須是黑色的。即沒有連續的紅色節點；但是并沒有說黑色節點的孩子必須是紅色節點；
4）對于每個節點，從該節點到其所有后代葉節點的簡單路徑上，均包含相同數目的黑色節點。即每條路徑都會包含相同數量的黑色節點；
5）每個葉子結點都是黑色的(此處的葉子結點指的是空節點，即NIL節點)，避免數錯了路徑個數(路徑：從根走到NIL節點)。

所以我們可以根據上面的性質思考一下，為什么滿足上面的性質，紅黑樹就能保證：從根結點到NULL節點，其最長路徑中節點個數不會超過最短路徑節點個數的倆倍？

在極端場景下我們可以進行分析：

整體紅黑樹圖，此時滿足紅黑樹的性質：

最短路徑：全黑

?最長路徑：一黑一紅

2.2 AVL樹與紅黑樹的比較

1）AVL樹的高度接近log2N；
2）紅黑樹的高度，如果是從最短路徑看，則是全黑，相當于一個滿二叉樹；

而滿二叉樹的高度計算如下：
???????????????????????????????? N=2h?1 --》 h=log2(N+1) ≈ log2N;
那么我們可以知道，最長路徑(一黑一紅)，則是2* log2N;
我們可以舉一個實際的例子：
假如有10億個數，那么log2N=10億 --》N=30；
AVL樹：需要尋找30次；
紅黑樹：需要尋找60次；
雖然紅黑樹尋找的次數比AVL數多，但是對于現有的cpu來說，并沒有太大的影響。

總結：
1）從查找效率來說，AVL樹與紅黑樹相差不大；
2）從增刪操作來說，AVL樹需要通過多次旋轉來降低高度來保持嚴格平衡，但是旋轉是有代價的。而紅黑樹并不是這樣，只是近似平衡，從而減少了旋轉的次數。
總的來說，紅黑樹的效率要比AVL樹好。

3 紅黑樹的定義及插入操作討論

3.1 紅黑樹的定義

enum Colour
{RED,BLACK
};template<class K,class V>
struct RBTreeNode
{RBTreeNode<K, V>* _left;RBTreeNode<K, V>* _right;RBTreeNode<K, V>* _parent;pair<K, V> _kv;Colour _col;RBTreeNode(const pair<K,V>& kv):_left(nullptr),_right(nullptr),_parent(nullptr),_kv(kv),_col(RED)//新增節點給為紅色{}
};

3.2 紅黑樹的插入操作討論

紅黑樹也是一顆二叉搜索樹，所以當進行插入操作的時候我們也可以通過之前所學系的AVL樹的插入操作進行實行。但是在插入過程中我們得遵循紅黑樹的性質，因此，我們對其進行了一些討論，如下：

首先，我們先定義一個紅黑樹操作的框架：

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);//但是要注意的是紅黑樹的根是黑色的_root->_col = BLACK;return true;}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);//新插入結點是紅色，這是在初始化的時候就定義的紅色if (cur->_kv.first < parent->_kv.first){parent->_left = cur;cur->_parent = parent;}else{parent->_right = cur;cur->_parent = parent;}//檢驗是否滿足紅黑樹的性質，所以在此進行討論}
private:Node* _root;
};

3.2.1 實施過程中的問題

根節點是黑色，這是紅黑樹的性質要求的。那么新插入結點開始為什么要是紅色？

因為根據紅黑樹的性質要求，每條路徑的黑色節點的數量都是相同的，那么如果插入結點是黑色的話，那么其他路徑就都少了一個黑色節點，這樣調整起來工程量較大，十分麻煩。所以插入結點顏色一定是紅色。但是如果插入節點的父親節點是黑色，那是沒有問題的。若插入結點的父親節點是紅色的，那么就會違反紅黑樹的性質(沒有連續的紅色節點)，那就需要進行處理。

3.2.2 對于叔叔節點(u)的討論

接下來，我們插入紅色節點，將父親節點設定為紅色，從而破壞了紅黑樹(沒有連續的紅色節點)的性質。因為爺爺節點(g)、父親節點(p)和當前節點(cur)都是固定的，所以下面我們將要對叔叔節點(u)進行討論。
假設：
①g(grandfather):爺爺節點
②p(parent):父親節點
③u(uncle):叔叔節點
④cur(current):當前節點

1）情形一：叔叔節點(u)存在且為紅色

g = 黑色，p = 紅色，u = 紅色，cur = 紅色。

?問題說明：
①孩子節點(cur)是紅色的，父親節點(p)是紅色的，爺爺節點(g)是黑色的，此時叔叔節點是我們的關鍵。
②根據紅黑樹的性質，倆個紅色不能相連，所以我們需要將父親節點(p)變為黑色，但是父親節點(p)變黑，那么叔叔節點(u)就少了一個黑色。
此時我們將爺爺節點(g)變為紅色。

?③但是，此時叔叔節點(u)的路徑就少了一個黑色節點。因此，我們將叔叔節點(u)變為黑色。

?④爺爺節點(g)是否為根節點？
????????1）若爺爺節點(g)是根節點，則將爺爺節點(g)變為黑色。

????????2）若爺爺節點(g)是子樹，爺爺節點(g)一定有父親節點，且爺爺節點(g)的父親如果是紅色，則需要繼續向上調整。?

?以上為第一種情況的抽象圖，下面我們對具體的圖形進行解析：

①a/b/c/d/e為空樹

②c/d/e是下面4個子樹中的一種(一個黑色節點)：

?從上我們可以看一下共有多少種情況：
c/d/e為上面4種中的任意一種：4×4×4=64種
插入位置共有4中位置
所以此紅黑樹共有64×4=256種情況。

總結(情況一(叔叔節點(u)存在且為紅)的解決方案):

①p/u變為黑色，g變為紅色；
②如果g為根，再把g變為黑色；
③若g不為根，則繼續往上處理(g可以當做現在的cur)；
④p/u是g的左或者右沒有影響，cur是p的左或者右也沒有影響，處理方式是相同的。

2）情況二：叔叔節點(u)不存在/叔叔節點(u)存在且為黑

①叔叔節點(u)不存在，則當前節點(cur)就是新增，因為如果cur不是新增節點，則cur和p一定有一個節點的顏色是黑色，就不滿足每條路徑黑色節點個數相同的性質。

?②叔叔節點(u)存在，則一定是黑色。(因為改為叔叔節點(u)存在，且為紅色的情況我們已經分析了)，那么當前節點(cur)則必定為黑色。第二步中的cur節點為紅色是因為在調整過程中由黑色變為了紅色。

?總結(情況二：叔叔節點(u)不存在/叔叔節點(u)存在且為黑的解決方案)：

①p為g的左孩子，cur為p的左孩子，則進行右單旋；
②p為g的右孩子，cur為p的右孩子，則進行左單旋；
③p、g變色：p變為黑色，g變為紅色。

3）情況三：叔叔節點(u)不存在/叔叔節點(u)存在且為黑

雖然情況三和情況二的條件是一樣的，但是cur和p不在同一側。

1）叔叔節點(u)不存在，cur為新增節點

?2）叔叔節點(u)存在且為黑

總結(情況三：叔叔節點(u)不存在/叔叔節點(u)存在且為黑的解決方案)：

1）p為g的左孩子,cur為p的右孩子,則進行左右雙旋+變色；
2）p為g的右孩子,cur為p的左孩子,則進行右左雙旋+變色;
3）g、cur變色：g變為紅色，cur變為黑色。

3.3 插入操作完整代碼

bool Insert(const pair<K,V>& kv){if (_root == nullptr){_root = new Node(kv);//但是要注意的是紅黑樹的根是黑色的_root->_col = BLACK;return true;}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);//新插入結點是紅色，這是在初始化的時候就定義的紅色if (cur->_kv.first < parent->_kv.first){parent->_left = cur;cur->_parent = parent;}else{parent->_right = cur;cur->_parent = parent;}//檢驗是否滿足紅黑樹的性質，所以在此進行討論//1.此時cur為紅，parent為紅，此時就違反了紅黑樹的性質//8.繼續向上處理的判斷是parent存在且為紅色的情況,所以記性增加parent存在的情況while (parent && parent->_col == RED){//3.插入之前可以認為是紅黑樹，cur為紅，parent為紅，則肯定有爺爺節點Node* grandfather = parent->_parent;//4.此時，cur、parent、grandfather是固定的，則需要找uncle節點，從而看如何變化使其不違反紅黑樹性質if (parent == grandfather->_left){Node* uncle = grandfather->_right;//5.情況一：叔叔節點uncle存在且為紅if (uncle && uncle->_col == RED){parent->_col = BLACK;uncle->_col = BLACK;grandfather->_col = RED;//6.繼續往上處理cur = grandfather;parent = cur->_parent;//7.第一種情況如果g為根，則將grandfather的顏色變為黑色，這個可以在循環外進行處理//如果parent->_colour == 黑色，則無需進行處理//所以我們需要進行處理的是parent->_colour == 紅色,所以我們可以在while循環處進行下一次向上處理判斷}else //8.情況二：叔叔節點uncle不存在/為黑色，但是此時不需要考慮uncle節點，因為旋轉和變色都與其無關{//9.上面滿足了p為g的左孩子,此時應滿足cur是p的左孩子條件if (cur == parent->_left){RotalR(grandfather);parent->_col = BLACK;grandfather->_col = RED;}//10.情況三：情況三和情況二的條件是一樣的，但是cur和p不在同一側。//此時要求cur是p的右孩子情況else{RotalLR(grandfather);grandfather->_col = RED;cur->_col = BLACK;}//11.如果是雙旋，那么因為parent是紅色，不能通過while循環判斷，并且也不會違反規則了，所以可以直接break;break;}}else{Node* uncle = grandfather->_left;//5.情況一：叔叔節點uncle存在且為紅if (uncle && uncle->_col == RED){parent->_col = BLACK;uncle->_col = BLACK;grandfather->_col = RED;//6.繼續往上處理cur = grandfather;parent = cur->_parent;//7.第一種情況如果g為根，則將grandfather的顏色變為黑色，這個可以在循環外進行處理//如果parent->_colour == 黑色，則無需進行處理//所以我們需要進行處理的是parent->_colour == 紅色,所以我們可以在while循環處進行下一次向上處理判斷}else //8.情況二：叔叔節點uncle不存在/為黑色，但是此時不需要考慮uncle節點，因為旋轉和變色都與其無關{//9.上面滿足了p為g的右孩子,此時應滿足cur是p的右孩子條件if (cur == parent->_right){RotalL(grandfather);parent->_col = BLACK;grandfather->_col = RED;}//10.情況三：情況三和情況二的條件是一樣的，但是cur和p不在同一側。//此時要求cur是p的右孩子情況else{RotalRL(grandfather);grandfather->_col = RED;cur->_col = BLACK;}//11.如果是雙旋，那么因為parent是紅色，不能通過while循環判斷，并且也不會違反規則了，所以可以直接break;break;}}}//7.如果grandfather是根，則可以再次進行處理_root->_col = BLACK;//2.如果parent不是紅色，則說明沒有問題return true;}//旋轉部分：與AVL樹是一樣的，只是減少了平衡因子//左單旋void RotalL(Node * parent){//定義階段Node* subR = parent->_right;Node* subRL = subR->_left;//更改階段parent->_right = subRL;if (subRL)//子樹可能是空{subRL->_parent = parent;}//先記錄parent的父結點,因為parent可能是一個子樹，也可能是一個根Node* ppnode = parent->_parent;subR->_left = parent;parent->_parent = subR;//如果是根if (parent == _root){_root = subR;subR->_parent = nullptr;}else//parent不是根，那么parent可能是父結點的左節點還是右結點{if (parent == ppnode->_left){ppnode->_left = subR;}else{ppnode->_right = subR;}subR->_parent = ppnode;}}//右單旋void RotalR(Node* parent){//1.定義節點//2.更改階段//3.注意子樹可能為空//4.parent是否為根//5.更新平衡因子Node* subL = parent->_left;Node* subLR = subL->_right;//更改階段parent->_left = subLR;if (subLR){subLR->_parent = parent;}Node* ppnode = parent->_parent;subL->_right = parent;parent->_parent = subL;if (parent == _root){_root = subL;subL->_parent = nullptr;}else{if (parent == ppnode->_left){ppnode->_left = subL;}else{ppnode->_right = subL;}subL->_parent = ppnode;}}//左右旋void RotalLR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;//進行旋轉RotalL(parent->_left);//以30為旋轉點進行旋轉RotalR(parent);//以90為旋轉點進行旋轉}//右左旋void RotalRL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;//先進行右旋轉，再左旋轉RotalR(subR);RotalL(parent);}

4 判斷是否為紅黑樹

如果讓你判斷一棵樹是否為紅黑樹，你會如何判斷？
1）A同學：紅黑樹中有這樣一條概念：最長路徑不會超過最短路徑的2倍，能否使用這個概念來進行判斷？
是不可以的，因為如果這顆樹的確滿足最長路徑不超過最短路徑2倍這個概念，但是如果路徑的顏色如果不滿足紅黑樹的性質，那么這棵樹顯而易見也不是紅黑樹。所以這個思路是不可行的。

2）B同學：我們可以通過紅黑樹的性質來進行判斷這顆樹是一顆紅黑樹？
是可以的，因為若滿足紅黑樹的性質，則可以判斷其是一顆紅黑樹。并且性質中的每條路徑的黑色節點數量相同，則可以限制最長路徑不會超過最短路徑倆倍這個概念。

判斷一顆樹是否為紅黑樹，我們主要滿足紅黑樹性質的2、3、4條性質。
其中第2條性質很好判斷：

//性質2：根節點是黑色的if (_root->_col != BLACK){return false;}

性質3卻存在一個小問題：如果一個節點是紅色的，則它的倆個孩子節點必須是黑色的。
那么我們是那當前節點和它的孩子節點比較還是和它的父親節點進行比較？如果是孩子節點，那么我們首先需要判斷它是否有孩子節點，其次，需判斷是它的左孩子還是右孩子，這樣寫起來，代碼就顯得比較繁瑣復雜。
因此，我們換種思路，如果當前節點和其父親節點進行比較，那么該節點只有一個父親節點，并且這樣判斷也可以滿足不能有連續紅色節點的性質，所以這樣是比較優秀的解法。

//檢查是否滿足性質3:沒有連續的紅色節點if (cur->_col == RED && cur->_parent->_col == RED){return false;}

但是性質4確實有些難度：
首先，我們可以使用遞歸來檢驗這棵樹。?

bool check(Node* cur)
{if(cur == nullptr){return true;}return check(cur->_left) && check(cur->_right);
}
bool IsRBTree()
{if(_root == nullptr){return true;}check(_root);
}

其次，我們可以將上面的我們寫好的性質的代碼添加進去。

bool check(Node* cur)
{if(cur == nullptr){return true;}//檢查是否滿足性質3:沒有連續的紅色節點if (cur->_col == RED && cur->_parent->_col == RED){return false;}return check(cur->_left) && check(cur->_right);
}
bool IsRBTree()
{if(_root == nullptr){return true;}//性質2：根節點是黑色的if (_root->_col != BLACK){return false;}check(_root);
}

最后，我們只需要滿足性質4:每條路徑有相同數量的黑色節點即可。

此時有這樣一個思路：

1）首先我們計算一條路徑中的黑色節點數量作為一個參考值；
2）遞歸每條路徑并計算黑色節點的數量與這個參考值進行比較，若相等則正確，不相等則報錯。

bool check(Node* cur,int BlackNum,int RefNum){if (cur == nullptr){//到達葉子結點時進行判定黑色節點數量與算出來的數量是否相同//檢查是否滿足性質4if (BlackNum != RefNum){return false;}return true;}//檢查是否滿足性質3:沒有連續的紅色節點if (cur->_col == RED && cur->_parent->_col == RED){return false;}//如果當前節點cur為黑色節點,則黑色節點數量++if (cur->_col == BLACK){BlackNum++;}//該節點的左節點和右結點繼續遞歸,沒有加&，則表示每一層多少個，不受下一層的影響return check(cur->_left, BlackNum, RefNum) && check(cur->_right,BlackNum,RefNum);}bool IsRBTree(){if (_root == nullptr){return true;}//性質2：根節點是黑色的if (_root->_col != BLACK){return false;}//因為每條路徑的黑色節點的個數是相同的//所以我們可以設置一個參考值int RefNum = 0;Node* left = _root;while (left){//如果節點的顏色為黑色,則++if (left->_col == BLACK){RefNum++;}left = left->_left;}//通過check()進行檢查return check(_root,0,RefNum);}

我們進行驗證這個紅黑樹是否正確：

int main()
{RBTree<int,int> r1;int a[] = { 3,2,4,5,6,7,8,10,9,1 };for (auto e : a){r1.Insert(make_pair(e,e));}r1.Inorder();cout << r1.IsRBTree() << endl;
}