目錄

紅黑樹介紹

紅黑樹的性質(zhì)與平衡控制關(guān)系

紅黑樹節(jié)點(diǎn)的插入

情況1：不需要調(diào)整

情況2：uncle節(jié)點(diǎn)為紅色

情況3：uncle節(jié)點(diǎn)為黑色

總結(jié)與代碼實(shí)現(xiàn)

紅黑樹的刪除（待實(shí)現(xiàn)）

紅黑樹的效率

---

紅黑樹介紹

紅黑樹是第二種平衡二叉搜索樹，為了解決普通二叉搜索樹的效率問題，紅黑樹在控制平衡時選擇近似平衡而不是AVL樹的絕對平衡，每一個節(jié)點(diǎn)都會存儲一個表示顏色的屬性，包括紅色和黑色，通過對顏色的控制，紅黑樹可以保證沒有一條路徑會比其他路徑的長度長出兩倍

紅黑樹的性質(zhì)

1. 根節(jié)點(diǎn)一定是黑色
2. 一條簡單路徑下不會出現(xiàn)連續(xù)的紅色節(jié)點(diǎn)，如果父親節(jié)點(diǎn)為紅色，則其孩子節(jié)點(diǎn)一定為黑色，如果父親節(jié)點(diǎn)為黑色，則沒有限制
3. 對于每個節(jié)點(diǎn)來說，從該節(jié)點(diǎn)開始到其后代所有節(jié)點(diǎn)的簡單路徑上均包含相同數(shù)量的黑色節(jié)點(diǎn)
4. （了解）每個空葉子結(jié)點(diǎn)都是黑色的

在上圖中，NIL表示空葉子節(jié)點(diǎn)，以NIL作為結(jié)束條件，一共有11條路徑，需要注意不是以葉子節(jié)點(diǎn)為結(jié)束條件（即不是7條路徑）

滿足上面的四個性質(zhì)，紅黑樹就可以保證其相對平衡的條件：紅黑樹可以保證最長路徑會比最短路徑的長度長出兩倍。

最短路徑：節(jié)點(diǎn)顏色為全黑的路徑，此時黑色節(jié)點(diǎn)的個數(shù)即為路徑的長度
最長路徑：節(jié)點(diǎn)顏色為紅色和黑色交替出現(xiàn)的路徑

紅黑樹的性質(zhì)與平衡控制關(guān)系

因為黑色節(jié)點(diǎn)的個數(shù)可以決定一條路徑的長度，假設(shè)黑色節(jié)點(diǎn)的個數(shù)為h，則最短路徑的長度也為h，滿足第二條規(guī)則時，紅色節(jié)點(diǎn)的個數(shù)不會超過黑色節(jié)點(diǎn)（1個或者h(yuǎn)個），從而最長路徑的最大長度為2h，因為紅色節(jié)點(diǎn)是在黑色節(jié)點(diǎn)出現(xiàn)后才會出現(xiàn)。

如果按照下圖的插入方式導(dǎo)致紅色節(jié)點(diǎn)連續(xù)出現(xiàn)：

違反了規(guī)則二，此時最短路徑的長度的兩倍會小于最長路徑的長度，從而打破了紅黑樹的平衡。

如果插入的27為黑色節(jié)點(diǎn)，則最長路徑的長度增加，并且黑色節(jié)點(diǎn)的個數(shù)也增加，違反了規(guī)則三，此時對于其他路徑來說也需要增加一個黑色節(jié)點(diǎn)。

所以為了維持平衡，不可以插入黑色節(jié)點(diǎn)，此時最長路徑的長度剛好為2h，如下圖所示：

綜上所述，在滿足第二條規(guī)則和第三條規(guī)則下可以保證紅黑樹的最長路徑始終不會超過最短路徑的2倍

紅黑樹節(jié)點(diǎn)的插入

根據(jù)紅黑樹的性質(zhì)可以看出紅黑樹如何控制高度近似平衡，但是如果插入了節(jié)點(diǎn)，可能會破壞原有的平衡，此時需要通過重新填色或者旋轉(zhuǎn)調(diào)整使紅黑樹重新達(dá)到平衡

在前面的分析中可以得知，如果插入的節(jié)點(diǎn)是黑色節(jié)點(diǎn)，可能會導(dǎo)致每一條路徑都需要多一個黑色節(jié)點(diǎn)，為了更加方便處理，規(guī)定插入的節(jié)點(diǎn)是紅色節(jié)點(diǎn)

