[數據結構]紅黑樹，詳細圖解插入

一、紅黑樹的概念

二、紅黑樹的性質

三、紅黑樹節點的定義

四、紅黑樹的插入（步驟）

1.為什么新插入的節點必須給紅色？

2、插入紅色節點后，判定紅黑樹性質是否被破壞

五、插入出現連續紅節點情況分析+圖解（看uncle節點）

5.1、uncle存在且為紅

5.2、uncle不存在

1、單旋

2、雙旋

5.3、uncle存在且為黑

1、單旋

2、雙旋

六、插入總結

1、紅黑樹插入的兩種步驟

?2、插入代碼

七、紅黑樹總結及代碼

一、紅黑樹的概念

紅黑樹，是一種二叉搜索樹，但在每個結點上增加一個存儲位表示結點的顏色，可以是Red或 Black。通過對任何一條從根到葉子的路徑上各個結點著色方式的限制，

紅黑樹確保——沒有一條路徑會比其他路徑長出兩倍，因而是接近平衡的

二、紅黑樹的性質

1. 每個結點不是紅色就是黑色

2. 根節點是黑色的?

3. 如果一個節點是紅色的，則它的兩個孩子結點是黑色的（沒有連續的紅節點）

4. 從任一結點到其所有后代葉結點的簡單路徑上，均包含相同數目的黑結點?

5. 每個葉子結點都是黑色的(此處的葉子結點指的是NIL空結點)

????????最優情況：全黑或每條路徑都是一黑一紅的滿二叉樹，高度logN

? ? ? ? 最差情況：每顆子樹左子樹全黑，右子樹一黑一紅。高度2*logN。

? ? ? ? 可以發現，最壞情況的時間復雜度和AVL樹一樣，都是O(logN)，但是紅黑樹這種近似平衡的結構減少了大量旋轉，綜合性能優于AVL樹。

三、紅黑樹節點的定義

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){}
};

四、紅黑樹的插入（步驟）

1.為什么新插入的節點必須給紅色？

（1）新節點給紅色，可能出現連續紅節點

（2）如果新節點給黑色，必定會違反性質4（其每條路徑的黑色節點數量相同）

2、插入紅色節點后，判定紅黑樹性質是否被破壞

因為新節點的默認顏色是紅色，所以

（1）雙親節點的顏色是黑色，沒有違反紅黑樹任何性質，則不需要調整；

（2）雙親節點為紅色，就會出現連續的紅節點，此時需要對紅黑樹分情況來討論：見下一部分

五、插入出現連續紅節點情況分析+圖解（看uncle節點）

約定:cur為當前節點，p為父節點，g為祖父節點，u為叔叔節點

下面的分析都是以p為g的左孩子為例

5.1、uncle存在且為紅

cur插入后，p和u變黑，g變紅

（1）g沒有父親，g為根，g變黑

（2）g有父親。其為黑，結束；其為紅，后把g當成cur，繼續向上調整

5.2、uncle不存在

u不存在，則cur一定是新插入的節點。

（如果cur不是新插入的節點，則cur和p一定有一個節點是黑色，否則每條路徑黑色節點不相同）

下圖為解釋：

1、單旋

右單旋

2、雙旋

?左單旋 + 右單旋?

5.3、uncle存在且為黑

uncle存在且為黑，是情況一變來的，所以cur原來的節點一定是黑色的。

現在其是紅色的原因是，cur的子樹在調整過程中將cur的顏色由黑變紅。

1、單旋

右單旋

2、雙旋

左單旋 + 右單旋

六、插入總結

1、紅黑樹插入的兩種步驟

1、uncle存在且為紅

2、uncle不存在或者 uncle存在且為黑

通過分析，

uncle不存在的單旋和 uncle存在且為黑的單旋可以寫在一起，

uncle不存在的雙旋和 uncle存在且為黑的雙旋可以寫在一起，

不論uncle存在或者不存在，都不影響此步的單旋或者雙旋。

當p為g的右孩子時，操作都相反。

詳細步驟見其中while (parent && parent->_col == RED)這一步。

