在java語言中，TreeMap TreeSet 等都是基于紅黑樹的原理實(shí)現(xiàn)的，主要是用它來存儲(chǔ)有序的數(shù)據(jù)，時(shí)間復(fù)雜度是O(lgn)，效率非常之高，在學(xué)習(xí)這些數(shù)據(jù)集合的時(shí)候，了解到紅黑樹，由此對(duì)紅黑樹進(jìn)行了深入的學(xué)習(xí)。

1、文中提到的給一個(gè)節(jié)點(diǎn)到兄弟，或者拿一個(gè)節(jié)點(diǎn)過來，其實(shí)都是很多文章中提到了左旋與右旋的目的；
2、我這里面畫的圖真的不如維基百科的圖，主要是傳遞一些我總結(jié)的的理解方式

紅黑樹是基于二叉排序樹的:

• 若任意節(jié)點(diǎn)的左子樹不空，則左子樹上所有結(jié)點(diǎn)的值均小于它的根結(jié)點(diǎn)的值；
• 若任意節(jié)點(diǎn)的右子樹不空，則右子樹上所有結(jié)點(diǎn)的值均大于它的根結(jié)點(diǎn)的值；
• 任意節(jié)點(diǎn)的左、右子樹也分別為二叉查找樹。
• 沒有鍵值相等的節(jié)點(diǎn)（no duplicate nodes）

紅黑樹的有效條件：

1. 節(jié)點(diǎn)是<font color="red">紅色</font>或<font color="black">黑色</font>
2. 根節(jié)點(diǎn)是黑色
3. 每個(gè)葉子節(jié)點(diǎn)(NIL , NULL) 是黑色的
4. 每個(gè)<font color="red">紅色</font>節(jié)點(diǎn)的兩個(gè)子節(jié)點(diǎn)是黑色，也就是沒有兩個(gè)相連節(jié)點(diǎn)都是紅色的
5. 從任何一個(gè)節(jié)點(diǎn)到其下面的每個(gè)葉子節(jié)點(diǎn)的路徑上都包含相同數(shù)目的黑色節(jié)點(diǎn)

推論：
    - 每個(gè)路徑上的 黑節(jié)點(diǎn)>=紅節(jié)點(diǎn) 數(shù)量；
    - 從根到葉子的最長(zhǎng)路徑 max <= min 從根到葉子的最短路徑

一、紅黑數(shù)新增元素

<font color="deepgreen">紅黑樹新增節(jié)點(diǎn)有可能破壞的規(guī)則是:不能有相連2個(gè)紅點(diǎn)！?。。。?！</font>

新增節(jié)點(diǎn)的需要遵循2個(gè)條件：
- 紅黑樹是基于二叉排序樹的，新增元素必然在葉子上,且按照排序添加到應(yīng)該的節(jié)點(diǎn)下，這是最基本的
- 紅黑樹的新增的元素必須是紅色的，這是為了不破壞紅黑樹第5個(gè)有效條件
- 基于上面基本條件，新增節(jié)點(diǎn)只有兩種情況，
①：樹的第一個(gè)元素，成為根
②：加到黑點(diǎn)下面，沒有破壞特性
③：加到紅色點(diǎn)的下面，破壞了紅黑樹特性（這才是最需要修復(fù)樹的）

①.樹的第一個(gè)元素，成為根

situation1.jpg

②.加到黑點(diǎn)下面，沒有破壞特性

situation2.jpg

③.加到紅色點(diǎn)的下面

這種情況，我的理解就是，如果加到父節(jié)點(diǎn)紅點(diǎn)下面，那如果需要保持紅黑樹特性,爺爺節(jié)點(diǎn)一定是黑色的，也就只有叔節(jié)點(diǎn)是紅色與黑色兩種情況了；
既然父節(jié)點(diǎn)這邊有2個(gè)紅色的相連，那我就給一個(gè)紅色點(diǎn)給叔節(jié)點(diǎn)那邊就行了,兄弟有難同擔(dān)嘛。
如果叔叔是紅色，我給一個(gè)紅色的過去，那又會(huì)造成叔節(jié)點(diǎn)那邊有2個(gè)紅點(diǎn)相連了，叔節(jié)點(diǎn)就有麻煩了，那怎么辦呢？老爸和叔叔都搞不定了那就讓爺爺去搞定吧。
如果叔叔是黑色，那給一個(gè)紅色的給叔節(jié)點(diǎn)，不會(huì)給叔節(jié)點(diǎn)造成麻煩，那就不需要爺爺插手了，就搞定了。

以下的所有的例子都可以歸于以上的情況

1)如果新增的元素存在父元素，父元素是紅色，叔元素是紅色的

situation3.jpg

2)如果新增的元素存在父元素，父元素是紅色，叔元素是黑色的

此處需要說明：由于二叉樹的特性，新增的節(jié)點(diǎn)一定替代了原有的葉子節(jié)點(diǎn)位置，所以第一次出現(xiàn)當(dāng)前的情況時(shí)，為了保證第五個(gè)條件成立，叔節(jié)點(diǎn)一定是NiL，
只有之后尾部遞歸到上面去才會(huì)出現(xiàn)叔節(jié)點(diǎn)可能存在不是葉子的情況，處理方法都是一樣的)
維基百科給的例子沒有特殊說明，我開始誤解了

situation4.jpg

3)在第四種情況中，只舉例說明了右旋，左旋如圖

