💓博主CSDN主頁:麻辣韭菜💓
?
?專欄分類：C++知識分享?
?
🚚代碼倉庫:C++高階🚚
?
🌹關(guān)注我🫵帶你學(xué)習(xí)更多C++知識
? 🔝🔝

---

?

---

前言

前面我們實現(xiàn)了AVL樹，發(fā)明AVL樹的人是天才，那發(fā)明紅黑樹的人就是天才中天才。

AVL由于加入平衡因子，所以對樹的平衡過于嚴格。這就導(dǎo)致了頻繁的旋轉(zhuǎn)。從而增加時間復(fù)雜度。這也是為什么map和set底層的封裝沒有用AVL樹，而是用的紅黑樹！！！

一、紅黑樹的概念

二、紅黑樹的性質(zhì)?

1. 每個結(jié)點不是紅色就是黑色

2. 根節(jié)點是黑色的?

3. 如果一個節(jié)點是紅色的，則它的兩個孩子結(jié)點是黑色的?

4. 對于每個結(jié)點，從該結(jié)點到其所有后代葉結(jié)點的簡單路徑上，均 包含相同數(shù)目的黑色結(jié)點?

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

三、紅黑樹節(jié)點的定義 ?

enum Color //顏色
{RED,BLACK,
};template<class T, class V>
struct RBTreeNode
{RBTreeNode<T, V>* _left; //左孩子RBTreeNode<T, V>* _right; //右孩子RBTreeNode<T, V>* _parent; //父親pair<T, V> _kv;Color _col;RBTreeNode(const pair<T, V>& kv):_left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv), _col(RED) //為什么默認是紅色？根節(jié)點必須是黑色，這就意味著默認給黑色那么調(diào)整次數(shù)就會變多。{}
};

利用節(jié)點這個類，我們再定義紅黑樹類 。

template <class T, class V>
class RBTree
{typedef RBTreeNode<T, V> Node; //節(jié)點名字太長 重新命名
private:Node* _root;
};

四、紅黑樹插入?

??插入的代碼這里細節(jié)，從搜索二叉樹到AVL樹，都是一樣的。

bool Insert(const pair<T, 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);//判斷k的值是大于還是小于父親的k值if (parent->_kv.first > kv.first){parent->_left = cur;}else{parent->_right = cur;}cur->_parent = parent;}

?約定:cur為當(dāng)前節(jié)點，p為父節(jié)點，g為祖父節(jié)點，u為叔叔節(jié)點

?情況一: cur為紅，p為紅，g為黑，u存在且為紅

?

• ?如果g是根節(jié)點，調(diào)整完成后，需要將g改為黑色
• 如果g是子樹，g一定有雙親，且g的雙親如果是紅色，需要繼續(xù)向上調(diào)整

?情況二: cur為紅，p為紅，g為黑，u不存在/u存在且為黑

?

?說明:u的情況有兩種
1.如果u節(jié)點不存在，則cur一定是新插入節(jié)點，因為如果cur不是新插入節(jié)點則cur和p一定有一個節(jié)點的顏色是黑色，就不滿足性質(zhì)4:每條路徑黑色節(jié)點個數(shù)相同。
2.如果u節(jié)點存在，則其一定是黑色的，那么cur節(jié)點原來的顏色一定是黑色的現(xiàn)在看到其是紅色的原因是因為cur的子樹在調(diào)整的過程中將cur節(jié)點的顏色由黑色改成紅色。
p為g的左孩子，cur為p的左孩子，則進行右單旋轉(zhuǎn);相反p為g的右孩子，cur為p的右孩子，則進行左單旋轉(zhuǎn)p、g變色--p變黑，g變紅

?情況三: cur為

?

while (parent && parent->_col == RED){Node* grandfather = parent->_parent;if (grandfather->_left == parent){Node* uncle = grandfather->_right;// 情況1：u存在且為紅，變色處理，并繼續(xù)往上處理if (uncle && uncle->_col == RED){parent->_col = BLACK;uncle->_col = BLACK;grandfather->_col = RED;// 繼續(xù)往上調(diào)整cur = grandfather;parent = cur->_parent;}else // 情況2+3：u不存在/u存在且為黑，旋轉(zhuǎn)+變色{//     g//   p   u// c if (cur == parent->_left){RotateR(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{//     g//   p   u//     cRotateL(parent);RotateR(grandfather);cur->_col = BLACK;//parent->_col = RED;grandfather->_col = RED;}break;}}else // (grandfather->_right == parent){//    g//  u   p//        cNode* uncle = grandfather->_left;// 情況1：u存在且為紅，變色處理，并繼續(xù)往上處理if (uncle && uncle->_col == RED){parent->_col = BLACK;uncle->_col = BLACK;grandfather->_col = RED;// 繼續(xù)往上調(diào)整cur = grandfather;parent = cur->_parent;}else // 情況2+3：u不存在/u存在且為黑，旋轉(zhuǎn)+變色{//    g//  u   p//        cif (cur == parent->_right){RotateL(grandfather);grandfather->_col = RED;parent->_col = BLACK;}else{//    g//  u   p//    cRotateR(parent);RotateL(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}}_root->_col = BLACK;return true;}

?關(guān)于旋轉(zhuǎn)不懂的，你可以去看之前的C++ AVL樹底層實現(xiàn)原理。關(guān)于驗證紅黑樹，大家感興趣的可以去我碼云看完整代碼！！！