㈠ 什麼是紅黑樹
最近研究JDK源碼的時候，發現TreeMap和TreeSet底層數據結構是紅黑樹，當然，TreeSet其實本質上就是Value為一個固定值的TreeMap。在JDK1.8以後，HashMap也用到了紅黑樹。
那紅黑樹到底是怎樣的一種數據結構呢？相信大家都不是非常了解，我也去翻了好多的相關文章，發現一篇很有趣的漫畫，可以幫助大家很快了解紅黑樹大概是怎樣的一種數據結構，有哪些特點。 只是大概的介紹一下紅黑樹，詳細的實現大家還是請參考相關的演算法書籍。
以下內容轉自： 漫畫演算法：什麼是紅黑樹？
1.左子樹上所有結點的值均小於或等於它的根結點的值。
2.右子樹上所有結點的值均大於或等於它的根結點的值。
3.左、右子樹也分別為二叉排序樹。
下圖中這棵樹，就是一顆典型的二叉查找樹：
1.查看根節點9：
3.由於10 < 13，因此查看左孩子11：
假設初始的二叉查找樹只有三個節點，根節點值為9，左孩子值為8，右孩子值為12：
2.根節點是黑色。
3.每個葉子節點都是黑色的空節點（NIL節點）。
4 每個紅色節點的兩個子節點都是黑色。(從每個葉子到根的所有路徑上不能有兩個連續的紅色節點)
5.從任一節點到其每個葉子的所有路徑都包含相同數目的黑色節點。
下圖中這棵樹，就是一顆典型的紅黑樹：
什麼情況下會破壞紅黑樹的規則，什麼情況下不會破壞規則呢？我們舉兩個簡單的栗子：
1.向原紅黑樹插入值為14的新節點：
為了重新符合紅黑樹的規則，嘗試把紅色節點變為黑色，或者把黑色節點變為紅色。
下圖所表示的是紅黑樹的一部分，需要注意節點25並非根節點。因為節點21和節點22連續出現了紅色，不符合規則4，所以把節點22從紅色變成黑色：
但這樣並不算完，因為憑空多出的黑色節點打破了規則5，所以發生連鎖反應，需要繼續把節點25從黑色變成紅色：
逆時針旋轉紅黑樹的兩個節點，使得父節點被自己的右孩子取代，而自己成為自己的左孩子。說起來很怪異，大家看下圖：
圖中，身為右孩子的Y取代了X的位置，而X變成了自己的左孩子。此為左旋轉。
順時針旋轉紅黑樹的兩個節點，使得父節點被自己的左孩子取代，而自己成為自己的右孩子。大家看下圖：
圖中，身為左孩子的Y取代了X的位置，而X變成了自己的右孩子。此為右旋轉。
首先，我們需要做的是變色，把節點25及其下方的節點變色：
這時候我們需要把節點13看做X，節點8看做Y，像剛才的示意圖那樣進行右旋轉：
如果想要詳細了解紅黑樹演算法，可以參考這篇文章： Java數據結構和演算法（十一）——紅黑樹
㈡ 紅黑樹(Red-black tree)
樹 是一種 抽象數據類型 ，或是實作這種抽象數據類型的數據結構，用來模擬具有樹狀結構性質的 數據集合 。
紅黑樹 是一種自平衡二叉查找樹，典型的用途是實現 關聯數組 ，它是復雜的，但它的操作有著良好的最壞情況運行時間,並且在實踐中是高效的 O(log n ) 時間內做查找，插入和刪除，這里的 n 是樹中元素的數目。
一個由n個節點隨機構成的二叉查找樹的高度為(log n ).證明如下：
而時間復雜度是以某個基礎數據操作的重復次數作為量度。紅黑樹的是二叉搜索樹，左子樹上所有節點的值均小於他的根節點的值，右子樹上所有節點均大於根節點的值，左右子節樹相對根節點按大小分布。如果把每次節點值的比較看成基礎數據操作，那麼最差的查找情況是一直查找到高度最大的根節點，那麼查找的時間復雜度即與高度成正比，可表示成 O(log n ) 。
簡單了解了紅黑樹的字面定義，下面動手感受下紅黑樹的相關操作。當你插入或者刪除一個節點時，可能會破壞紅黑樹的性質，所以需要對樹節點進行重新著色或者旋轉，來保持紅黑樹的結構。首先看下二叉樹的旋轉。
假設pivot節點不為空，其右子樹不為空，那麼左旋即是：使pivot的右孩子Y為子樹的根，pivot節點為子樹根節點的左孩子，pivot左孩子、Y節點的右孩子不改變，Y節點左孩子變為pivot節點右孩子。
假設pivot節點不為空，其左子樹不為空，那麼右旋：使pivot的左孩子Y為子樹的根，pivot節點為子樹根節點的右孩子，pivot的右孩子、Y節點的左孩子不變，Y節點的右孩子變為pivot節點的左孩子。
實戰演練之增加、刪除節點時，如何保證紅黑樹的性質不被破壞。
往一個空的紅黑樹中，依次插入數據：12 1 9 2 0 11 7 19 4
節點為根節點，所以為黑色，兩個null節點為黑色節點。
按照二叉搜索樹的邏輯，9小於12、大於1，應該是1節點的右孩子。但，新增的兩個NIL節點已經使得12，1，9，NI這條路徑的黑色節點至少為兩個，而12，NIL這條路徑的黑色節點只有兩個。所以要對1節點進行左旋，9節點變為12節點的左孩子，發現問題還是存在。繼續，對12節點進行右旋，9節點為根節點，1、12分別為9節點的左右孩子。嘗試著色，9節點必須為黑色，而1，12節點可以為紅色，也可以為黑色。
0節點直接作為1節點的左孩子，保持跟2節點相同的顏色即可。左右子樹依舊保持平衡。
從二叉查找樹的性質看，7節點作為2節點的右孩子即可。這時來分析著色問題，我們先看最短路徑的黑色分布，9，12，NIL這條路徑，有三個黑色節點，以此為參考，嘗試改變9節點左子樹的著色。目前最長的路徑是9，1，2，7，NIL這條路徑。保持三個黑色節點的話，9跟NIL已經為黑色節點，而紅色節點又不能挨著，所以只能是1為紅色節點，2為黑色節點，7為紅色節點。那麼9，1，0，NIIL這條路徑，0就要為黑色節點。調整完畢。
19節點作為12節點的右孩子，與左孩子保持一樣的紅色即可。
4節點應該作為7節點的左子樹，無論著什麼顏色，以1節點為根節點的子樹，都要破壞紅黑性質。所以應該進行旋轉。先以7為根節點進行一次右旋，再以2為根節點進行一次左旋。嘗試著色即可。
類似插入節點的分析、總結，刪除節點也可以針對每種場景找到固定的著色方法，就像玩一個游戲，有自己的推理跟玩法。我先做個PPT，這塊稍後補充。
所有的插入、刪除都是有限個情況，基於插入、刪除的情況分析，即可編寫演算法生成紅黑樹，使其在固定的業務場景中發揮紅黑樹穩定操作效率的特色了。
在 計算機科學 中， AVL樹 是最先發明的 自平衡二叉查找樹 。在AVL樹中任何節點的兩個 子樹 的高度最大差別為一，所以它也被稱為 高度平衡樹 。查找、插入和刪除在平均和最壞情況下都是 O （log n ）。增加和刪除可能需要通過一次或多次 樹旋轉 來重新平衡這個樹。
節點的 平衡因子 是它的左子樹的高度減去它的右子樹的高度（有時相反）。帶有平衡因子1、0或 -1的節點被認為是平衡的。帶有平衡因子 -2或2的節點被認為是不平衡的，並需要重新平衡這個樹。平衡因子可以直接存儲在每個節點中，或從可能存儲在節點中的子樹高度計算出來。
不提問題的碼農不是好程序員。自己寫完了紅黑樹的簡單剖析，感覺還是只懂皮毛，沒有從觸碰到演算法的核心內容。所以，不妨留幾個小問題，擔心自己腦子生銹或者沒事想玩手機的時候，再提筆研究下紅黑樹。
教你初步了解紅黑樹
演算法的時間復雜度和空間復雜度-總結
紅黑樹從頭至尾插入和刪除
AVL樹
紅黑樹C源碼實現與剖析
Echo
8 Nov，2016
㈢ 求紅黑樹應用實例，謝謝！
紅黑樹用在關聯數組、字典的實現上。需要的空間比散列表小。
任何鍵值對應，需要隨機存儲和鍵有序的情況都可以用。
實例中
內存中比如緩存的(區塊-數據)，編號對應內容，引索號對應數據項
日期對應日程。價格對應商品。
應用遍及，在內存中使用效率比較高
㈣ HashMap與SparseArray簡單總結
HashMap：
1、hashMap採用了數組+鏈表+紅黑樹來存儲數據。
2、每一個鍵值對封裝為一個節點Node<K,V>,存在一個數組Node<K,V>[] table，其元素為Node節點。其次，數組中每個元素也都有一個鏈表結構，此鏈表用來存儲下標位置相同但內容不同的節點，每有一個這樣的節點就插入到鏈表尾部。
3、put操作時，使用key的hashcode值計算其在table中的數組索引，遍歷數組，找到該索引元素，如果為空，則直接將node插入到當前數組位置。
4、若不為空，判斷兩個key的hashcode值和內容是否相等，相等則直接替換value，插入完成。
5、若兩個節點不是同一個，那麼開始遍歷節點所在的鏈表，在鏈表中查找比較key，沒有查找到則插入到鏈表尾部。若鏈表size大於8，則將其轉為紅黑樹，將節點插入到樹中。為什麼是8呢，可以看下源碼里的解釋，
``
``
設為8其實是一個保底策略。因為鏈表的長度分布滿足泊松分布，長度為8的概率為千萬分之六，可以說接近於0了。這么設置的用意在於，保證在極端情況下，鏈表不會無限制增長，否則查找消耗會非常大。此時將其轉為紅黑樹，查找效率會優於鏈表。而只要我們哈希函數設置合理的話，鏈表的長度基本都達不到8，也不會出現轉為紅黑樹的最差情況。
6、table的初始size為16，每次添加完table元素後會判斷是否超出，超出就進行擴容，擴容size總為2的冪。還有一個關鍵的屬性，負載因子loadFactor，初始值為0.75。這個負載因子表示table的存儲空間利用率，我們知道，table不是所有位置都會存儲元素的。為什麼要設為0.75，首先，如果這個負載因子越大，表明空間利用率越高，擴容的次數相對就少，但是這樣在插入新元素時發生位置碰撞的幾率就越大，進而就會增加對應鏈表的長度，那麼鏈表變長了，查詢效率相應地就變低了；而若負載因子越小，那麼空間利用率越低，table中空閑位置越多，同樣的表的長度相對地只能存儲更少的元素，因此插入元素時發生擴容操作的機會就越大，元素更多的是存在table數組中，而不是發生沖突存到鏈表中，查找效率會比較快。
總結起來，上述兩種情況各有優劣。綜合考慮空間開銷和查找效率，負載因子既不能太大也不能太小。又因為，鏈表的長度滿足泊松分布，大於8的幾率微乎其微，把負載因子設為0.75，鏈表長度基本不可能超過8，同時更不可能轉化為紅黑樹了。所以設為0.75是在通常情況下，綜合考慮了查找效率和空間開銷的折衷選擇。
7、關於紅黑樹，它也是一種二叉搜索樹，紅黑樹的查找效率優於二叉搜索樹，增刪的效率優於平衡二叉樹。可以認為是結合了兩者的優點。
SparseArray：
1、sparsearray採用了int[] mKeys 和 Object[] mValues兩個數組來分別存儲key和value。
2、對於某個key值，先查找其在mKeys中的索引i，直接mValues[i]獲取key對應的value，也就是說key與其對應的value存儲下標是一樣的。
且看sparsearray的put方法，非常易懂，
``
public void put(int key, E value) {
int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
``
3.sparsearray對mKeys數組做了正序排列，因此，在進行遍歷查找key時，使用的是二分查找法，一切為了效率。
4.sparsearray使用int類型，不同與hashmap使用Integer，省去了自動裝箱過程，消耗更少內存。
總的來說，sparseArray內存性能優於hashMap，一般適用於key為整型值，數據量較少的應用場景。也是考慮內存優化時替代Hash Map的首選。
㈤ 什麼是紅黑樹
紅黑樹（Red Black Tree） 是一種自平衡二叉查找樹，是在計算機科學中用到的一種數據結構，典型的用途是實現關聯數組。
紅黑樹是在1972年由Rudolf Bayer發明的，當時被稱為平衡二叉B樹（symmetric binary B-trees）。後來，在1978年被 Leo J. Guibas 和 Robert Sedgewick 修改為如今的「紅黑樹」。
樹的旋轉
當我們在對紅黑樹進行插入和刪除等操作時，對樹做了修改，那麼可能會違背紅黑樹的性質。
為了保持紅黑樹的性質，我們可以對相關結點做一系列的調整，通過對樹進行旋轉（例如左旋和右旋操作），即修改樹中某些結點的顏色及指針結構，以達到對紅黑樹進行插入、刪除結點等操作時，紅黑樹依然能保持它特有的性質（五點性質）。
㈥ 紅黑樹的用途
紅黑樹用在關聯數組、字典的實現上。需要的空間比散列表小。 任何鍵值對應,需要隨機存儲和鍵有序的情況都可以用。
㈦ 紅黑樹和平衡二叉樹 區別
紅黑樹和平衡二叉樹的主要區別如下：
平衡二叉樹（AVL）樹是嚴格的平衡二叉樹，平衡條件必須滿足（所有節點的左右子樹高度差不超過1）。不管我們是執行插入還是刪除操作，只要不滿足上面的條件，就要通過旋轉來保持平衡，而的英文旋轉非常耗時的。所以平衡二叉樹（AVL）適合用於插入與刪除次數比較少，但查找多的情況。
紅黑樹在二叉查找樹的基礎上增加了著色和相關的性質使得紅黑樹相對平衡，從而保證了紅黑樹的查找、插入、刪除的時間復雜度最壞為O(log
n)。所以紅黑樹適用於搜索，插入，刪除操作較多的情況。
(7)紅黑樹主要用來存儲有序的數據擴展閱讀：
平衡二叉樹在Windows
NT內核中廣泛存在。
紅黑樹的應用：
1、在C
++的STL中，地圖和集都是用紅黑樹實現的；
2、著名的Linux的的進程調度完全公平調度程序，用紅黑樹管理進程式控制制塊，進程的虛擬內存區域都存儲在一顆紅黑樹上，每個虛擬地址區域都對應紅黑樹的一個節點，左指針指向相鄰的地址虛擬存儲區域，右指針指向相鄰的高地址虛擬地址空間；
3、IO多路復用的epoll的的的實現採用紅黑樹組織管理的sockfd，以支持快速的增刪改查；
4、Nginx的的的中用紅黑樹管理定時器，因為紅黑樹是有序的，可以很快的得到距離當前最小的定時器；
5、Java中的TreeMap中的實現。
參考資料：
網路-平衡二叉樹
網路-紅黑樹
㈧ 紅黑樹的術語
紅黑樹是一種特定類型的二叉樹，它是在計算機科學中用來組織數據比如數字的塊的一種結構。所有數據塊都存儲在節點中。這些節點中的某一個節點總是擔當起始位置的功能，它不是任何節點的兒子，我們稱之為根節點或根。它有最多兩個兒子，都是它連接到的其他節點。所有這些兒子都可以有自己的兒子，以此類推。這樣根節點就有了把它連接到在樹中任何其他節點的路徑。
如果一個節點沒有兒子，我們稱之為葉子節點，因為在直覺上它是在樹的邊緣上。子樹是從特定節點可以延伸到的樹的某一部分，其自身被當作一個樹。在紅黑樹中，葉子被假定為 null 或空。
由於紅黑樹也是二叉查找樹，它們當中每一個節點的比較值都必須大於或等於在它的左子樹中的所有節點，並且小於或等於在它的右子樹中的所有節點。這確保紅黑樹運作時能夠快速的在樹中查找給定的值。
㈨ 紅黑樹-演算法導論
這個周看演算法導論，看到紅黑樹，看的我雲里霧里繞啊。雖然最後看懂了，據我估計，要是過一個星期不看保證忘干凈，因此決定寫篇博客記錄下紅黑樹。
紅黑樹是二叉樹的一種，所以學習紅黑樹必須先搞懂二叉樹。
如圖，一顆二叉樹是按照結點（二叉樹結構）組成的。每個結點可以用鏈表結構標示。每個結點都應該有left right p ，他們分別指向左兒子，右兒子和父結點。每個結點還應該有個關鍵字key。如果某個兒子結點不存在，則相應位置就是nil。跟結點是樹中唯一的父結點值是nil的節點。
設x為二叉樹中的一個結點，如果y是x的左子樹中的一個結點，則key[y]<=key[x]。如果y是x的右子樹中的一個結點，則key[x]<=key[y]
我們有很多結點，如何將他組合成符合二叉樹性質的二叉樹呢？
我們一般通過下面兩種方式遍歷二叉樹中的key
樹根的關鍵字（key）在左子樹和右子樹的關鍵字之間輸出就是 中序遍歷演算法
樹根的關鍵字（key）在左子樹和右子樹的關鍵字之前輸出就是 前序遍歷演算法
從圖中我們能看出只要沿著各個結點的left指針查找下去，知道遇見nil 時候為止，就是最小值，最大值正好相反。
如圖，3的前趨是2， 後繼是6。
前趨後繼的規律是什麼呢?
前趨：如果結點x的左子樹為非空，則x的前趨就是做子樹中的最右結點。要是x的左子樹為nil ，並且有前趨y（key是最最小值對應的x是沒有前趨的），那麼y是x的最低祖先，並且y的右兒子也是x的祖先。（x必須出現在y的右兒子的分支中，並且y是最低祖先）
後繼：如果結點x的右子樹為非空，則x的後繼就是右子樹中的最左結點。要是x的右子樹為nil ，並且有後繼y（key是最大值對應的x是沒有後繼的），那麼y是x的最低祖先，並且y的左兒子也是x的祖先。（x必須出現在y的左兒子的分支中，並且y是最低祖先）
這里一定要搞明白，因為這里是紅黑樹刪除的基礎部分。
二叉樹結點的刪除分三種情況。
這里針對第三種情況的刪除，我們不是刪除z，而是刪除的是z的後繼y，把y的值賦值給z，這樣不破壞樹中的結構。變成了只是刪除了一個葉子，這個葉子的特點是 左兒子是nil 。
紅黑樹是一種二叉查找樹，但在每個結點上增加一個存儲位表示結點的顏色，可以是RED或者Black。通過對任何一條從跟到葉子的路徑上各個結點著色方式的限制，紅黑樹確保沒有一條路徑會比其他路徑長出兩倍，因而是接近平衡的。
樹中每個結點包含五個域：color，key ，left，right 和p。如果某結點沒有一個子結點或者父結點，則該結點相應的指針為nil。
從圖中我們能看出每個葉子節點都是nil。nil對象都是一樣的。幹嘛不用一個nil 代替呢。因此如下結構。
旋轉應該是二叉樹的性質，只是普通二叉樹沒必要旋轉。紅黑樹需要旋轉來平衡樹結構。
結果如下。
右旋的過程只是相反而已。
左旋的作用是將右兒子變成父結點。
右旋的作用是將左兒子變成父結點。
這樣變化有什麼用處呢？
我們知道，紅黑樹就是二叉樹，因此向二叉樹中插入數據沒有啥區別。只是不過，當我們插入結點的某些時候就破壞了紅黑樹性質。因此，我們需要對二叉樹進行調整讓其適合紅黑樹的特性。
下面我們應該分析什麼情況下插入結點能破壞紅黑樹。
假如我們插入的結點是黑色的，肯定是破壞了二叉樹的性質5。（除非是根節點不破壞。）
但是我們插入的結點是紅色的，不一定破壞二叉樹的五條性質，為了方便，我們還是將二叉樹插入的結點染成紅色的比較好。(情況變少)
當我們插入一個紅色結點可能破壞那些性質呢？第一條和第三條肯定是不會被破壞的，恆成立的。第五條因為插入的結點是紅色的肯定也是成立的。這里可能不成立的是第二條（跟結點是黑的，要是插入的結點就是根結點）和第四條（如果一個結點是紅的，它的兩個兒子是黑的，因為要是插入的結點的父結點是紅的話，那麼父父結點就不符合要求了）。
因此，紅黑樹的結構被破壞就兩種情況，不是性質2就是性質4.
性質2好解決，將結點染成黑色的就行了。不做分析。
我們重點分析性質4破壞，我們如何修正。
我們知道性質4被破壞的條件是父節點是紅色的。
如圖
這里我們分情況討論 s 的顏色。
第一種情況 ： s的結點是紅色。
這個情況，我們從根到左邊的黑色結點數是2 ，右邊的黑色結點數是2。
那麼我們如何將其變成從跟到葉子的所有路線的結點數是2還不破壞紅黑樹呢？
只有下面一種變化才能符合紅黑樹，這樣從根向下就符合紅黑樹了。
將祖父結點（跟結點）變成紅色，p 和s 結點都變成 黑節點。
從上面的結果圖我們能看出來， 根父 的顏色不定，可能是紅色的，也可能是黑色的，那麼我們就應該讓 根 當做被插入的新節點，遍歷根父 的兄弟的結點的顏色情況情況。這其實就是遞歸了。
要是每個根父的兄弟結點都是紅色的話，那麼遍歷到根就結束了。將根染成黑色即可。要是根父的兄弟不是紅色，那麼就應該進入到第二種情況了。
第二種情況：s結點是黑色的。
這種情況不管如何變化，讓總結點數不變的情況下，單純染色根本沒有辦法讓所有結點符合紅黑樹特性。讓從根到葉子的路徑含有相同的黑色結點。 那麼怎麼辦呢？
我們知道，二叉樹可以旋轉，旋轉可以改變樹的結構。
這里我們用根做旋轉（左旋或者右旋），結果如下
我們看看旋轉結果，結果1，根變成p兒子的一邊黑色結點樹沒有變化。而x的一邊黑色結點數量減少了1。那我們如何讓x一邊增加1呢？只有如下一種情況，將p染成黑色，根染成紅色。
結果2是無法達到我們的要求的，因此我們需要拋棄掉這種情況，讓s是黑的時候只能變成結果1。
結果1所有的情況下都滿足紅黑樹，不需要進行遞歸了。
這里我們需要看看什麼情況下，x結點是p結點的兒子而不是根結點的兒子。這里我們需要看左旋右旋邏輯圖了。
因此這里我們總結下結果1 的條件
結果2 就是剩下的。那麼要是結果2的情況，我們應該如何處理呢。
那麼結果2 在右旋的結構圖就很清晰了。如下。p的右兒子是插入的結點x。
這種情況如何解決呢？
因為x是p的右兒子，所以旋轉只能是左旋轉。我們以p為根節點旋轉。
結果如下
這樣就變成了結果1 准備右旋轉的的情況了。
同理，情況2的左旋圖就變成了結果1准備左旋圖的情況了。
總結
這里上面的方法是演算法導論給出的，下面的是自己實現的。
刪除操作和二叉樹的操作一樣，同樣的只不過是刪除的時候，可能引起對紅黑樹性質的破壞。
這里把刪除二叉樹的總結搬過來
這里我們羅列下這三種情況各個刪除結點的結構。
二叉樹第一種情況：沒有兒子的情況。
二叉樹第二種情況：只有一個兒子。左兒子或者右兒子。有四種情況
二叉樹第三種情況：最多有一個右兒子
我們看出來，第三種情況不是第一種情況，就是第二種情況。因此這里我們只需要研究第一種情況和第二種情況就行了。
當x是紅色的時候
將x刪除，我們發現紅黑樹的黑色結點的數量不會發生任何變化。紅黑樹結構正常
我們發現不管什麼條件下，刪除紅色結點紅黑樹不會發生任何變化。
這里我們需要討論下 p 和 s的顏色，我們知道p 和s 分別只有紅色和黑色，並且p 和s 不能同時為紅色。那麼p 和s的組合情況只有三種了。
我們發現不管哪一種情況都刪除x的那一支都缺少一個黑色結點。
組合1
組合一通過染色是不可能達到樹的平衡的。（有人好說了，把p染成黑色，s染成紅色不就行了？我剛開始也犯了這個錯誤，要是s的兩個兒子是紅色怎麼辦呢？紅色是不參與節點數計算的。）
因此我們這里直能通過旋轉來改變樹的結構來看看能不能達到我們的要求。我們以p旋轉看看結果如下。
這貌似也不行，因為SL 可能是紅色的，違反性質4。因此我們可以看出來，p是紅色的情況下，旋轉一次想讓紅黑樹平衡依賴S的兩個結點的顏色。
要是p左旋，那麼s的左孩子是黑色的就可以。要是p右旋，那麼s的右孩子是黑色的就可以了。
因此這里討論下s的兩個孩子的顏色情況。
如果SL 和SR 都是紅色怎麼處理呢？
單純的旋轉根本不可能讓紅黑樹成立。只能先改變顏色在旋轉了。
顏色改變如下
要是SL 和SR都是黑色的情況下
結構圖如下
這種結構圖 SL SR 都是nil。這種情況下旋轉一下 p就行了。
SR SL只有一個顏色是紅色的。如果p的刪除分支是左兒子。那麼SL 是紅色，只能以s先右旋轉。這樣就變成了 SL SR都是黑色，但是s是紅色的情況。是SL ,SR變化成平衡樹的中間過程
最後這種情況，和SL SR 都是黑色一樣的處理。
組合2
這里我們單純靠染色是不可能實現樹平衡的。因為刪除x的結點的一支的結點都是黑色的。沒有可以改變的紅色結點存在。怎麼辦呢？我們只能通過旋轉將刪除的節點的一支上面增加紅色結點才行。這里有個s是紅色的，我們需要讓其到刪除結點分支上。
旋轉結果
這樣組合2刪除結點的分支上有紅色結點了。到這里我們發現這個地方的樹可能違反紅黑樹了。
違反1：根是紅色的話，s是紅色違反性質4.
違反2：p結點黑節點數量還是對不上。違反性質5
不過沒關系，要是我們能通過染色讓樹平衡的話，不用再調整樹的結構的話，那麼組合2也就算是解決了。
貌似通過染色也解決不了這個樹平衡的問題，不過違反的紅黑樹的地方可以減少，我們將s染成黑色，p染成紅色。
這里我們發現只有 p刪除結點的一支，黑色結點數量少一。正好是組合一的情況。按照組合一的情況做一次旋轉就可以解決問題
組合三
這種情況是最復雜的了。我們知道S要是紅色，這就是組合2的情況，要是p是紅色，那麼就是組合1了。那我們想辦法怎麼讓s或者p變成紅色的呢？我們先從葉子節點找紅色結點，看能不能讓s或者p變成紅色的。肯定是可以的。不過有一定條件。這里需要依賴SL,SR的顏色了。
當SL,SR都是紅色，這種變化只通過改變顏色就可以讓s變成紅色，變成組合2的情況。
當SL,SR 只有一個紅色的時候，通過改變顏色是不能達到要求的。因此我們就需要做旋轉來達到要求。
當SL SR 都是黑色。沒有紅色，p結點一下是不能解決這個問題的。那怎麼辦呢？這樣只能依賴p的父類了。不過這里需要注意的是p本身不平衡，我們這里依賴p的父類的時候，p需要是平衡的。如何平衡p呢？
我們只需要將s變成紅色就可以了。p就平衡了。
不過這里注意，p的這一整支的所有分支都是少黑色結點1 的。
這里我們注意到p只有一個兒子。這里我們需要把p當成刪除結點x的一個兒子。這樣就轉換成了x帶一個兒子的情況了。這種情況如何平衡樹。下面討論一個孩子的時候包含，暫時不在這里講解。
先拿一種情況分析 x是p的左兒子，x有一個左兒子
分析L 如果L是黑色的話，肯定是nil。因此可以將這種只有一個兒子的情況轉換成沒有兒子的情況。也可以這么說，要是x有兒子，兒子的顏色一定不是黑色。而是紅色。如圖
㈩ TreeMap理解
jdk:1.8
本文將介紹java中集合框架中實現 Map 介面 TreeMap ， TreeMap 實現 map 介面提供根據元素 key 自然排序或使用自定義排序規則來存儲元素，之前文章有介紹 HashMap 和 LinkedHashMap ，可以對比來查看有些地方是相似，建議查看本文之前閱讀之前介紹文章
TreeMap 元素默認排序是按照自然排序，對於 Integer 是按照升序，對於字元按照字母順序，下面例子：
上面增加key是無序，但是返回key的 set 是有升序，同時使用字元串，存儲是自然序-字母順序
下面是例子：
TreeMap 不像 hash map 和linked hash map，不需要hash來定位元素位置，因為沒有使用數組來存儲元素
如果自然排序不能滿足需求，初始化時候可以自定義排序規則，下面例子使用 Integer 降序排列：
hashMap 不能保證key排序存儲和出現相同排序，但是 TreeMap 可以保證key總是有序性存儲
現在已經知道TreeMap存儲元素是有序，因為 TreeMap 屬性，可以查詢最大，最小，查找key小於或者大於固定值，等等，下面介紹小部分情況例子：
TreeMap 實現 NavigableMap 介面和內部工作規則使用紅黑樹：
紅黑樹超過了本文介紹訪問，然而這些key存儲是有序
首先：紅黑數保證元素數據結構一致性，可以想像是棵芒果樹在天空下，樹上分支向下成長，樹的根節點元素是第一個節點，從根節點出發，任何元素左節點小於中間節點，右節點大於中間節點，定義大於或者小於自然排序或者自定義排序初始化時候，這個規則保證 TreeMap 元素總是有序和可以預測順序
第二：紅黑樹是自平衡樹，以上屬性保證基本操作，例如：搜索 、獲取、增加、和刪除時間復雜度是O(log n),在增加和刪除過程中，會改變樹形狀，樹的長分支搜索需要時間比較長，短分支需要時間短， TreeMap 自平衡保證紅黑樹特性，不會使上面情況發生，因此考慮到使用紅黑樹設計，對每次刪除和插入，最大樹高度被維持需要時間復雜度O(log n)，例如 樹自平衡，
上面hash map 和linked hash map，tree map不是線程安全，因此多線程環境處理方式和之前講相似
之前介紹 HashMap 和 LinkedHashMap 實現，現在是 TreeMap ，很重要概況下它們三者之區別：
HashMap 適合一般場景，實現提供存儲和 獲取操作，缺點是存放元素是無序和，在排序場景 性能低下，需要遍歷所有元素來進行排序
TreeMap 完全自己控制key` 排序，在另一方面，性能會比其他性能差
TreeMap 在沒有引起性能問題情況下，linked hash map提高hash map排序問題
本文討論 java 中 TreeMap 和內部實現,因此最後一系列文章中討論共同 map 介面實現，簡單討論
之間優缺點使用情況