一、紅黑樹概念
1.1 什么是紅黑樹
紅黑樹，是一種二叉搜索樹，但在每個結點上增加一個存儲位表示結點的顏色，可以是Red或 Black。 通過對任何一條從根到葉子的路徑上各個結點著色方式的限制，紅黑樹確保沒有一條路徑會比其他路徑長出倆倍，也就是最長路徑不超過最短路徑的2倍，因而是接近平衡的。
2.1 紅黑樹的性質
- 每個結點不是紅色就是黑色
- 根節點是黑色的
- 如果一個結點是紅色的，則他的兩個孩子是黑色的，及不存在兩個連續的紅色結點
- 對于每個葉子結點，從該結點到其所有后代葉結點的簡單路徑，均包含相同數目的黑色節點
- 每個葉子結點都是黑色的（此處的葉子節點指的是空節點）
思考：為什么滿足上面的性質，紅黑樹就能保證：其最長路徑中節點個數不會超過最短路徑節點 個數的兩倍？
【解釋】：由于紅黑樹要保證每條路徑的黑色結點個數相同，且不能存在連續的兩個紅色結點，所以最短路徑就是全黑，最長路徑是一黑一紅交替，這樣紅黑樹的最長路徑的極限也只能為最短路徑的兩倍
二、紅黑樹的實現
2.1 紅黑樹結點的定義
enum Color
{RED,BLACK
};
template<class K,class V>
struct RBTreeNode
{RBTreeNode(const pair<K,V>& kv):_left(nullptr),_right(nullptr),_parent(nullptr),_kv(kv),_col(RED){}struct RBTreeNode* _left;struct RBTreeNode* _right;struct RBTreeNode* _parent;pair<K, V> _kv;Color _col;
};思考：在結點的定義中，為什么要將結點的默認顏色給成紅色的？
【解釋】：若將結點的顏色默認為黑色，由于要求每條路徑的黑色結點個數相同，如果新插入一個結點，就會破壞這個性質，影響比較大，如果將結點的顏色默認為紅色，那么最多也就會出現兩個連續的紅色結點，只會影響一條路徑，只需要進行調整即可，影響比較小
2.2 紅黑樹的插入
1. 按照二叉搜索樹的規則將結點插入到紅黑樹中
2. 檢測插入結點后，紅黑樹的性質是否遭到破壞
因為新節點的默認顏色是紅色，因此：如果其雙親節點的顏色是黑色，沒有違反紅黑樹任何 性質，則不需要調整；但當新插入節點的雙親節點顏色為紅色時，就違反了性質三不能有連在一起的紅色節點，此時需要對紅黑樹分情況來討論：
約定:cur為當前節點，p為父節點，g為祖父節點，u為叔叔節點（因為cur與p一定為紅色，g一定為黑色，我們只需要對u進行討論）
- 情況一：cur為紅，p為紅，g為黑，u存在且為紅（假設uncle在g的右邊）
注意：此時看到的樹可能是一顆完整的樹，也可能是一顆子樹
解決方法：
????????由于出現了連續的兩個紅色結點，我們只能將p變為黑色，因為如果cur為新增結點，將其變為黑色會破壞性質4，而將p變為黑色，會導致g的左右子樹黑色節點不同，所以需要將u也變為黑色，而g有可能只是一顆子樹，為了保證與其他路徑的黑色節點個數相同，還需要將g變為紅色，如果g為根節點的話，再將其變為黑色即可。
- 情況二：cur為紅色，p為紅色，g為黑色，u不存在或者u存在且為黑色（假設u在g的右邊）
說明：u的情況存在兩種
1.uncle不存在，那么cur一定是新增的那個結點，因為如果不是新增結點，那么cur和p至少有一個應該為黑色，不然就違反性質3了
2.uncle存在且為黑色，那么cur原來的顏色一定為黑色，現在看到cur的顏色為紅色是因為cur子樹在調整過程中將cur變為了紅色
【解決辦法】：
- 如果cur為p的左孩子
將p變黑，g變紅，以g作為父親結點右單旋
- 如果cur為p的右孩子
將cur變黑，g變紅，先以p為父親節點左單旋，在以g為父親節右單旋
ps：uncle為g左邊原理同上，對于旋轉不清楚的可以參考數據結構--AVL樹
2.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 (parent->_kv.first>kv.first){parent->_left = cur;}else{parent->_right = cur;}cur->_parent = parent;while (parent && parent->_col == RED){Node* grandfather = parent->_parent;if (parent == grandfather->_left){Node* uncle = grandfather->_right;if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfather->_col = RED;//繼續向上調整cur = grandfather;parent = cur->_parent;}else //uncle不存在或者uncle存在且為黑{if (cur == parent->_left){// g// p u// cRotateR(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{// g// p u// cRotateL(parent);RotateR(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}else{Node* uncle = grandfather->_left;if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfather->_col = RED;//繼續向上調整cur = grandfather;parent = cur->_parent;}else //uncle不存在或者uncle存在且為黑{if (cur == parent->_right){// g// u p// cRotateL(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{// g// u p// cRotateR(parent);RotateL(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}}_root->_col = BLACK;return true;
}三、紅黑樹的驗證
紅黑樹的檢測分為兩步：
1. 檢測其是否滿足二叉搜索樹(中序遍歷是否為有序序列)
2. 檢測其是否滿足紅黑樹的性質
bool IsBalance()
{if (_root->_col == RED)return false;Node* cur = _root;int RefNum = 0; //作為路徑黑色結點個數的參考while (cur){if (cur->_col == BLACK)RefNum++;cur = cur->_left;}return _IsBalance(_root,RefNum,0);
}bool _IsBalance(Node* root,int RefNum,int num)
{if (root == nullptr){//驗證每條路徑的黑色節點個數是否相同if (num != RefNum){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)num++;return _IsBalance(root->_left, RefNum, num) && _IsBalance(root->_right, RefNum, num);
}
)
