AVL樹
AVL樹叫做平衡二叉樹，它的前提是二叉排序樹(BST或叫做二叉查找樹)。由于在生成BST樹的過程中可能會出現線型樹結構，比如插入的順序是：1, 2, 3, 4, 5, 6, 7..., n。
定義：它是一棵空樹或它的左右兩個子樹的高度差的絕對值不超過1，并且左右兩個子樹都是一棵平衡二叉樹。
在BST樹中，比較理想的狀況是每個子樹的左子樹和右子樹的高度相等，此時搜尋的時間複雜度是log(N)。
可是，一旦這棵樹演化成了線型樹的時候，這個理想的情況就不存在了，此時搜尋的時間複雜度是O(N)，在資料量很大的情況下，我們并不願意看到這樣的結果。
現在我們要做的事就是讓BST在建立的過程中不要向線型樹發展。方法就是讓其在添加新節點的時候，不斷調整樹的平衡狀态。
節點失衡
對于節點平衡有這樣的定義：它是一棵空樹或它的左右兩個子樹的高度差的絕對值不超過1，并且左右兩個子樹都是一棵平衡二叉樹。而這裡提到的高度差，就是我們下面會引入的平衡因子：BF（balance factor）。
因為AVL樹說到底還是一個二叉樹，隻有兩個子節點。而且節點失衡的發生，是因為有一個新節點的插入，這個新插入的節點導緻了某些節點左右子節點高度的不一緻。是以我們可以枚舉出以下4種情況的失衡狀态。
- 在一個節點的左子樹的左子樹上插入一個新節點。即LL。在這種情況下，我們可以通過将節點右旋使其平衡。如圖-2所示
原A的左孩子B變為父結點，A變為其右孩子，而原B的右子樹D變為A的左子樹，注意旋轉之後D是A的左子樹。
- 在一個節點的右子樹的右子樹上插入一個新節點。即RR。在這種情況下，我們可以通過将節點左旋使其平衡。如圖-3所示
這時隻需要把樹向左旋轉一次即可，如圖所示，原A右孩子B變為父結點，A變為其左孩子，而原B的左子樹Blh将變為A的右子樹。
- 在一個節點的左子樹的右子樹上插入一個新節點。即LR。在這種情況下，我們不能直接通過将節點左旋或右來使其平衡了。這裡需要兩步來完成，先讓樹中高度較低的進行一次左旋（RR型），這個時候就變成了LL了。再進行一次單右旋操作即可。如圖-4所示；
- 左旋一次
- 右旋一次
總結：LR這種情況，需要旋轉兩次，僅一次的旋轉是不能夠使二叉樹再次平衡。如圖所示，在B節點按照RR型向左旋轉一次之後，二叉樹在A節點仍然不能保持平衡，這時還需要再向右旋轉一次。
- 在一個節點的右子樹的左子樹上插入一個新節點。即RL。在這種情況下，我們不能直接通過将節點左旋或右來使其平衡了。這裡需要兩步來完成，先讓樹中高度較低的進行一次右旋，這個時候就變成了RR了。再進行一次單左旋操作即可。如圖-5所示；
更多C++背景開發技術點知識内容包括C/C++，Linux，Nginx，ZeroMQ，MySQL，Redis，MongoDB，ZK，流媒體，音視訊開發，Linux核心，TCP/IP，協程，DPDK多個進階知識點。
C/C++Linux伺服器開發進階架構師/C++背景開發架構師免費學習位址
【文章福利】另外還整理一些C++背景開發架構師 相關學習資料，面試題，教學視訊，以及學習路線圖，免費分享有需要的可以點選領取
- 右旋一次
- 左旋一次
平衡二叉樹某一節點的右孩子的左子樹上插入一個新的節點，使得該節點不再平衡。同樣，這時需要旋轉兩次，旋轉方向剛好同LR型相反。
從上面對節點失衡的說明，以及圖解。我想你已經對旋轉的操作有了一個大概地認識了吧。從圖中我們也可以看出，LL型和RR型、LR型和RL型是兩個行為很相似地操作。其實他們互為對稱。
紅黑樹
紅黑樹是一種很有意思的平衡檢索樹。它的統計性能要好于平衡二叉樹(有些書籍根據作者姓名，Adelson-Velskii和Landis，将其稱為AVL-樹)，是以，紅黑樹在很多地方都有應用。在C++ STL中，很多部分(目前包括set, multiset, map, multimap)應用了紅黑樹的變體(SGI STL中的紅黑樹有一些變化，這些修改提供了更好的性能，以及對set操作的支援)。
紅黑樹的定義如下：
- 滿足下列條件的二叉搜尋樹是紅黑樹
- 每個結點要麼是“紅色”，要麼是“黑色”
- 所有的葉結點都是空結點，并且是“黑色”的。
- 如果一個結點是“紅色”的，那麼它的兩個子結點都是“黑色”的。
- (注:也就是說，如果結點是黑色的，那麼它的子節點可以是紅色或者是黑色的)。
- 結點到其子孫結點的每條簡單路徑都包含相同數目的“黑色”結點
- 根結點永遠是“黑色”的
之是以稱為紅黑樹的原因就在于它的每個結點都被“着色”為紅色或黑色。這些結點顔色被用來檢測樹的平衡性。但需要注意的是，紅黑樹并不是平衡二叉樹，恰恰相反，紅黑樹放松了平衡二叉樹的某些要求，由于一定限度的“不平衡”，紅黑樹的性能得到了提升。
從根結點到葉結點的黑色結點數被稱為樹的“黑色高度”(black-height)。前面關于紅黑樹的性質保證了從根結點到葉結點的路徑長度不會超過任何其他路徑的兩倍。
考慮一棵黑色高度為3的紅黑樹：從根結點到葉結點的最短路徑長度顯然是2(黑-黑-黑)，最長路徑為4(黑-紅-黑-紅-黑)。
不可能在最長路經中加入更多的黑色結點，紅色結點的子結點必須是黑色的，是以在同一簡單路徑中不允許有兩個連續的紅色結點。綜上，我們能夠建立的最長路經将是一個紅黑交替的路徑。
由此我們可以得出結論：對于給定的黑色高度為n的紅黑樹，從根到葉結點的簡單路徑的最短長度為n-1，最大長度為2(n-1)。
插入和删除操作中，結點可能被旋轉以保持樹的平衡。紅黑樹的平均和最差搜尋時間都是O(log2 n)。Cormen [2001]給出了對于這一結論的證明。在實際應用中，紅黑樹的統計性能要好于平衡二叉樹，但極端性能略差。
紅黑樹中結點的插入過程
插入結點的過程是：
- 在樹中搜尋插入點
- 新結點将替代某個已經存在的空結點，并且将擁有兩個作為子結點的空結點
- 新結點标記為紅色，其父結點的顔色根據紅黑樹的定義确定；如果需要，對樹作調整
注意 空結點和NULL指針是不同的。在簡單的實作中，可以使用作為“監視哨”，标記為黑色的公共結點作為前面提到的空結點。
給一個紅色結點加入兩個空的子結點符合性質4，同時，也必須確定紅色結點的兩個子結點都是黑色的(根據性質3)。盡管如此，當新結點的父結點時紅色時，插入紅色的子結點将是違反定義的。這時存在兩種情況。
紅色父結點的兄弟結點也是紅色的
簡單地對上級結點重新着色将解決沖突。當結點B被重新着色之後，應該重新檢驗更大範圍内樹結點的顔色，以確定整棵樹符合定義的要求。結束時根結點應當是黑色的，如果它原先是紅色的，則紅黑樹樹的黑色高度将遞增1。
紅色父結點的兄弟結點是黑色的
這種情形比較複雜。
重新對結點着色将把結點A變成黑色，于是，樹的平衡将被破壞，因為左子樹的黑色高度将增加，而右子樹的黑色高度沒有相應地改變。如果我們把結點B着上紅色，那麼左右子樹的高度都将減少，樹依然不平衡。此時，繼續對結點C進行着色将導緻更糟糕的情況，左子樹黑色高度增加，右子樹黑色高度減少。為了解決問題，需要旋轉并對樹結點進行重新着色。這時算法将正常結束，因為子樹的根結點(A)被着色為黑色，同時，不會引入新的紅-紅沖突。
結束插入過程
插入結點時，可能會需要重新着色，或者旋轉，來保持紅黑樹的性質。如果旋轉完成，那麼算法就結束了。對于重新着色來說，我們會在子樹的根留下一個紅色結點，于是需要繼續向上對樹進行修整，以保持紅黑樹的性質。最壞情況下，我們将不得不對到樹根的所有路徑進行處理。插入的時間複雜度為O(log2 n)。删除結點的時間複雜度與此類似。
結點的删除
紅黑樹的結點删除情況要比插入複雜一些。我們可以把實際的删除操作分成3種情況(先不讨論顔色)，其中被删除的結點用紫色标記，藍色表示任意顔色的結點，可能是紅色，也可能是黑色：
情況a: 被删除的結點沒有子結點(兩個子結點都是空結點)
原先屬于X的空結點被A“繼承”。如果被删除結點是黑色結點，則可能造成樹的黑色高度變化。
情況b: 有一個子結點
B結點取代原X結點的位置。如果被删除的結點是黑色結點，則可能造成樹的黑色高度發生變化；如果B是紅色結點，還可能需要重新着色。
情況c: 有兩個子結點
這種情形比較複雜。需要将X和它的左子樹中的鍵值最大的結點進行交換。這通常會導緻重新着色，對樹的黑色高度的改變，以及随之而來的旋轉。
需要說明的是，僅僅删除結點是不夠的，因為此後很可能還需要對樹進行重新着色。如果删除的是紅色結點，那麼沒有關系，因為這不會影響樹的黑色高度；而如果删除的是黑色結點，事情就沒那麼簡單了。需要把受到影響(移動或交換)的結點标記為黑色，如果它原來已經是黑色的，那麼需要标記為“雙黑”(雙黑，或double-black是許多英文資料中提及的一個概念。簡單地說，标記為“雙黑”意味着需要對周圍的紅色結點進行“抹黑 ”處理)。
包含“雙黑”結點顯然不符合紅黑樹的要求，是以必須消除這種情況。出現“雙黑”的情況可以分為4種：
1、雙黑結點的兄弟結點是紅色的
2、雙黑結點的兄弟是黑色的，并且它的兄弟有兩個黑色的子結點
3、雙黑結點的兄弟是黑色的，并且，它的兄弟的左、右子結點分别是紅色和黑色
4、雙黑結點的兄弟是黑色的，并且，它的兄弟的右子結點是紅色的
很顯然，上述四種情況包括了可能的所有狀況。
處理雙黑結點的基本思想是進行“色彩補償”。換言之，将鄰近的紅色結點變為黑色，同時，此雙黑結點也“還原”為黑色。
總結
紅黑樹引入了“顔色”的概念。引入“顔色”的目的在于使得紅黑樹的平衡條件得以簡化。正如著名的密碼學專家Bruce Schneier所說的那樣，“Being Partly balanced can be good enough”，紅黑樹并不追求“完全平衡”——它隻要求部分地達到平衡要求，降低了對旋轉的要求，進而提高了性能。
紅黑樹能夠以O(log2 n)的時間複雜度進行搜尋、插入、删除操作。此外，由于它的設計，任何不平衡都會在三次旋轉之内解決。當然，還有一些更好的，但實作起來更複雜的資料結構能夠做到一步旋轉之内達到平衡，但紅黑樹能夠給我們一個比較“便宜”的解決方案。紅黑樹的算法時間複雜度和AVL相同，但統計性能比AVL樹更高。
當然，紅黑樹并不适應所有應用樹的領域。如果資料基本上是靜态的，那麼讓他們待在他們能夠插入，并且不影響平衡的地方會具有更好的性能。如果資料完全是靜态的，例如，做一個哈希表，性能可能會更好一些。
在實際的系統中，例如，需要使用動态規則的防火牆系統，使用紅黑樹而不是散清單被實踐證明具有更好的伸縮性。
原文連結：🏆【資料結構之旅】「AVL平衡樹專項」帶你領略常用的AVL樹與紅黑樹的奧秘（規則篇） - 掘金