學過數據數據結構都知道二叉樹的概念，而又有多種比較常見的二叉樹類型，比如完全二叉樹、滿二叉樹、二叉搜索樹、均衡二叉樹、完美二叉樹等；今天我們要說的紅黑樹就是就是一顆非嚴格均衡的二叉樹，均衡二叉樹又是在二叉搜索樹的基礎上增加了自動維持平衡的性質，插入、搜索、删除的效率都比較高。紅黑樹也是實現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文檔，想要獲取的小夥伴的朋友，可以私信我關鍵字【資料】進行獲取。