1：紅黑樹的概念

紅?樹是?棵?叉搜索樹，他的每個結點增加?個存儲位來表?結點的顏?，可以是紅?或者??。通過對任何?條從根到葉?的路徑上各個結點的顏?進?約束，紅?樹確保沒有?條路徑會?其他路徑?出2倍，因?是接近平衡的。

1：紅黑樹的規則

1. 每個結點不是紅?就是??

2. 根結點是??的

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

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

2：紅黑樹確保最短路徑的方法

1:由規則4可知，從根到NULL結點的每條路徑都有相同數量的??結點，所以極端場景下，最短路徑就就是全是??結點的路徑，假設最短路徑?度為bh(black height)。

2:由規則2和規則3可知，任意?條路徑不會有連續的紅?結點，所以極端場景下，最?的路徑就是???紅間隔組成，那么最?路徑的?度為2* bh

3:綜合紅?樹的4點規則??，理論上的全?最短路徑和???紅的最?路徑并不是在每棵紅?樹都存在的。假設任意?條從根到NULL結點路徑的?度為x，那么bh <= h <= 2 * bh。

3： 紅?樹的效率

假設N是紅?樹樹中結點數量，h最短路徑的?度，那么, 由此推出，也就是意味著紅?樹增刪查改最壞也就是?最?路徑 ，那么時間復雜度還是。2h ? 1 <= N < 22?h ? 1h ≈ logN 2 ? logNO(logN)紅?樹的表達相對AVL樹要抽象?些，AVL樹通過?度差直觀的控制了平衡。紅?樹通過4條規則的顏?約束，間接的實現了近似平衡，他們效率都是同?檔次，但是相對??，插?相同數量的結點，紅?樹的旋轉次數是更少的，因為他對平衡的控制沒那么嚴格。

2：紅黑樹的模擬實現

1：紅黑樹的結構

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

template<class K, class V>
class RBTree
{typedef RBTreeNode<K, V> Node;
public:private:Node* _root = nullptr;
};

2：紅黑樹的插入

對于紅黑樹的插入我們一般分成兩種情況，一種是叔節點（父節點的兄弟節點）存在為紅；第二種是叔節點不存在或者為黑。

第一種情況很好處理，只需要變色就行，第二種情況需要變色加旋轉（和AVLTree樹的旋轉一樣，就不過多講解了）

下面是實現代碼

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 (kv.first < cur->_kv.first){parent = cur;cur = cur->_left;}else if (kv.first > cur->_kv.first){parent = cur;cur = cur->_right;}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;//調整邏輯while (parent && parent->_col == RED){Node* grandparent = parent->_parent;if (parent == grandparent->_left){Node* uncle = grandparent->_right;//uncle存在且為紅if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandparent->_col = RED;cur = grandparent;parent = cur->_parent;}//uncle不存在或者uncle為黑else{if (cur == parent->_right){RL(grandparent);parent->_col = BLACK;grandparent->_col = RED;}else{RR(parent);RL(grandparent);cur->_col = BLACK;grandparent->_col = RED;}break;}}else//(parent==grandparent->_right){Node* uncle = grandparent->_left;//uncle存在且為紅if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandparent->_col = RED;cur = grandparent;parent = cur->_parent;}else//uncle不存在或者為黑{if (cur == parent->_right){RL(grandparent);parent->_col = BLACK;grandparent->_col = RED;}else{RL(parent);RL(grandparent);cur->_col = BLACK;grandparent->_col = RED;}break;}}}}_root->_col = BLACK;return true;
}
//右單旋
void RR(Node* pParent)
{Node* subL = pParent->_left;Node* subLR = subL->_right;pParent->_left = subLR;if (subLR != nullptr){subLR->_parent = pParent;}subL->_right = pParent;Node* ppnode = pParent->_parent;pParent->_parent = subL;subL->_parent = ppnode;if (ppnode == nullptr){_root = subL;}else{if (ppnode->_left == pParent){ppnode->_left = subL;}else{ppnode->_right = subL;}}
}
//左單旋
void RL(Node* pParent)
{Node* subR = pParent->_right;Node* subRL = subR->_left;pParent->_right = subRL;if (subRL != nullptr){subRL->_parent = pParent;}subR->_left = pParent;Node* ppnode = pParent->_parent;pParent->_parent = subR;subR->_parent = ppnode;if (ppnode == nullptr){_root = subR;}else{if (ppnode->_left == pParent){ppnode->_left = subR;}else{ppnode->_right = subR;}}
}