?2、插入代碼

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);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* grandfather = parent->_parent;//p為g左孩子if (parent == grandfather->_left){Node* uncle = grandfather->_right;// 情況1：u存在且為紅 if (uncle && uncle->_col == RED){// 變色parent->_col = uncle->_col = BLACK;grandfather->_col = RED;// 繼續向上處理cur = grandfather;parent = cur->_parent;}else // u不存在 或 存在且為黑{//情況2.1 ， 3.1if (cur == parent->_left){//     g//   p// cRotateR(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else//情況2.2 , 3.2{//     g//   p//		cRotateL(parent);RotateR(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}//p為g右孩子else // parent == grandfather->_right{Node* uncle = grandfather->_left;// u存在且為紅if (uncle && uncle->_col == RED){// 變色parent->_col = uncle->_col = BLACK;grandfather->_col = RED;// 繼續向上處理cur = grandfather;parent = cur->_parent;}else{if (cur == parent->_right){// g//	  p//       cRotateL(grandfather);grandfather->_col = RED;parent->_col = BLACK;}else{// g//	  p// cRotateR(parent);RotateL(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}}_root->_col = BLACK;return true;
}

七、紅黑樹總結及代碼

紅黑樹和AVL樹都是高效的平衡二叉樹，增刪改查的時間復雜度都是O(logN)，紅黑樹不追求絕對平衡，只需保證最長路徑不超過最短路徑的2倍，相對而言，降低了插入和旋轉的次數，所以在經常進行增刪的結構中性能比AVL樹更優，而且紅黑樹實現比較簡單，所以實際運用中紅黑樹更多。

using namespace std;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){}};template<class K, class V>
struct 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);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* grandfather = parent->_parent;//p為g左孩子if (parent == grandfather->_left){Node* uncle = grandfather->_right;// 情況1：u存在且為紅 if (uncle && uncle->_col == RED){// 變色parent->_col = uncle->_col = BLACK;grandfather->_col = RED;// 繼續向上處理cur = grandfather;parent = cur->_parent;}else // u不存在 或 存在且為黑{//情況2.1 ， 3.1if (cur == parent->_left){//     g//   p// cRotateR(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else//情況2.2 , 3.2{//     g//   p//		cRotateL(parent);RotateR(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}//p為g右孩子else // parent == grandfather->_right{Node* uncle = grandfather->_left;// u存在且為紅if (uncle && uncle->_col == RED){// 變色parent->_col = uncle->_col = BLACK;grandfather->_col = RED;// 繼續向上處理cur = grandfather;parent = cur->_parent;}else{if (cur == parent->_right){// g//	  p//       cRotateL(grandfather);grandfather->_col = RED;parent->_col = BLACK;}else{// g//	  p// cRotateR(parent);RotateL(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}}_root->_col = BLACK;return true;}void RotateL(Node* parent){++_rotateCount;Node* cur = parent->_right;Node* curleft = cur->_left;parent->_right = curleft;if (curleft){curleft->_parent = parent;}cur->_left = parent;Node* ppnode = parent->_parent;parent->_parent = cur;if (parent == _root){_root = cur;cur->_parent = nullptr;}else{if (ppnode->_left == parent){ppnode->_left = cur;}else{ppnode->_right = cur;}cur->_parent = ppnode;}}void RotateR(Node* parent){++_rotateCount;Node* cur = parent->_left;Node* curright = cur->_right;parent->_left = curright;if (curright)curright->_parent = parent;Node* ppnode = parent->_parent;cur->_right = parent;parent->_parent = cur;if (ppnode == nullptr){_root = cur;cur->_parent = nullptr;}else{if (ppnode->_left == parent){ppnode->_left = cur;}else{ppnode->_right = cur;}cur->_parent = ppnode;}}bool CheckColour(Node* root, int blacknum, int benchmark){if (root == nullptr){if (blacknum != benchmark)return false;return true;}if (root->_col == BLACK){++blacknum;}if (root->_col == RED && root->_parent && root->_parent->_col == RED){cout << root->_kv.first << "出現連續紅色節點" << endl;return false;}return CheckColour(root->_left, blacknum, benchmark)&& CheckColour(root->_right, blacknum, benchmark);}bool IsBalance(){return IsBalance(_root);}bool IsBalance(Node* root){if (root == nullptr)return true;if (root->_col != BLACK){return false;}// 基準值int benchmark = 0;Node* cur = _root;while (cur){if (cur->_col == BLACK)++benchmark;cur = cur->_left;}return CheckColour(root, 0, benchmark);}int Height(){return Height(_root);}int Height(Node* root){if (root == nullptr)return 0;int leftHeight = Height(root->_left);int rightHeight = Height(root->_right);return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;}private:Node* _root = nullptr;public:int _rotateCount = 0;
};