情況1：不需要調(diào)整

如果插入的節(jié)點(diǎn)是紅色節(jié)點(diǎn)，并且其父親節(jié)點(diǎn)是黑色節(jié)點(diǎn)，此時不需要進(jìn)行任何處理，當(dāng)父親節(jié)點(diǎn)是黑色節(jié)點(diǎn)時，保證了規(guī)則三沒有違背，因為黑色節(jié)點(diǎn)的個數(shù)決定了高度，插入前如果保證原樹是紅黑樹，那么高度一定滿足紅黑樹的近似平衡，并且此時插入紅色節(jié)點(diǎn)也不會違背規(guī)則二，如下圖的一種情況所示：

情況2：uncle節(jié)點(diǎn)為紅色

如果cur的節(jié)點(diǎn)是紅色，并且其父親節(jié)點(diǎn)（假設(shè)為parent）是紅色節(jié)點(diǎn)，此時說明父親的兄弟節(jié)點(diǎn)（假設(shè)為uncle）也一定為紅色，因為插入前一定是紅黑樹（插入前不是紅黑樹那么插入前就已經(jīng)出現(xiàn)了不平衡，需要進(jìn)行調(diào)整），當(dāng)父親節(jié)點(diǎn)時紅色，說明父親節(jié)點(diǎn)所在的路徑缺少黑色節(jié)點(diǎn)，違反了規(guī)則三。父親節(jié)點(diǎn)的父親節(jié)點(diǎn)（假設(shè)為grandfather）也一定為黑色，如果為紅色則違反了第二條規(guī)則所以插入前的狀態(tài)應(yīng)該為：

cur節(jié)點(diǎn)可能為新增的紅色節(jié)點(diǎn)，也可能為上一次調(diào)整變?yōu)榈募t色節(jié)點(diǎn)

1. 假設(shè)a、b、c、d和e為黑色節(jié)點(diǎn)個數(shù)為0的紅黑樹，此時cur為新插入節(jié)點(diǎn)如下圖所示：

因為出現(xiàn)了連續(xù)的紅色節(jié)點(diǎn)，為了恢復(fù)紅黑樹的平衡，此時需要進(jìn)行調(diào)整，因為uncle節(jié)點(diǎn)為紅色，為了保證每條路徑上都有一個黑色節(jié)點(diǎn)并且保證沒有連續(xù)的紅色節(jié)點(diǎn)出現(xiàn)，將parent節(jié)點(diǎn)的顏色改為黑色，將uncle節(jié)點(diǎn)的顏色改為黑色，將grandfather節(jié)點(diǎn)改為紅色（如果grandfather節(jié)點(diǎn)為根節(jié)點(diǎn)則再處理為黑色），處理完后，cur = grandfather繼續(xù)向上調(diào)整直到遇到根節(jié)點(diǎn)：

對于 uncle為紅色的情況來說，不需要考慮插入位置在 parent左或者右、 parent在 grandfather的左或者右已經(jīng) uncle在 grandfather的左或者右，因為不論是哪種情況，本質(zhì)都是將 uncle和 parent變?yōu)楹谏黾觾蛇吢窂降暮谏?jié)點(diǎn)使其滿足規(guī)則二和規(guī)則三

1. 假設(shè)a、b、c、d和e為黑色節(jié)點(diǎn)個數(shù)大于0，此時cur為上一次調(diào)整變成的紅色節(jié)點(diǎn)，如下圖所示：

對于當(dāng)前情況來說，只有cur位置的節(jié)點(diǎn)是紅色，其余幾棵子樹已經(jīng)通過調(diào)整變成了符合規(guī)則的紅黑樹，所以也可以歸類為上面的情形，處理方式與上面相同

情況3：uncle節(jié)點(diǎn)為黑色

uncle節(jié)點(diǎn)為黑色時一共有兩種情況：

1. uncle節(jié)點(diǎn)不存在
2. uncle節(jié)點(diǎn)存在且為黑

因為紅黑樹規(guī)定下空節(jié)點(diǎn)是黑色的，所以uncle節(jié)點(diǎn)不存在與存在且為黑可以視為一種情況，下面主要以uncle節(jié)點(diǎn)不存在進(jìn)行分析，對于uncle節(jié)點(diǎn)存在且為黑的情況給出一種分析，剩下與uncle節(jié)點(diǎn)不存在的情況類似

