引言：
學過數據數據結構都知道二叉樹的概念，而又有多種比較常見的二叉樹類型，比如完全二叉樹、滿二叉樹、二叉搜索樹、均衡二叉樹、完美二叉樹等；今天我們要說的紅黑樹就是就是一顆非嚴格均衡的二叉樹，均衡二叉樹又是在二叉搜索樹的基礎上增加了自動維持平衡的性質，插入、搜索、刪除的效率都比較高。紅黑樹也是實現TreeMap存儲結構的基石。
一. 二叉搜索樹
二叉搜索樹又叫二叉查找樹、二叉排序樹，我們先看一下典型的二叉搜索樹，這樣的二叉樹有何規則特點呢？
1．節點的左子樹小於節點本身；
2．節點的右子樹大於節點本身；
3．左右子樹同樣為二叉搜索樹；
下圖就是一顆典型的二叉搜索樹
二叉搜索樹是均衡二叉樹的基礎，我們看一下它的搜索步驟如何
我們要從二叉樹中找到值為 58 的節點
第一步：首先查找到根節點，值為60的節點
第二步：比較我們要找的值58與該節點的大小
如果等於，那麼恭喜，已經找到；
如果小於，繼續找左子樹；
如果大於，那麼找右子樹；
很明顯58 < 60，因此我們找到左子樹的節點 56，此時我們已經定位到了節點56
第三步：按照第二步的規則繼續找
58 > 56 我們需要繼續找右子樹，定位到了右子樹節點58，恭喜，此時我們已經找到了。
我們經過三步就已經找到了，其實就是我們平時所說的二分查找，這種二叉搜索樹好像查找效率很高，但同樣它也有缺陷，如下面這樣的二叉搜索樹。
看到這樣的二叉搜索樹是否很彆扭，典型的大長腿瘸子，但它也是二叉搜索樹，如果我們要找值為50的節點，基本上和單鏈表查詢沒多大區別了，性能將大打折扣。這個時候我們的均衡二叉樹就粉墨登場了，均衡二叉樹就是在二叉搜索樹的基礎上添加了自動維持平衡的性質。
上面的大長腿瘸子二叉搜索樹經過自動平衡後，可能就成為了下面這樣的二叉樹。
經過了自動平衡，再去找值為50的節點，查找性能將提升很多。紅黑樹就是非嚴格均衡的二叉搜索樹。
二. 紅黑樹規則特點
紅黑樹具體有哪些規則特點呢？
1．節點分為紅色或者黑色；
2．根節點必為黑色；
3．葉子節點都為黑色，且為null；
4．連接紅色節點的兩個子節點都為黑色（紅黑樹不會出現相鄰的紅色節點）；
5．從任意節點出發，到其每個葉子節點的路徑中包含相同數量的黑色節點；
6．新加入到紅黑樹的節點為紅色節點；
規則看著好像挺多，沒錯，因為紅黑樹也是均衡二叉樹，需要具備自動維持平衡的性質，上面的6條就是紅黑樹給出的自動維持平衡所需要具備的規則
我們看一看一個典型的紅黑樹到底是什麼樣兒？
首先解讀一下規則，除了字面上看到的意思，還隱藏了哪些意思呢？
第一. 從根節點到葉子節點的最長路徑不大於最短路徑的2倍
怎麼樣的路徑算最短路徑？
從規則5中，我們知道從根節點到每個葉子節點的黑色節點數量是一樣的，那麼純由黑色節點組成的路徑就是最短路徑；
什麼樣的路徑算是最長路徑？
根據規則4和規則3，若有紅色節點，則必然有一個連接的黑色節點，當紅色節點和黑色節點數量相同時，就是最長路徑，也就是黑色節點（或紅色節點）* 2
第二. 為什麼說新加入到紅黑樹中的節點為紅色節點
從規則4中知道，當前紅黑樹中從根節點到每個葉子節點的黑色節點數量是一樣的，此時假如新的黑色節點的話，必然破壞規則，但加入紅色節點卻不一定，除非其父節點就是紅色節點，因此加入紅色節點，破壞規則的可能性小一些，下面我們也會舉例來說明。
什麼情況下，紅黑樹的結構會被破壞呢？破壞後又怎麼維持平衡，維持平衡主要通過兩種方式【變色】和【旋轉】，【旋轉】又分【左旋】和【右旋】，兩種方式可相互結合。
下面我們從插入和刪除兩種場景來舉例說明
因為文章過長不能一一上傳編寫，所以整理成了PDF文檔，想要獲取的小夥伴的朋友，可以私信我關鍵字【資料】進行獲取。
