一. 紅黑樹的概念

二叉樹的優化，每個節點有一個變量表示結點的顏色，可以是紅色或黑色，通過對節點顏色的約束，可以確保沒有路徑比其他路徑長出兩倍，接近平衡。

1. 紅黑樹的規則

1. 每個節點不是紅色就是黑色
2. 根節點是黑色
3. 不能有相連的紅色節點，也就是說一個節點如果是紅色，他的孩子一定是黑色
4. 對于任意一條從根節點到空的路徑，黑色節點的數量都相同
   

思考

為什么紅黑樹的最長路徑不超過最短路徑的兩倍？
每條路徑都有相同數量的黑色節點，假設一條路上全是黑色，這是最短的路徑長度為h，由于不能有相連的紅色節點，最長的路徑是一個紅一個黑的路徑排列，長度為2h，所以對任意一條路徑長度x來說，h<=x<=2h

2. 紅黑樹的效率

假設節點數量為N，h為最短路徑長度，2^h-1 <= N < 2^2*h-1, 分析可得h=logN,由此可見最快的查找為logN，最壞的情況下高度為2h，查找效率也還是2*logN，所以紅黑樹的查找效率為O(logN)

二.紅黑樹的實現

1. 紅黑樹的結構

用bool類型來定義樹的顏色，
定義parent，left和right指針方便后續的調整

typedef bool RBTreeColor;
const  RBTreeColor RBTreeRed = true;
const  RBTreeColor RBTreeBlack = false;template <class K,class V>
struct RBTreeNode
{typedef RBTreeNode Node;pair<K, V> _kv;Node* _parent;Node* _left;Node* _right;RBTreeColor _color;RBTreeNode(const pair<K,V>& kv):_kv(kv),_parent(nullptr),_left(nullptr),_right(nullptr),_color(RBTreeRed){}
};
template <class K, class V>
class RBTree
{
public:typedef RBTreeNode Node;private:Node*  _root=nullptr;
};

2. 紅黑樹的插入

1. 先按照二叉樹的規則進行插入
2. 如果是空樹插入，則新插入的節點為黑色，成為樹的根，否則新插入的節點為紅色，這是為了維護每條路徑上的黑色節點數量相同這個規則
3. 非空樹插入后，新增節點為紅色，如果父節點為黑色，不違反插入規則，插入結束
4. 非空樹插入后，新增節點為紅色，如果父節點也為紅色，違反插入規則，需要進行平衡調整

3. 紅黑樹的平衡調整

走到了平衡這一步，一定是因為出現了相連的兩個紅色節點，新插入節點c(cur)為紅色，插入節點的父節點p(parent)一定也為紅色，父節點的父節點g(grandparent)一定是黑色，這三個節點的顏色都是固定的，關鍵看父節點兄弟節點u(uncle)的情況，根據u的情況,可以分出幾種平衡調整規則

情況1：變色

u存在且為紅，p和u變成黑色，g變成紅色，把g當成新的c，繼續向上更新
分析：以g為根的左右子樹的黑色節點數是一定的，把g變成紅色，p和u變成黑色，不會影響左右子樹的黑色節點數，以g為根的樹的黑色節點數的也沒有改變，由于g的父節點也是紅色，所以需要把g當成新的c節點繼續向上更新

情況2：單旋+變色

u不存在或者存在且為黑
u不存在時，c一定是新增節點；u存在且為黑時，c一定不是新增節點，符合情況一
分析：這種情況必須使p的變成黑色，g變成紅色，然后旋轉，讓p變成這棵樹新的根，由于新的根是黑色，不管他的父節點是什么，都符合紅黑樹的規則，插入結束
關于旋轉的具體分析參照AVL數章節

當p是g的左孩子，c是p的左孩子，以g為旋轉點，進行右單旋，p變成新的根，

當p是g的右孩子，c是p的右孩子，以g為旋轉點，進行左單旋，p變成新的根，

情況3：雙旋+變色

u不存在或者存在且為黑
u不存在時，c一定是新增節點；u存在且為黑時，c一定不是新增節點，符合情況一
分析：和情況二類似，根據情況單旋變雙旋

當p是g的左孩子，c是p的右孩子，先以p為旋轉點，進行左單旋，然后以g為旋轉點，進行右單旋，c變黑，g變紅，c變成這棵樹新的根

當p是g的右孩子，c是p的左孩子，先以p為旋轉點，進行右單旋，然后以g為旋轉點，進行左單旋，c變黑，g變紅，c變成這棵樹新的根

4. 紅黑樹插入及平衡調整代碼實現

旋轉代碼參考AVL章節—>AVL原理及實現

};
template <class K, class V>
bool RBTree < K,V>::Insert(const pair<K, V>& kv)
{if (_root == nullptr){_root = new Node(kv);_root->_color = RBTreeBlack;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 (parent->_kv.first < kv.first)parent->_right = cur;elseparent->_left = cur;cur->_parent = parent;while (parent && parent->_color == RBTreeRed){Node* grandfather = parent->_parent;//  g//p   u//p為g的左代碼實現if (parent == grandfather->_left){Node* uncle = grandfather->_right;//  u存在且為紅,p和u變黑，g變紅，改變cur和p的指向，繼續向上變；if (uncle && uncle->_color == RBTreeRed){parent->_color = uncle->_color = RBTreeBlack;grandfather->_color = RBTreeRed;cur = grandfather;parent = grandfather->_parent;}// u不存在或存在且為黑else{//      g//    p    u//  c//單旋加變色，c為p的左,   p變成新的根，p變黑，g變紅if (cur == parent->_left){RorateR(grandfather);parent->_color = RBTreeBlack;grandfather->_color = RBTreeRed;}//        g//    p         u//       c//雙旋加變色，c為p的右，else{RorateLR(grandfather);cur->_color = RBTreeBlack;grandfather->_color = RBTreeRed;}}}else{ //這里是p為g的情}return true;}

5.紅黑樹的驗證

這里需要回憶一下紅黑樹四條規則，只要滿足了這四條規則，就符合紅黑樹的標準

1. 節點顏色用bool值標記，天然滿足這個規則
2. 檢查根節點是否是黑色即可
3. 一個節點可能不止一個孩子，但一個節點只能有一個父親，所以遇到一個紅色節點就查他的父親是否是黑色，滿足這點就滿足了第三點
4. 可以先序計算任意一條路徑黑色節點的數量 ，然后讓每個路徑的黑色節點數和他比較，如果全都相等就滿足第四條規則

template <class K, class V>
bool RBTree < K, V>::check(Node* root, int count, const int blackNum)
{// 檢查到空樹就比較黑色節點數if (root == nullptr){if (count == blackNum)return true;elsereturn false;}//如果有連續的紅色節點，返回false，// 這里的root不會是根節點，如果是根節點在IsBanlance函數就已經檢測出并返回了，所以每一個紅色節點的父節點都不會為空if (root->_color == RBTreeRed && root->_parent->_color == RBTreeRed)return false;//遇到黑色節點if (root->_color == RBTreeBlack)count++;return check(root->_left, count, blackNum) && check(root->_right, count, blackNum);
}
template <class K, class V>
bool RBTree < K, V>::IsBanlance(Node* root)
{if (root == nullptr)return true;if (root->_color == RBTreeRed)return false;Node* cur = root;int count = 0;while (cur){if (cur->_color == RBTreeBlack)count++;cur = cur->_left;}
}