時間過的好快，我也修煉到紅黑樹了
人世這一遭，何其短暫而漫長啊……
一、AVL樹
1.AVL樹的介紹
1.
雖然二叉搜索樹的搜索效率很高，當(dāng)搜索樹接近滿二叉樹時，搜索效率可以達(dá)到logN，但是如果數(shù)據(jù)是有序的，則二叉搜索樹會退化為單支樹，搜索效率和普通的序列式容器相同了就，所以在搜索樹的基礎(chǔ)上，兩位俄羅斯數(shù)學(xué)家研究出了平衡搜索樹。
2.
平衡搜索樹要求任一結(jié)點(diǎn)的左右子樹的高度差不超過|1|，這個高度差簡稱為平衡因子，balance factor，計(jì)算方式為右子樹高度減左子樹的高度，所以在平衡搜索樹里面任意的一個結(jié)點(diǎn)的平衡因子都是0或1或-1，不會出現(xiàn)2或-2的情況，因?yàn)槠胶馑阉鳂湟笞笥易訕涓叨炔畈怀^|1|。
3.
如果我們保證了一棵搜索樹是平衡搜索樹，那他的價值將會無限放大，因?yàn)樗淖笥易訕涓叨葮O其接近于平衡，他的效率我們可以看作是以2為低的N的對數(shù)，所以假設(shè)有10億個數(shù)，用vector或list查找的次數(shù)最壞就是10億次，但如果我們用平衡搜索樹查找最壞僅僅只是30次，效率之差天壤地別。但該如何將一棵普通的搜索樹調(diào)整為平衡搜索樹呢？實(shí)際上需要不斷連續(xù)的旋轉(zhuǎn)進(jìn)行調(diào)平衡，調(diào)整過程正是今天的主題，也就是搜索樹旋轉(zhuǎn)調(diào)平衡為平衡搜索樹的過程。
2.AVL樹插入的思路
1.
在研究AVL樹結(jié)點(diǎn)插入之前，我們先來看看AVL樹結(jié)點(diǎn)的定義，在AVL樹中結(jié)點(diǎn)不再是二叉鏈結(jié)構(gòu)了，而是變?yōu)槿骀溄Y(jié)構(gòu)，這里需要解釋一下為什么，因?yàn)樵谀晨米訕洳迦虢Y(jié)點(diǎn)之后，如果這棵子樹的高度發(fā)生了變化，那么子樹的上面的根節(jié)點(diǎn)的平衡因子是需要進(jìn)行調(diào)整的，而且得一路向上進(jìn)行調(diào)整，如果不用三叉鏈結(jié)構(gòu)，我們就只能通過parent和cur迭代的方式進(jìn)行向上調(diào)整，過于繁瑣，所以在這個地方AVL樹結(jié)點(diǎn)引入了三叉鏈結(jié)構(gòu)，三叉鏈結(jié)構(gòu)天生就可以打通子樹和根結(jié)點(diǎn)之間的關(guān)聯(lián)，在處理平衡因子上帶來很大的優(yōu)勢。
2.
每一個結(jié)點(diǎn)都應(yīng)該有平衡因子，當(dāng)新增結(jié)點(diǎn)之后平衡因子變?yōu)?或-2時，就已經(jīng)出問題了，平衡因子為2或-2的結(jié)點(diǎn)所在子樹已經(jīng)不滿足AVL樹的性質(zhì)了，此時就需要進(jìn)行旋轉(zhuǎn)調(diào)平衡，那么這時候平衡因子也就不必繼續(xù)向上進(jìn)行調(diào)整了，我們需要處理這棵子樹將其重新調(diào)整為AVL樹。
template <class K, class V>
struct AVLTreeNode
{
pair<K, V> _kv;
AVLTreeNode<K, V>* _left;
AVLTreeNode<K, V>* _right;
AVLTreeNode<K, V>* _parent;
int _bf;// balance factor
AVLTreeNode(const pair<K, V>& kv)
:_kv(kv)
,_left(nullptr)
,_right(nullptr)
,_parent(nullptr)
,_bf(0)
{}
};
3.
AVL樹插入的步驟共分為3步，第一步和搜索樹規(guī)則相同，還是迭代找到插入結(jié)點(diǎn)的位置，進(jìn)行結(jié)點(diǎn)的插入。第二步更新平衡因子，如果平衡因子出現(xiàn)2或-2時更新結(jié)束，我們需要對異常平衡因子對應(yīng)結(jié)點(diǎn)所在的子樹進(jìn)行旋轉(zhuǎn)調(diào)平衡，也有可能平衡因子始終并未出現(xiàn)異常，僅僅只是一直向上更新平衡因子到根節(jié)點(diǎn)為止，更新的過程中整條路徑的結(jié)點(diǎn)的平衡因子均未出現(xiàn)異常，我們就無須進(jìn)行旋轉(zhuǎn)調(diào)平衡處理。第三步對異常平衡因子所在結(jié)點(diǎn)子樹進(jìn)行旋轉(zhuǎn)調(diào)平衡處理，調(diào)平衡的同時我們也要調(diào)平衡因子，讓平衡因子不再異常。當(dāng)然，如果平衡因子并未異常，那么插入結(jié)點(diǎn)就成功，否則就必須得進(jìn)行旋轉(zhuǎn)調(diào)平衡處理，旋轉(zhuǎn)調(diào)平衡這里共分為左單旋，右單旋，左右雙旋，右左雙旋四種情況，下面我會對各種情況進(jìn)行詳細(xì)的講解。
4.
迭代找插入結(jié)點(diǎn)位置進(jìn)行插入我就不講解了，如果有不懂的，可以去看前面二叉搜索樹那一節(jié)的文章，在這里我先來講一講更新平衡因子的過程。
其實(shí)更新的過程也比較簡單，能出現(xiàn)的情況也就三種，一種是在向上更新的過程中平衡因子異常了，我們結(jié)束更新，對異常的這棵子樹進(jìn)行旋轉(zhuǎn)調(diào)平衡處理（如左圖所示）。另一種就是在向上更新的過程中平衡因子一直沒有出現(xiàn)異常，那么我們更新到根節(jié)點(diǎn)就停止，此時也不需要旋轉(zhuǎn)調(diào)平衡處理，直接在AVL樹的insert函數(shù)里return true即可。最后一種就是不用向上更新，為啥不用向上更新呢？比如原來某棵樹結(jié)點(diǎn)的平衡因子是1或-1，在新增結(jié)點(diǎn)過后，平衡因子變?yōu)榱?，此時還需要向上更新嗎？當(dāng)然不用了，因?yàn)檫@棵子樹的高度沒有變化呀！向上更新啥嘛，子樹高度不變，上面樹的高度肯定也不變啊，只要高度不變，我們就無需向上更新平衡因子。
5.
下面我們來談?wù)凙VL樹的重頭戲，也就是旋轉(zhuǎn)調(diào)平衡的過程，先來看看左單旋和右單旋。
在新增結(jié)點(diǎn)之前，這棵樹必須得是AVL樹或AVL子樹，在插入構(gòu)建AVL樹的過程中我們處理的就是非AVL樹的情況，所以在新增結(jié)點(diǎn)之前，子樹一定是AVL樹，所以如果9是新增結(jié)點(diǎn)的話，那么8的左邊就一定是空，這樣才會引發(fā)平衡因子異常。但如果8的左邊不是空，而是一棵子樹，那么9就不可能是新增結(jié)點(diǎn)，因?yàn)槿绻亲訕?的右邊肯定也是一棵子樹，9應(yīng)該是右子樹下邊新增的結(jié)點(diǎn)，如果你要真畫出來所有具體的圖，那這里的情況會非常的多，但其實(shí)無論你的8左邊是否為空，或者8的右子樹根新增結(jié)點(diǎn)還是右子樹的下面新增了一個結(jié)點(diǎn)，最后的情況都是一樣的，你的新增結(jié)點(diǎn)引發(fā)了parent7的平衡因子異常，7的平衡因子變?yōu)?了，那就說明7的右子樹太高了，所以我們旋轉(zhuǎn)將7的右邊連接到subRL上，subR的左鏈接到parent上，subR的parent鏈接到原來parent的parent上面去，這樣我們就把高度降下來了，789的平衡因子都重新調(diào)整為0，這棵子樹就重新調(diào)整為AVL樹，所有的平衡因子都正常了。
右單旋的情況和左單旋類似，是由于新增結(jié)點(diǎn)插入到parent的左邊，然后在向上迭代更新平衡因子的過程中parent的平衡因子變?yōu)榱?2，那就是parent的左子樹太高了，我們需要降低這棵子樹的高度，那就進(jìn)行右單旋，將parent的左鏈接到subLR上subL的右鏈接到parent上，subL的parent鏈接到parent的parent上面去。
這里我在多說一句，下面我們畫的圖是邏輯抽象圖，而不是具體的情況對應(yīng)的圖，因?yàn)榫唧w的情況的圖畫不完的，就拿第一張圖來說，7的左邊可能掛了結(jié)點(diǎn)或子樹，8的左右兩邊都有可能掛著結(jié)點(diǎn)或子樹，但無論你掛了多少結(jié)點(diǎn)或子樹，在新增結(jié)點(diǎn)之前你這棵整體的子樹一定一定一定是AVL樹，那么只要在新增結(jié)點(diǎn)之后，更新平衡因子過程中parent的平衡因子變?yōu)?，那就需要進(jìn)行左單旋來降高度，只要降了高度，789的平衡因子就都會變成0，這一點(diǎn)通過9為新增結(jié)點(diǎn)，8和7的左邊為空這樣的情況就可以說明。
6.
左右雙旋和右左雙旋有點(diǎn)麻煩，因?yàn)樗麄兊恼{(diào)平衡因子過程較為復(fù)雜，而左單旋和右單旋的調(diào)平衡因子過程非常簡單，只需要將parent，subL/subR的平衡因子調(diào)為0就可以，但每個雙旋的平衡因子都有3種情況，所以比較繁瑣。
下面第一張圖片代表的場景是右左雙旋的場景，三種情況雖然都是右左雙旋，但是每種情況的平衡因子的處理是不一樣的，如果是第一行的場景，則只需要把parent和subR的平衡因子都置為0即可，但第如果是第二行的情況，我們在3的左子樹新增結(jié)點(diǎn)時出現(xiàn)了折線型的平衡因子為2的問題，此時依舊是右左雙旋，但是平衡因子的調(diào)節(jié)就有些不一樣了，subRL的平衡因子變?yōu)?，因?yàn)閟ubRL做根，parent在左旋時鏈接了新增在3左子樹的結(jié)點(diǎn)，所以parent的平衡因子變?yōu)?，subR鏈接到3的右邊也就是空，那么subR的平衡因子就被調(diào)整為1.當(dāng)情況是第三行時，調(diào)節(jié)平衡因子如圖所示，這里不再過多贅述，雙旋的平衡因子調(diào)節(jié)主要還是跟著圖走。
補(bǔ)充一點(diǎn)：右左雙旋時，先以subR為軸進(jìn)行左單旋，然后再以parent為軸進(jìn)行右單旋。在調(diào)節(jié)平衡因子時，我們需要判斷subRL是自己新增還是左子樹新增或是右子樹新增，這里的判斷方式通過subRL的平衡因子就可以分辨出來，如果是0，那就是自己新增，如果是1那就是右子樹新增，如果是-1那就是左子樹新增。通過這三種情況，分別對子樹的平衡因子進(jìn)行調(diào)整處理。
當(dāng)情況變?yōu)樽笳劬€式的平衡因子異常問題，我們就需要采用左右雙旋的方式進(jìn)行解決，先以subL為軸點(diǎn)進(jìn)行左單旋，再以parent為軸進(jìn)行右單旋，這樣就完成了旋轉(zhuǎn)調(diào)平衡的過程。與右左雙旋相同的是對于平衡因子的調(diào)節(jié)同樣要分為三種情況，這里不再繼續(xù)贅述，下面圖片闡述的很清楚。
3.AVL樹插入的代碼（死亡三部曲）
1.
第一步：插入結(jié)點(diǎn)并完成結(jié)點(diǎn)的鏈接過程
這個步驟的實(shí)現(xiàn)和二叉搜索樹一樣，如果_root是空，我們就new一個結(jié)點(diǎn)，把結(jié)點(diǎn)地址給到_root，讓_root指向這個結(jié)點(diǎn)，這個結(jié)點(diǎn)就是AVL樹的根節(jié)點(diǎn)，然后直接返回true。如果_root不是空，那就根據(jù)搜索樹結(jié)構(gòu)特征，用while循環(huán)向下迭代找插入結(jié)點(diǎn)的位置，注意向下迭代找插入結(jié)點(diǎn)的過程中，不僅僅只需要一個cur指針，如果僅有cur一個指針，我們是無法將new出來的結(jié)點(diǎn)鏈接到樹上面的，因?yàn)閏ur只是一個局部變量，無法改變函數(shù)外面樹的結(jié)點(diǎn)的鏈接關(guān)系，所以我們還需要一個局部變量parent，在cur向下迭代之前把其地址給到parent，那么等到cur迭代到正確插入結(jié)點(diǎn)的位置時，我們通過局部指針parent，就能操縱外面樹對應(yīng)根節(jié)點(diǎn)的左右指針，但外面的根節(jié)點(diǎn)還是一樣，我們無法通過parent操縱，然后把new出來的結(jié)點(diǎn)地址給到cur，再把cur鏈接到parent上，此時不能通過parent的左右哪個為空，我們就把cur鏈接到哪個上面去，因?yàn)閜arent的左右都有可能為空，所以還需要進(jìn)行cur里面的kv鍵值對和parent里面的kv鍵值對的first之間再進(jìn)行一次比較，這樣才能判斷出cur究竟要插入到parent的左右哪個位置上去。插入結(jié)點(diǎn)之后，還有一件事需要去做，因?yàn)槲覀兊腁VL樹結(jié)點(diǎn)是三叉鏈結(jié)構(gòu)，所以cur結(jié)點(diǎn)里的_parent指針還需要指定它的指向，否則cur結(jié)點(diǎn)沒有父親了，所以處理完parent的左右指針過后，還需要再處理一次cur的_parent指針。
2.
第二步：更新平衡因子
更新平衡因子的過程，在上面思路部分我也做了詳細(xì)的說明，下面就是將思路轉(zhuǎn)換為代碼的具體實(shí)現(xiàn)。首先需要解決的問題是如何更新平衡因子？如果插入的結(jié)點(diǎn)是parent的左，那就是parent的左樹高了，parent的平衡因子就應(yīng)該- -，如果插入的結(jié)點(diǎn)是parent的右，parent的平衡因子就應(yīng)該++，此時就需要看parent平衡因子的值了，如果是1或-1，則繼續(xù)向上讓cur和parent迭代更新平衡因子，如果是0則說明parent子樹的高度沒有改變無須向上更新，就該停下來了。其他情況就是如果平衡因子出現(xiàn)2或-2則也該停下來了，因?yàn)槲覀円獙ζ溥M(jìn)行"治療"，也就是旋轉(zhuǎn)調(diào)平衡的過程，通過parent和cur的平衡因子的不同，又可以細(xì)分為4種"治療手段"。最后如果cur更新到_root的位置就需要跳出循環(huán)了，parent此時為nullptr結(jié)束循環(huán)。
template <class K, class V>
class AVLTree
{
typedef AVLTreeNode<K, V> Node;
public:
bool Insert(const pair<K, V>& kv)
{
//兩步:1.找插入結(jié)點(diǎn)位置進(jìn)行結(jié)點(diǎn)插入 2.更新平衡因子
if (_root == nullptr)
{
_root = new Node(kv);
}
//1.找插入結(jié)點(diǎn)位置進(jìn)行結(jié)點(diǎn)的插入
Node* cur = _root;
Node* parent = nullptr;
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);
if (parent->_kv.first > cur->_kv.first)
{
parent->_left = cur;
cur->_parent = parent;
}
else
{
parent->_right = cur;
cur->_parent = parent;
}
//2.更新平衡因子
while (parent)//最極端場景就是更新到根節(jié)點(diǎn)位置
{
if (cur == parent->_left)
parent->_bf--;
else
parent->_bf++;
if (parent->_bf == 0)
break;
if (parent->_bf == 1 || parent->_bf == -1)
{
cur = parent;
parent = cur->_parent;
}
else if (parent->_bf == 2 || parent->_bf == -2)
{
//旋轉(zhuǎn)調(diào)平衡
if (parent->_bf == 2 && cur->_bf == 1)
{
//左單旋
RotateL(parent);
}
else if (parent->_bf == -2 && cur->_bf == -1)
{
//右單旋
RotateR(parent);
}
else if (parent->_bf == 2 && cur->_bf == -1)
{
//右左雙旋
RotateRL(parent);
}
else if (parent->_bf == -2 && cur->_bf == 1)
{
//左右雙旋
RotateLR(parent);
}
else
{
//若出現(xiàn)不可預(yù)料的情況，直接斷死
assert(false);
}
break;//旋轉(zhuǎn)結(jié)束，跳出循環(huán)
}
else//若出現(xiàn)不可預(yù)料的情況，直接斷死
{
assert(false);
}
}
}
3.
第三步：旋轉(zhuǎn)調(diào)平衡
在調(diào)平衡這個地方，一定要注意對著圖來進(jìn)行操作，否則很容易出問題。
如果是單旋的代碼： 需要注意的就是三叉鏈這種特殊結(jié)構(gòu)的處理，他就像是雙向循環(huán)鏈表一樣，你新鏈接結(jié)點(diǎn)時，不僅要處理新節(jié)點(diǎn)的左和右指針指向，新節(jié)點(diǎn)左右結(jié)點(diǎn)的一個指針指向你也要處理呀，所以代碼對數(shù)就應(yīng)該是兩對兒：新節(jié)點(diǎn)的左指針指向，左指針指向結(jié)點(diǎn)的右指針指向。新節(jié)點(diǎn)的右指針指向，右指針指向結(jié)點(diǎn)的左指針指向。
在AVL樹這里那最多代碼對兒數(shù)就應(yīng)該是三對兒（這里只拿左單旋舉例子，右單旋類似，反過來即可），parent的_right指針和subRL的_parent指針，當(dāng)然這里需要判斷subRL是否存在，如果存在那就需要更改subRL的_parent指針，不存在就不需要管了。parent的_parent指針和subR的_left指針。subR的_parent指針，和上面那個結(jié)點(diǎn)的左或右指針，當(dāng)然上面可能不存在，那subR就變成了根節(jié)點(diǎn)，我們需要更新一下_root的指向，從原來指向parent更新到現(xiàn)在指向subR結(jié)點(diǎn)，如果上面存在那就需要更改上面結(jié)點(diǎn)的左或右指針，從原來的指向parent結(jié)點(diǎn)到現(xiàn)在指向的subR結(jié)點(diǎn)。最后調(diào)整一下平衡因子，單旋的平衡因子最好調(diào)了，將parent和parent的左或右結(jié)點(diǎn)的平衡因子都調(diào)成0就OK了。
//3.左單旋，右單旋，左右雙旋，右左雙旋
void RotateL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
Node* pParent = parent->_parent;
//AVL樹這樣的三叉鏈結(jié)構(gòu)，調(diào)整一個結(jié)點(diǎn)對另一個結(jié)點(diǎn)的指向，另外一個結(jié)點(diǎn)的指向也需要調(diào)整指向?qū)γ娴慕Y(jié)點(diǎn)上去，他是雙向的。
parent->_right = subRL;//調(diào)整parent向下的指向，下面是有可能調(diào)整subRL向上的指向
if (subRL)
subRL->_parent = parent;
parent->_parent = subR;//調(diào)整parent向上的指向，下面就得調(diào)整subR向下的指向
subR->_left = parent;
subR->_parent = pParent;//調(diào)整了subR向上的指向，下面就得調(diào)整上面對subR的指向。
if (pParent == nullptr)
_root = subR;//如果parent恰好指向根節(jié)點(diǎn)，并且parent指向結(jié)點(diǎn)的bf為2或-2，則此時就需要換根結(jié)點(diǎn)指針的地址了
else
{
if (parent == pParent->_left)
pParent->_left = subR;
else
pParent->_right = subR;
}
//重新調(diào)整平衡因子
parent->_bf = subR->_bf = 0;
}
void RotateR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
Node* pParent = parent->_parent;
parent->_left = subLR;
if (subLR)
subLR->_parent = parent;
parent->_parent = subL;
subL->_right = parent;
subL->_parent = pParent;
if (pParent == nullptr)
_root = subL;
else
{
if (pParent->_left == parent)
pParent->_left = subL;
else
pParent->_right = subL;
}
//調(diào)整平衡因子
parent->_bf = subL->_bf = 0;
}
如果是雙旋的代碼： 旋轉(zhuǎn)的代碼其實(shí)并不需要我們怎么寫，我們直接復(fù)用左右單旋的代碼即可，但在傳參時要注意軸點(diǎn)的位置變化，拿右左雙旋來舉例，軸點(diǎn)先為subR后為parent。其實(shí)雙旋代碼的關(guān)鍵在于平衡因子的調(diào)整，但只要有圖，害，平衡因子的調(diào)整算個啥嘛！那不輕輕松松就調(diào)節(jié)好了？所以在單旋之前先記錄一下subRL的平衡因子，否則單旋過后subRL的平衡因子都被處理成0了，我們無法區(qū)分調(diào)節(jié)平衡因子的三種情形了。記錄平衡因子之后，我們就可以分三種情況對parent subR subRL的平衡因子進(jìn)行處理了，處理過后雙旋的代碼也就結(jié)束了。
所以在雙旋代碼這里可以看到，它主要的難點(diǎn)不是旋轉(zhuǎn)，因?yàn)樾D(zhuǎn)我們調(diào)用單旋復(fù)用代碼就可以處理了，真正的難點(diǎn)是在平衡因子的調(diào)節(jié)這塊兒，他又分了三種情況。
void RotateLR(Node* parent)
{
//這里比較難的一個點(diǎn)實(shí)際上是雙旋之后的平衡因子的調(diào)整
Node* subL = parent->_left;
Node* subLR = subL->_right;
int bf = subLR->_bf;// 單旋過后，subLR的平衡因子會被改變，提前記錄一下平衡因子
RotateL(parent->_left);
RotateR(parent);
if (bf == 0)// subLR本身就是新增
{
subL->_bf = subLR->_bf = parent->_bf = 0;
}
else if(bf == 1)// subLR的右子樹進(jìn)行新增
{
subL->_bf = -1;
subLR->_bf = parent->_bf = 0;
}
else if (bf == -1)// subLR的左子樹進(jìn)行新增
{
parent->_bf = 1;
subLR->_bf = subL->_bf = 0;
}
else
{
//若出現(xiàn)不可預(yù)料的情況，直接斷死
assert(false);
}
}
void RotateRL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
int bf = subRL->_bf;
RotateR(parent->_right);
RotateL(parent);
if (bf == 0)
{
parent->_bf = subR->_bf = subRL->_bf = 0;
}
else if (bf == 1)
{
parent->_bf = -1;
subR->_bf = subRL->_bf = 0;
}
else if (bf == -1)
{
subR->_bf = 1;
parent->_bf = subRL->_bf = 0;
}
else
{
assert(false);
}
}
4.AVL樹的驗(yàn)證
1.
寫完AVL樹之后，我們還需要寫一個程序?qū)VL樹進(jìn)行驗(yàn)證，要不然你說你的樹是AVL樹他就是AVL樹?。∪f一你寫錯了呢？所以寫完AVL樹的插入之后，還需要再對其進(jìn)行驗(yàn)證，看是否滿足AVL樹的條件。
2.
雖然AVL樹的插入比較棘手，插入結(jié)點(diǎn)后又得更新平衡因子，平衡因子出問題之后，又得旋轉(zhuǎn)調(diào)平衡把樹的高度降下來，除降高度外，又得把異常的平衡因子重新調(diào)為正常。
對于單旋雖然在旋轉(zhuǎn)代碼處理上細(xì)節(jié)比較多，但平衡因子的重新調(diào)整還不算麻煩，比較簡單。而對于雙旋那簡直就惡心死了，光調(diào)節(jié)平衡因子還分為三種情況，調(diào)來調(diào)去頭疼死了。
但有一說一，AVL樹的驗(yàn)證是真的簡單，這總算能平衡一下受傷的心靈了，紅黑樹那里是插入不簡單，驗(yàn)證還挺難，哈哈哈，更加棘手。
3.
在驗(yàn)證這里，我們分兩個方向?qū)ζ溥M(jìn)行驗(yàn)證，通過中序遍歷的結(jié)果看其是否先滿足搜索樹，如果遍歷結(jié)果不是升序，那就別說AVL樹了，連搜索樹他都夠嗆。
然后通過AVL樹的規(guī)則對其驗(yàn)證，每一個結(jié)點(diǎn)的右子樹 - 左子樹的高度差的絕對值不超過1。這里我們就需要寫一個遞歸，先遞歸根，再分別遞歸左子樹和右子樹，保證任意一棵子樹的左右高度差不超過1，所以還需要多寫一個求高度的遞歸算法，這個算法也簡單，左右子樹高度較大的那個再+1就是樹的高度。
中序和測試左右高度差的代碼通過后，就可以說明當(dāng)前樹的確是一棵AVL樹。
void InOrder()
{
_InOrder(_root);
}
int Height(Node* root)
{
if (root == nullptr)
return 0;
return Height(root->_left) > Height(root->_right) ? Height(root->_left) + 1 : Height(root->_right) + 1;
}
bool IsBalance()
{
return _IsBalance(_root);
}
private:
bool _IsBalance(Node* root)
{
if (root == nullptr)// 空樹也算作平衡樹
return true;
int leftHeight = Height(root->_left);
int rightHeight = Height(root->_right);
if (rightHeight - leftHeight != root->_bf)//順便做的一件事
{
cout << root->_kv.first << ":" << "平衡因子異常" << endl;
return false;
}
return abs(leftHeight - rightHeight) < 2 && _IsBalance(root->_left) && _IsBalance(root->_right);
}
void _InOrder(Node* _root)
{
if (_root == nullptr)
return;
_InOrder(_root->_left);
cout << _root->_kv.first << ":" << _root->_kv.second << endl;
_InOrder(_root->_right);
}
Node* _root = nullptr;
};
二、紅黑樹
1.紅黑樹的介紹
1.
在實(shí)際應(yīng)用中，AVL樹用的很少，反而紅黑樹卻名聲在外，聲明遠(yuǎn)揚(yáng)，被用的最多。其實(shí)就是因?yàn)锳VL樹的規(guī)則過于嚴(yán)苛，導(dǎo)致稍微插入一些結(jié)點(diǎn)就有可能違反了AVL樹的規(guī)則，我們就需要通過旋轉(zhuǎn)調(diào)平衡進(jìn)行處理，但旋轉(zhuǎn)調(diào)平衡是有代價的啊，如果插入結(jié)點(diǎn)就調(diào)平衡，插入節(jié)點(diǎn)就調(diào)平衡，自然AVL樹的效率就下來了，所以為了減少AVL樹多次的旋轉(zhuǎn)導(dǎo)致的效率降低問題，重新設(shè)定規(guī)則進(jìn)而產(chǎn)生了紅黑樹。
2.
紅黑樹有5條重要的性質(zhì)，但最有用的就是其中的第c和d條。
a.紅黑樹的節(jié)點(diǎn)不是紅色就是黑色
b.紅黑樹的根節(jié)點(diǎn)必須是黑色
c.紅黑樹從當(dāng)前根節(jié)點(diǎn)到每條路徑上的黑色節(jié)點(diǎn)數(shù)量都相同。
d.紅色節(jié)點(diǎn)的左右孩子必須是黑色
e.每個葉子節(jié)點(diǎn)的顏色都是黑色的（此處的葉子節(jié)點(diǎn)是指空節(jié)點(diǎn)，這可以幫助我們更好的分辨出每一條路徑）
3.
在上面的5條規(guī)則控制下，紅黑樹的最長路徑不超過最短路徑的2倍，因而紅黑樹是近似于平衡的，即使紅黑樹的最長路徑是二倍，他的搜索效率也非常的高，如果說AVL樹的搜索時間復(fù)雜度最壞是logN，那么紅黑樹最壞的搜索時間復(fù)雜度也僅僅是2倍的logN而已，比如查找10億個數(shù)，AVL樹最壞需要查找30次，而紅黑樹最壞需要查找60次，但30次和60次對于CPU來說那可以直接忽略，CPU每秒計(jì)算50億次呢，你這30或60次簡直太小了。所以紅黑樹的搜索效率和AVL樹可以近似看作相等，但是紅黑樹不需要那么多的旋轉(zhuǎn)來調(diào)平衡，因?yàn)榧t黑樹可以允許最長路徑是最短路徑的2倍，他的要求并沒有AVL樹那么嚴(yán)格，所以紅黑樹的旋轉(zhuǎn)次數(shù)要比AVL樹少很多，效率自然就提升了，故而實(shí)際應(yīng)用中紅黑樹要比AVL樹用的更多一些。
反過頭來我們再思考一下，為什么保證紅黑樹的那幾條規(guī)則以后，紅黑樹的最長路徑可以是最短路徑的二倍呢？他要求根節(jié)點(diǎn)的每條路徑的黑色節(jié)點(diǎn)的數(shù)量必須相同，并且不允許出現(xiàn)連續(xù)的紅色節(jié)點(diǎn)，所以最長路徑的情形就是黑色節(jié)點(diǎn)和紅色節(jié)點(diǎn)交替出現(xiàn)，最短路徑就只有黑色結(jié)點(diǎn)，此時最長路徑就恰好是最短路徑的二倍。
2.紅黑樹插入的思路
1.
先來看一眼紅黑樹結(jié)點(diǎn)的定義，其實(shí)紅黑樹結(jié)點(diǎn)和AVL樹結(jié)點(diǎn)很相似，唯一不同的就是紅黑樹把AVL樹結(jié)點(diǎn)的平衡因子換做了枚舉常量，枚舉常量就是enum color定義的，顏色只包括RED和BLACK。
new結(jié)點(diǎn)調(diào)用RBTreeNode的構(gòu)造函數(shù)時，我們默認(rèn)結(jié)點(diǎn)的顏色為紅色，這里要解釋一下為什么結(jié)點(diǎn)的默認(rèn)顏色為紅色。首先插入結(jié)點(diǎn)是有可能違反紅黑樹的規(guī)則的，如果違反了規(guī)則，我們就需要對紅黑樹進(jìn)行"治療"，首先如果插入結(jié)點(diǎn)是黑色，則一定會違反紅黑樹的第4條規(guī)則，因?yàn)槟闫桨谉o故在某條路徑上多加了一個黑色結(jié)點(diǎn)，其他路徑就應(yīng)該都多加一個黑色結(jié)點(diǎn)才能治療紅黑樹，這樣解決的成本太大了。但如果你插入的是紅色結(jié)點(diǎn)，如果紅色結(jié)點(diǎn)的父親是紅色，那紅黑樹也出問題了，也需要治療，但如果紅色節(jié)點(diǎn)的父親是黑色，那紅黑樹就沒有出問題，我們就不需要治療，而且就算治療，成本也不大，只要修改紅色節(jié)點(diǎn)附近的路徑就可以了，而插入黑色結(jié)點(diǎn)修改的可是整棵樹的所有路徑。所以綜合分析來看，默認(rèn)構(gòu)造的結(jié)點(diǎn)顏色為紅色對我們最有優(yōu)勢。
enum color
{
RED,
BLACK
};
template <class K, class V>
struct RBTreeNode
{
pair<K, V> _kv;
RBTreeNode<K, V>* _left;
RBTreeNode<K, V>* _right;
RBTreeNode<K, V>* _parent;
enum color _col;
RBTreeNode(const pair<K,V> kv)
:_kv(kv)
,_left(nullptr)
,_right(nullptr)
,_parent(nullptr)
,_col(RED)
// 1.默認(rèn)構(gòu)造結(jié)點(diǎn)的顏色為紅色，如果是黑色肯定會出事，因?yàn)橐蟾?jié)點(diǎn)到所有葉子結(jié)點(diǎn)路徑上的黑色結(jié)點(diǎn)數(shù)量都相同，違反規(guī)則了
// 影響了所有的路徑，非常不好處理。
// 2.但如果是紅色就好多了，有可能出事，出事我們調(diào)整就好了，如果不出事那更好了。
{}
};
2.
紅黑樹的插入整體思路其實(shí)就兩步，比AVL樹的思路簡潔一些，第一步還是和二叉搜索樹一樣，這里不再贅述，第二步主要就是看parent的顏色，如果parent的顏色為紅色，我們才需要進(jìn)行治療，或者parent為空，代表我們插入的結(jié)點(diǎn)是根節(jié)點(diǎn)，那就需要強(qiáng)制將結(jié)點(diǎn)顏色改為黑色，因?yàn)榧t黑樹要求根節(jié)點(diǎn)必須為黑色。
3.
治療的情形有三種，處理關(guān)鍵在于uncle的顏色是紅色還是黑色。
情況1： cur是新增的紅色結(jié)點(diǎn)，其parent為紅色則需要治療這棵紅黑樹，如果uncle存在且為紅色則只需要讓parent和uncle顏色改為黑色，grandparent顏色先改為紅色，如果你不改為紅色，那么這兩條路徑就平白無故的多加了兩個黑色結(jié)點(diǎn)，勢必違反了紅黑樹的第四條規(guī)則，所以需要繼續(xù)判斷grandparent的parent顏色，如果grandparent的parent顏色為黑，則無須繼續(xù)治療，因?yàn)橐呀?jīng)治療完畢，相當(dāng)于把根節(jié)點(diǎn)的黑色平坦到兩條路徑下面，讓根節(jié)點(diǎn)顏色變?yōu)榱思t色，但如果randparent的parent顏色為紅，那還需要繼續(xù)對紅黑樹繼續(xù)治療，再次治療有可能出現(xiàn)下面三種情況的任意一種，可能是情況1，如果是情況1，則上一層的uncle左右不可能為空，因?yàn)槿绻麨榭眨谛略黾t色結(jié)點(diǎn)之前這棵樹就不是紅黑樹。除我們所說的上面這兩大種情況之外，還有第三種情況，那就是grandparent是根節(jié)點(diǎn)，此時我們就不需要判斷他的parent結(jié)點(diǎn)顏色了，直接強(qiáng)制將grandparent的顏色改為黑色即可。
情況2： 情況2一定是由情況1變上來的，否則如果cur是新增紅色，那原來的樹就不是紅黑樹了，違反了第四條規(guī)則，所以情況2一定是由情況1變上來的。治療情況2的問題也比較簡單，只需要以grandparent為軸進(jìn)行右單旋并且交換grandparent和parent的顏色即可，這樣就可以治療紅黑樹。具體右單旋的細(xì)節(jié)和AVL樹一樣，只是紅黑樹不需要調(diào)節(jié)平衡因子，僅僅只需要旋轉(zhuǎn)+變色就可以，這里不再多說右單旋的細(xì)節(jié)。
情況3： 情況3就是我們之前AVL樹所說的雙旋情況，這種情況也一定是由情況1變過來的，道理相同，如果不是情況1變過來的，那cur就是新增，如果是新增，原來的樹就不是紅黑樹了，那就出問題了，所以情況3也一定是由情況1變過來的。
在治療這種問題上，可以先以parent為軸進(jìn)行左單旋，只要左單旋過后，情況3就轉(zhuǎn)變?yōu)榱饲闆r2，此時我們只需要以grandparent為軸進(jìn)行右單旋+交換grandparent和cur的顏色即可治療完成紅黑樹。
情況23的uncle不存在： 有心的老鐵肯定發(fā)現(xiàn)了我在情況23的后面寫了uncle不存在，通過上面所說的情況23的處理大家就可以發(fā)現(xiàn)，uncle存在或者不存在對情況23有影響嗎？無論你存不存在，該右單旋+變色還得右單旋+變色，該先左后右單旋+變色還得先左后右單旋+變色，而且變色的結(jié)點(diǎn)和uncle有關(guān)系嗎？當(dāng)然沒有關(guān)系！所以直接把這種情況歸到23里面了就，所以整體的情況就是單旋+變色和雙旋+變色以及第一種情況，uncle存不存在都不重要。
4.
為了給大家解釋一下，情況2和3一定是由情況1變上來的，我下面畫了兩種圖的情況，分別對應(yīng)了右單旋+變色和先左后右單旋+變色的情況，并且在旋轉(zhuǎn)+變色處理之后紅黑樹一定治療成功了。下面的圖解釋的很清楚，我也就不廢話了，老鐵們可以看一下這兩個圖。
5.
其實(shí)上面所說的情況只是紅黑樹的一半的情況，但只要會這一半，另一半就是反過來的，比如parent不是grandparent的左，而是grandparent的右，如果此時cur是parent的右，那就是左單旋+變色，如果是parent的左，那就是先右單旋后左單旋+變色，思路僅僅只是上面那三種情況的反面，由于在AVL樹的部分左右單旋和雙旋的情況我已經(jīng)畫的非常通透了，在紅黑樹這里我只畫一面的情況，剩下的另一面兄弟們照貓畫虎肯定也能畫出來，所以在紅黑樹思路這個部分，我們只拿一面進(jìn)行思路的講解，另一面交給大家了。
3.紅黑樹插入的代碼（關(guān)鍵是uncle）
1.
紅黑樹插入代碼的第一部分還是和二叉搜索樹一樣，不再細(xì)說。
第二步就是針對cur的parent顏色為紅色搞一個while循環(huán)，因?yàn)槲覀冇锌赡軙蛏线M(jìn)行紅黑樹的治療，但while循環(huán)除這個條件外，還有一個容易忽略的點(diǎn)，就是治療到根位置就結(jié)束治療了，也就是parent == nullptr的時候，while循環(huán)也該結(jié)束了，或者parent顏色為黑色時while循環(huán)也該結(jié)束了，我們想的是循環(huán)結(jié)束的條件，寫的是循環(huán)繼續(xù)的條件，所以要用邏輯與而不是邏輯或。
跳出while循環(huán)可能是因?yàn)榍闆r1想上變到根結(jié)點(diǎn)了，然后迭代之后cur到了root的位置，parent到了nullptr的位置，此時我們需要強(qiáng)制將root指向結(jié)點(diǎn)的顏色改為黑色，所以在while循環(huán)的外面，我們直接斷死根節(jié)點(diǎn)顏色為黑色，不去判斷while循環(huán)是由于什么條件而結(jié)束的，直接斷死根節(jié)點(diǎn)顏色是黑色即可。
2.
while循環(huán)內(nèi)部，總體也是分兩面，一面是parent為grandparent的左，另一面是parent為grandparent的右，這兩面的內(nèi)部同樣都分為三種情況，cur和parent位置的迭代是要放在第一種情況的，因?yàn)榈谝淮涡略黾t色結(jié)點(diǎn)是不可能出現(xiàn)23種情況的，只可能出現(xiàn)uncle存在且為紅的情況，在第一種情況處理過后，我們才需要進(jìn)行cur和parent位置的迭代，下一步進(jìn)行判斷是否有可能為23種情況或者是再次為第一種情況，如果是23種情況的任意一種，在處理之后我們直接break即可，因?yàn)榇藭r紅黑樹治療工作已經(jīng)完成了。至于紅黑樹結(jié)點(diǎn)顏色的調(diào)節(jié)，大家可以對照上面我畫的圖進(jìn)行顏色的改變，這個很簡單，這里也不再多說了。
template <class K, class V>
class RBTree
{
typedef RBTreeNode<K, V> Node;
public:
bool Insert(const pair<K, V>& kv)
{
Node* parent = nullptr;
Node* cur = _root;
if (_root == nullptr)
{
_root = new Node(kv);
_root->_col = BLACK;
return true;
}
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);
if (parent->_kv.first > kv.first)
{
parent->_left = cur;
cur->_parent = parent;//這種三叉鏈的結(jié)構(gòu)一定要小心，在鏈接的時候，時刻注意雙向的性質(zhì)，我鏈接你，你鏈接我
}
else
{
parent->_right = cur;
cur->_parent = parent;
}
// 只要插入結(jié)點(diǎn)之后，parent為紅，此時違反紅黑樹規(guī)則，那我們就要對其進(jìn)行調(diào)整，parent有可能為root的parent->nullptr
while (parent && parent->_col == RED)
{
Node* grandparent = parent->_parent;
if (parent == grandparent->_left)
{
Node* uncle = grandparent->_right;
//情況1.uncle存在且為紅
if (uncle && uncle->_col == RED)
{
parent->_col = uncle->_col = BLACK;
grandparent->_col = RED;
cur = grandparent;
parent = cur->_parent;// 如果grandparent是根，則parent是空
}
//情況2.uncle不存在或uncle為黑 -- 右單旋+變色
else if (cur == parent->_left)
{
// g
// p
// c
RotateR(grandparent);
grandparent->_col = RED;
parent->_col = BLACK;
break;
}
//情況3.uncle不存在或uncle為黑 -- 左右雙旋+變色
else if (cur == parent->_right)
{
// g
// p
// c
RotateL(parent);
RotateR(grandparent);
cur->_col = BLACK;
grandparent->_col = RED;
break;
}
else
{
assert(false);
}
}
else// parent == grandparent->_right;
{
Node* uncle = grandparent->_left;
if (uncle && uncle->_col == RED)
{
grandparent->_col = RED;
uncle->_col = parent->_col = BLACK;
cur = grandparent;
parent = cur->_parent;
}
//uncle存在或?yàn)楹谏奶幚砬闆r都是下面兩種處理方式，通過cur在parent的左還是右，看處理方式是單旋還是雙旋即可，
//uncle存在或者不存在都是不重要的
//情況2.進(jìn)行左單旋+變色
else if (cur == parent->_right)
{
// g
// p
// c
RotateL(grandparent);
parent->_col = BLACK;
grandparent->_col = RED;
break;
}
//情況3.右左雙旋+變色
else if (cur == parent->_left)
{
// g 黑
// p 紅
// c 紅
RotateR(parent);
RotateL(grandparent);
cur->_col = BLACK;
grandparent->_col = RED;
break;
}
else
{
assert(false);
}
}
}
_root->_col = BLACK;
// 有可能parent為root的parent也就是nullptr時，跳出循環(huán)之后root可能顏色為紅色，所以我們在while外面直接斷死根節(jié)點(diǎn)為黑色
return true;
}
3.
下面放的是AVL樹的左右單旋代碼，唯一做出的修改就是將調(diào)節(jié)平衡因子的代碼進(jìn)行了刪除，所以紅黑樹這里的旋轉(zhuǎn)和AVL樹并無差別，在有了AVL樹旋轉(zhuǎn)的基礎(chǔ)之后，紅黑樹的旋轉(zhuǎn)+變色就好理解多了。
void RotateL(Node * parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
Node* pParent = parent->_parent;
//AVL樹這樣的三叉鏈結(jié)構(gòu)，調(diào)整一個結(jié)點(diǎn)對另一個結(jié)點(diǎn)的指向，另外一個結(jié)點(diǎn)的指向也需要調(diào)整指向?qū)γ娴慕Y(jié)點(diǎn)上去，他是雙向的。
parent->_right = subRL;//調(diào)整parent向下的指向，下面是有可能調(diào)整subRL向上的指向
if (subRL)
subRL->_parent = parent;
parent->_parent = subR;//調(diào)整parent向上的指向，下面就得調(diào)整subR向下的指向
subR->_left = parent;
subR->_parent = pParent;//調(diào)整了subR向上的指向，下面就得調(diào)整上面對subR的指向。
if (pParent == nullptr)
_root = subR;//如果parent恰好指向根節(jié)點(diǎn)，并且parent指向結(jié)點(diǎn)的bf為2或-2，則此時就需要換根結(jié)點(diǎn)指針的地址了
else
{
if (parent == pParent->_left)
pParent->_left = subR;
else
pParent->_right = subR;
}
}
void RotateR(Node * parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
Node* pParent = parent->_parent;
parent->_left = subLR;
if (subLR)
subLR->_parent = parent;
parent->_parent = subL;
subL->_right = parent;
subL->_parent = pParent;
if (pParent == nullptr)
_root = subL;
else
{
if (pParent->_left == parent)
pParent->_left = subL;
else
pParent->_right = subL;
}
}
4.紅黑樹的驗(yàn)證
1.
紅黑樹的驗(yàn)證相比AVL樹就復(fù)雜的多了，我們需要對紅黑樹的三個部分進(jìn)行驗(yàn)證，首先利用中序遍歷觀察是否滿足搜索樹，還需要驗(yàn)證紅黑樹中不能出現(xiàn)連續(xù)的紅色結(jié)點(diǎn)，最后還需要保證每條路徑的黑色結(jié)點(diǎn)數(shù)量都相同。
對于滿足搜索樹條件，我們只需要看中序遍歷的結(jié)果是否為升序就可以了，這個不難。
想要判斷紅黑樹中是否出現(xiàn)連續(xù)的紅色結(jié)點(diǎn)，最容易的方式就是判斷當(dāng)前結(jié)點(diǎn)和他的parent顏色是否均為紅色，如果你拿當(dāng)前結(jié)點(diǎn)和他的孩子比較，那就麻煩了，還得和左右兩個孩子進(jìn)行比較，左右還有可能為空，非常麻煩。我們直接比對當(dāng)前結(jié)點(diǎn)和其父節(jié)點(diǎn)，訪問父節(jié)點(diǎn)就很簡單了，因?yàn)槠胶馑阉鳂涮烊坏娜骀溄Y(jié)構(gòu)可以很輕松的幫助我們訪問父節(jié)點(diǎn)，所以我們只需要寫一個遞歸，前序遍歷整顆紅黑樹的所有結(jié)點(diǎn)，遇到空就返回，如果某個結(jié)點(diǎn)和其父節(jié)點(diǎn)的顏色均為紅色，直接返回false即可。文章來源：http://www.zghlxwxcb.cn/news/detail-401158.html
2.
比較有意思的其實(shí)是第4條性質(zhì)的驗(yàn)證，對于每一個結(jié)點(diǎn)，以此結(jié)點(diǎn)為父節(jié)點(diǎn)向下所有的路徑的黑色結(jié)點(diǎn)數(shù)量均相同，這個性質(zhì)可不好驗(yàn)證啊，而且還是對于每個結(jié)點(diǎn)的所有向下的路徑，這該怎么搞啊？
這里面隱含了一個細(xì)微的點(diǎn)，我也是思考過后才發(fā)現(xiàn)到的，我們無須驗(yàn)證所有結(jié)點(diǎn)的向下每條路徑上的黑色結(jié)點(diǎn)數(shù)量，只需要驗(yàn)證根節(jié)點(diǎn)root的向下所有路徑的黑色結(jié)點(diǎn)數(shù)量相同即可完成所有結(jié)點(diǎn)的驗(yàn)證。其實(shí)道理很簡單，只要根結(jié)點(diǎn)向下的每條路徑相等了，那么左右子樹的向下路徑一定是相等的，因?yàn)楦?jié)點(diǎn)是所有路徑的公共祖先，左右子樹的每條路徑的黑色結(jié)點(diǎn)數(shù)量都減1就好了，那對于左右子樹各自來說，兩棵子紅黑樹都不違反紅黑樹的第4條規(guī)則，假設(shè)其中一棵子紅黑樹的根節(jié)點(diǎn)顏色為紅色，那他的左右子樹路徑的黑色結(jié)點(diǎn)數(shù)量就都不變，因?yàn)楣沧嫦仁羌t色的，如果公共祖先是黑色的，那左右子樹路徑的黑色結(jié)點(diǎn)數(shù)量也是同時減1的，所以左右子樹還是不會違反紅黑樹第4條規(guī)則的。
綜上所述，只要滿足root根結(jié)點(diǎn)的紅黑樹第4條規(guī)則，其余所有結(jié)點(diǎn)作根時均可滿足第四條規(guī)則。
代碼實(shí)現(xiàn)上，在遞歸之前，我們可以迭代先統(tǒng)計(jì)一下紅黑樹最左路徑的黑色結(jié)點(diǎn)數(shù)量，以此來作為reference value，然后利用判斷不能出現(xiàn)連續(xù)紅色結(jié)點(diǎn)的遞歸算法，順便統(tǒng)計(jì)出每條路徑的黑色結(jié)點(diǎn)數(shù)量blackNum，當(dāng)遞歸到nullptr的時候也就是遞歸到完整的一條路徑了，此時進(jìn)行blackNum和reference value比對，如果不相等直接返回false即可。（注意blackNum用的是傳值而不是引用，因?yàn)槲覀兿Ｍ氖敲恳粋€遞歸到nullptr函數(shù)棧幀都有自己獨(dú)立的blackNum變量，而不是所有的棧幀共用一個局部blackNum變量，共用一個的話，統(tǒng)計(jì)出來的黑色結(jié)點(diǎn)數(shù)量就不是單條路徑的了，而是整棵紅黑樹的所有黑色結(jié)點(diǎn)數(shù)量了，所以不能用引用，應(yīng)該用傳值）文章來源地址http://www.zghlxwxcb.cn/news/detail-401158.html
void InOrder()
{
_InOrder(_root);
}
bool Check(Node* root, int blackNum, const int ref)
// blackNum用的就是傳值傳遞，遇到空返回的時候，每條路徑尾結(jié)點(diǎn)所在棧幀的blackNum都是獨(dú)立的，傳值就是用來干這個的，
//如果用引用傳參，那就廢了，每條路徑的黑色結(jié)點(diǎn)數(shù)量類和到int& blackNum上面去了。
{
if (root == nullptr)
{
//cout << "每條路徑的黑色結(jié)點(diǎn)數(shù)量:"<<blackNum << endl;
if (blackNum != ref)
{
cout << "違反規(guī)則: 本條路徑的黑色結(jié)點(diǎn)的數(shù)量和最左路徑不相等" << endl;
return false;
}
return true;
}
if (root->_col == RED && root->_parent->_col == RED)
{
cout << "違反規(guī)則: 出現(xiàn)了連續(xù)的紅色結(jié)點(diǎn)" << endl;
//root的parent顏色為黑色能說明這棵樹就是紅黑樹嗎？當(dāng)然確定不了，只有parent顏色為紅色我們倒是能夠確定違反了紅黑樹的規(guī)則
return false;
}
if (root->_col == BLACK)
++blackNum;
return Check(root->_left, blackNum, ref) && Check(root->_right, blackNum, ref);
}
bool IsBalance()
{
//求最長路徑和最短路徑的差不能保證樹就是紅黑樹，因?yàn)闃浣Y(jié)點(diǎn)的顏色有可能是不正確的，萬一出現(xiàn)連續(xù)的兩個紅色結(jié)點(diǎn)呢？
if (_root == nullptr)
return true;
//每個結(jié)點(diǎn)的顏色不是紅色就是黑色，這點(diǎn)枚舉類型就幫我們保證了，無須確定
//檢查的兩條原則，不能出現(xiàn)連續(xù)的兩個紅色結(jié)點(diǎn)，結(jié)點(diǎn)的每條路徑上的黑色結(jié)點(diǎn)數(shù)量都相同
if (_root->_col == RED)//root的顏色為黑色能確定這棵樹就一定是紅黑樹嗎？當(dāng)然確定不了，但只要root顏色為紅色，就可以確定違反紅黑樹規(guī)則
return false;
//遍歷這棵樹，找紅色結(jié)點(diǎn)，判斷紅色結(jié)點(diǎn)的父親是否為紅色
int ref = 0;
Node* cur = _root;
while (cur)
{
if (cur->_col == BLACK)
ref++;
cur = cur->_left;
}
return Check(_root, 0, ref);// 1.遍歷樹的所有結(jié)點(diǎn)，看當(dāng)前紅結(jié)點(diǎn)的父親是否為紅色結(jié)點(diǎn)
// 每個結(jié)點(diǎn)都給一個值，用于標(biāo)識逆回去的路徑上出現(xiàn)的黑色結(jié)點(diǎn)的數(shù)量。
//我們可以改變結(jié)點(diǎn)結(jié)果，或者利用遞歸算法的函數(shù)棧幀獨(dú)立性進(jìn)行解決，每一層的棧幀的黑色結(jié)點(diǎn)數(shù)量都是不同的。
}
private:
void _InOrder(Node* _root)
{
if (_root == nullptr)
return;
_InOrder(_root->_left);
cout << _root->_kv.first << ":" << _root->_kv.second << endl;
_InOrder(_root->_right);
}
Node* _root = nullptr;
};
到了這里，關(guān)于【C++】AVL樹和紅黑樹的插入的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
