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

---

?

---

前言

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

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

一、紅黑樹的概念

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

1. 每個(gè)結(jié)點(diǎn)不是紅色就是黑色

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

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

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

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

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

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) //為什么默認(rèn)是紅色？根節(jié)點(diǎn)必須是黑色，這就意味著默認(rèn)給黑色那么調(diào)整次數(shù)就會(huì)變多。{}
};

利用節(jié)點(diǎn)這個(gè)類，我們?cè)俣x紅黑樹類 。

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

四、紅黑樹插入?

??插入的代碼這里細(xì)節(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é)點(diǎn)，p為父節(jié)點(diǎn)，g為祖父節(jié)點(diǎn)，u為叔叔節(jié)點(diǎn)

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

?

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

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

?

?說(shuō)明:u的情況有兩種
1.如果u節(jié)點(diǎn)不存在，則cur一定是新插入節(jié)點(diǎn)，因?yàn)槿绻鹀ur不是新插入節(jié)點(diǎn)則cur和p一定有一個(gè)節(jié)點(diǎn)的顏色是黑色，就不滿足性質(zhì)4:每條路徑黑色節(jié)點(diǎn)個(gè)數(shù)相同。
2.如果u節(jié)點(diǎn)存在，則其一定是黑色的，那么cur節(jié)點(diǎn)原來(lái)的顏色一定是黑色的現(xiàn)在看到其是紅色的原因是因?yàn)閏ur的子樹在調(diào)整的過(guò)程中將cur節(jié)點(diǎn)的顏色由黑色改成紅色。
p為g的左孩子，cur為p的左孩子，則進(jìn)行右單旋轉(zhuǎn);相反p為g的右孩子，cur為p的右孩子，則進(jìn)行左單旋轉(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樹底層實(shí)現(xiàn)原理。關(guān)于驗(yàn)證紅黑樹，大家感興趣的可以去我碼云看完整代碼！！！