下面分析中， uncle節(jié)點(diǎn)不存在時將不展示 NIL節(jié)點(diǎn)

當(dāng)cur節(jié)點(diǎn)在parent的右子樹并且parent在grandfather的右子樹時，并且uncle不存在時，此時需要進(jìn)行左單旋，將parent的顏色更新為黑色，grandfather的顏色更新為紅色，因為如果僅僅是將parent變成黑色，則依舊不滿足規(guī)則三，其余路徑還是少一個黑色節(jié)點(diǎn)，通過左單旋使得當(dāng)前子樹的根節(jié)點(diǎn)變?yōu)楹谏珪r可以使當(dāng)前根節(jié)點(diǎn)出發(fā)的所有路徑都至少有一個黑色節(jié)點(diǎn)，如下圖所示：

當(dāng)cur節(jié)點(diǎn)在parent的左子樹并且parent在grandfather的左子樹時，此時需要進(jìn)行右單旋，將parent的顏色更新為黑色，grandfather的顏色更新為紅色，原因類比左單旋，過程如下圖所示：

當(dāng)cur節(jié)點(diǎn)在parent的右子樹并且parent在grandfather的左子樹時，此時需要進(jìn)行右左雙旋，將cur的顏色更新為黑色，將grandfather的顏色更新為紅色，過程如下：

當(dāng)cur節(jié)點(diǎn)在parent的左子樹并且parent在grandfather的右子樹時，此時需要進(jìn)行左右雙旋，將cur的顏色更新為黑色，將grandfather的顏色更新為紅色，過程如下：

如果uncle節(jié)點(diǎn)本身存在，那么經(jīng)過uncle節(jié)點(diǎn)的路徑下方的兩個子樹為紅色，而parent插入節(jié)點(diǎn)前至少會有一個黑色節(jié)點(diǎn)，如下圖所示：

此時在parent的右側(cè)插入一個cur節(jié)點(diǎn)（本身就是紅色節(jié)點(diǎn)cur節(jié)點(diǎn)也是如此）如下：

此時如果只是對parent節(jié)點(diǎn)的顏色進(jìn)行改變，則會出現(xiàn)parent所在路徑比uncle所在路徑多一個黑色節(jié)點(diǎn)，所以為了解決這個問題，單單改變顏色無法解決，當(dāng)cur在parent的右邊時，只需要一次左單旋即可，而cur在parent的左邊時，需要先進(jìn)行右旋再進(jìn)行左旋，以右左雙旋為例，如下圖所示：

對于其他兩種情況也是一樣的道理，此處不再贅述

總結(jié)與代碼實(shí)現(xiàn)

紅黑樹的插入過程一共有三種情況：

1. 當(dāng)插入節(jié)點(diǎn)的父親節(jié)點(diǎn)為黑色時，直接插入節(jié)點(diǎn)即可，不需要進(jìn)行任何調(diào)整
2. 當(dāng)uncle節(jié)點(diǎn)為紅色時，cur節(jié)點(diǎn)的parent節(jié)點(diǎn)和uncle節(jié)點(diǎn)均變?yōu)楹谏?#xff0c;將所在子樹的根節(jié)點(diǎn)變?yōu)榧t色，如果子樹的根節(jié)點(diǎn)為整棵樹的根節(jié)點(diǎn)，則再處理為黑色
3. 當(dāng)uncle節(jié)點(diǎn)為黑色（包括空節(jié)點(diǎn)的黑色和存在且為黑色節(jié)點(diǎn)）時，需要進(jìn)行旋轉(zhuǎn)
   1. parent和cur節(jié)點(diǎn)是同方向時，進(jìn)行一次旋轉(zhuǎn)（左旋或者右旋），將parent節(jié)點(diǎn)變?yōu)楹谏?#xff0c;將grandfather節(jié)點(diǎn)變?yōu)榧t色，此時因為parent是本棵子樹的根，所以更新完后當(dāng)前子樹也是一棵紅黑樹，顏色是黑色不需要再進(jìn)行調(diào)整
   2. parent和cur節(jié)點(diǎn)不是同方向時，進(jìn)行兩次旋轉(zhuǎn)（先左后右或者先右后左），再將cur節(jié)點(diǎn)變?yōu)楹谏?#xff0c;grandfather節(jié)點(diǎn)變?yōu)榧t色，更新完后當(dāng)前子樹也是一棵紅黑樹，并且因為cur的顏色是黑色不需要再進(jìn)行調(diào)整