situation5.jpg

4)前面的2種情況都是 N-P-G在一條直線上，實(shí)際上會(huì)存在不在條直線上的情況

situation6.jpg

situation7.jpg

5)執(zhí)行了上面的操作之后，就N,P的身份調(diào)換， P理解為新增的N'，N理解為'， 則N', P', G 在一條直線上，就可以按照之前的邏輯進(jìn)行處理了

二、紅黑數(shù)刪除元素

<font color="deepgreen">紅黑樹刪除可能破壞的紅黑樹規(guī)則是：任意節(jié)點(diǎn)到葉子點(diǎn)的所有路徑上黑點(diǎn)數(shù)量相同?。。。。。。?lt;/font>

在確定最終刪除節(jié)點(diǎn)位置前，需要做如下操作:
1. 在樹中找到需要?jiǎng)h除的點(diǎn),如果不存在,則直接結(jié)束
2. 如果存在的話,則可以執(zhí)行刪除操作。

用圖來說明刪除前預(yù)處理方法:

• 圖中說明了2種預(yù)處理方法
  1. 用左子樹最大值頂替刪除點(diǎn)的值，刪除左子樹最大值位置的點(diǎn)

  2. 用右子樹最小值頂替刪除點(diǎn)的值，刪除右子樹最小值位置的點(diǎn)

     
     
     pre_sulotion.jpg
• 當(dāng)做完這些預(yù)處理的之后，會(huì)發(fā)現(xiàn)一個(gè)有趣的現(xiàn)象,新的要?jiǎng)h除的點(diǎn)的位置，不可能有同時(shí)有2個(gè)子節(jié)點(diǎn)，必然至少有一個(gè)兒子是葉子(nil)節(jié)點(diǎn)

  1. 其中就只有兩種情況: ① 2個(gè)葉子(null)兒子； ② 一個(gè)兒子,一個(gè)葉子(nil),這一種又更有趣了, 兒子必然是紅色的，刪除點(diǎn)必然是黑色的

     
     
     pre_se.jpg

仔細(xì)看之后，發(fā)現(xiàn)只有①的情況需要做如下處理
第②種就簡(jiǎn)單了，直接用其中的存在的兒子節(jié)點(diǎn)替換到要?jiǎng)h除的位置并且顏色變?yōu)楹谏托辛?；再刪除掉需要?jiǎng)h除的點(diǎn)
所以這下面的邏輯都是第①種的情況下進(jìn)行處理

1.刪除點(diǎn)是紅色

• 沒啥可說明了的，刪除紅色的，不影響紅黑樹結(jié)構(gòu)，直接刪除就行了

2.刪除點(diǎn)是黑色

• 刪除黑色點(diǎn)，經(jīng)過該黑色點(diǎn)的路徑上的黑色點(diǎn)必然少一個(gè)，就會(huì)造成整棵樹不平衡，那有什么辦法呢；
  • <font color="red">（1）</font>第一種辦法就是讓其他的路徑上的黑色點(diǎn)也減少一個(gè)黑色點(diǎn)，那樣所有的路徑就平衡了；
  • <font color="blue">（2）</font>第二種辦法就是從兄弟節(jié)點(diǎn)上拿一個(gè)紅色的過來，放到刪除點(diǎn)的路徑上，并且設(shè)置為黑色，
    這樣的花即沒有減少兄弟節(jié)點(diǎn)路徑的黑點(diǎn)數(shù)量，也填補(bǔ)了刪除黑點(diǎn)的數(shù)量，同樣達(dá)到了紅黑樹平衡

2.1.刪除點(diǎn)是黑色，兄弟節(jié)點(diǎn)沒有紅點(diǎn)可拿

• 兄弟沒有紅點(diǎn)可拿，那沒關(guān)系，那就繼續(xù)往上去找找叔叔節(jié)點(diǎn)分支拿紅點(diǎn)，還沒有的話，繼續(xù)往上找....
  • 每一次找不到，也要保證每個(gè)子樹平衡，按下圖的方式修復(fù)樹,最終如果找到了根，修復(fù)之后，就是上面的<font color="red">（1）</font>的結(jié)果
  • 如果找到了，那就轉(zhuǎn)到2.2的處理方法了 ===>2.2

delete_case1.jpg

2.2.刪除點(diǎn)是黑色，兄弟節(jié)點(diǎn)有紅點(diǎn)可拿

• 兄弟節(jié)點(diǎn)有紅點(diǎn)拿，雖然排列的可能性很多，但是最終的效果就是兄弟分支少了一個(gè)紅色的，當(dāng)前刪除的分支多了一個(gè)黑色的，不需要往上遞歸了，
  直接就搞定了,修復(fù)之后，就是上面的<font color="blue">（2）</font>的結(jié)果
• 唯一要考慮的就是從兄弟那里拿走一個(gè)紅色，怎么讓樹仍然保持二叉排序樹的性質(zhì)
• 下圖中舉例了一些例子

delete-case2.jpg

三、java代碼實(shí)現(xiàn)

RBTree項(xiàng)目地址

總結(jié)

java 中紅黑樹的應(yīng)用非常多，treeMap treeSet 就連java8中的HashMap節(jié)點(diǎn)也在特殊條件下使用紅黑樹存儲(chǔ)，而java7中還是鏈?zhǔn)酱鎯?chǔ)，這是一個(gè)非常大的改變