代碼實(shí)現(xiàn)：

// 樹插入
bool insertNode(const pair<T, V>& kv)
{// 判斷key是否已經(jīng)存在if (findNode(kv.first)){// 已經(jīng)存在時插入失敗return false;}// 判斷根節(jié)點(diǎn)是否為空，為空則作為第一個節(jié)點(diǎn)if (_root == nullptr){_root = new node(kv);return true;}// 根節(jié)點(diǎn)不為空時接著遍歷插入node* cur = _root;// 定義父親節(jié)點(diǎn)記錄父親的位置node* parent = _root;while (cur){if (kv.first > cur->_kv.first){// 大于根節(jié)點(diǎn)數(shù)據(jù)，插入在右子樹，走到左子樹的空位置parent = cur;cur = cur->_right;}else if (kv.first < cur->_kv.first){// 小于根節(jié)點(diǎn)數(shù)據(jù)，插入在左子樹，走到右子樹的空位置parent = cur;cur = cur->_left;}}// 創(chuàng)建node節(jié)點(diǎn)// 創(chuàng)建節(jié)點(diǎn)可以使用新節(jié)點(diǎn)，但是要使cur走到新節(jié)點(diǎn)的位置，便于下面判斷新節(jié)點(diǎn)的平衡因子，再通過cur判斷祖先節(jié)點(diǎn)的平衡因子cur = new node(kv);// parent為葉子節(jié)點(diǎn)，鏈接新節(jié)點(diǎn)if (parent->_kv.first < kv.first){// 如果是右子樹，則插入在右子樹parent->_right = cur;}else{// 否則插入在左子樹parent->_left = cur;}// 鏈接父親cur->_parent = parent;// 插入節(jié)點(diǎn)顏色為紅色cur->_col = Red;// 存在父親且當(dāng)父親節(jié)點(diǎn)為紅色時需要判斷是否更新while (parent && parent->_parent && parent->_col == Red){node* grandfather = parent->_parent;if (grandfather->_right == parent){node* uncle = grandfather->_left;if (uncle && uncle->_col == Red){// 叔叔存在且為紅uncle->_col = parent->_col = Black;grandfather->_col = Red;cur = grandfather;parent = cur->_parent;}else{// cur在parent的右孩子if (cur == parent->_right){// 右右->左單旋rotateLeft(grandfather);// 改變顏色grandfather->_col = Red;parent->_col = Black;}else{// 右左->右左雙旋rotateRight(parent);rotateLeft(grandfather);cur->_col = Black;grandfather->_col = Red;}// 旋轉(zhuǎn)結(jié)束后不需要再向上更新break;}}else{node* uncle = grandfather->_right;if (uncle && uncle->_col == Red){// 叔叔存在且為紅uncle->_col = parent->_col = Black;grandfather->_col = Red;// 繼續(xù)向上更新cur = grandfather;parent = cur->_parent;}else{if(cur == parent->_left){// 叔叔不存在// 左左->右單旋rotateRight(grandfather);// 改變顏色grandfather->_col = Red;parent->_col = Black;}else{// 左右->左右雙旋rotateLeft(parent);rotateRight(grandfather);// 改變顏色grandfather->_col = Red;cur->_col = Black;}// 旋轉(zhuǎn)結(jié)束后不需要再向上更新break;}}}// 根節(jié)點(diǎn)為黑色_root->_col = Black;return true;
}

紅黑樹的刪除（待實(shí)現(xiàn)）

紅黑樹的效率

紅黑樹和AVL樹都是高效的平衡二叉樹，增刪改查的時間復(fù)雜度都是O()，紅黑樹不追

求絕對平衡，其只需保證最長路徑不超過最短路徑的2倍，相對而言，降低了插入和旋轉(zhuǎn)的次數(shù)，

所以在經(jīng)常進(jìn)行增刪的結(jié)構(gòu)中性能比AVL樹更優(yōu)，而且紅黑樹實(shí)現(xiàn)比較簡單，所以實(shí)際運(yùn)用中紅

黑樹更多