紅黑樹的用途

用於快速查詢元素，或者說快速根據關鍵字查詢值。和雜湊表不同，雜湊表是利用雜湊函數建立單向對映實現快速查詢。紅黑樹屬於二叉查詢樹，它使得樹的深度保持在O[ log(n) ]，查詢次數不多於最大深度，從而實現快速查詢。

紅黑樹的定義

1. 樹中有兩種顏色的節點，紅色和黑色（顧名思義）
2. 所有終端節點為黑色。終端節點（又稱葉子節點）就是null節點
3. 根節點是黑色
4. 不能有兩個連續的紅色節點（即每個紅色節點都有2個黑色節點）
5. 從根節點到終端節點路徑上的黑色節點個數相同

紅黑樹高效的原因

上述4、5最重要，找到終端可謂是最糟糕的情況了，即便的最壞的情況下，黑色節點都相同。那麼路徑最長的情況下是紅黑相間的情況下，最短情況是全部是黑色。顯然，到終端最長路徑不超過最短路徑的2倍。因此能夠保證樹的深度是O[ log(n) ]的（本人未證明），從而保證了效率。

紅黑樹的插入

首先要宣告一下，除了插入根節點之外，新插入的節點初始的顏色都是紅色的（後來可能會調整顏色）

1. 最簡單的情況——插入根節點

只需保證根節點為黑色，非常簡單。。。

2. 也很簡單的情況——新節點的父親是黑色的

沒有任何負面影響，因為即保證了紅色節點不連續，又不影響根節點到終端的黑色節點個數。原來是（黑）父親+（黑）孩子，現在是（黑）父親+（紅）新節點+（黑色）新節點的兒子

3. 新節點的父親是紅色的

這時候就出現了紅色節點連續的情況了，需要調整

3.1 新節點的叔叔是紅色的

把爺爺變成黑色，父親和叔叔變成紅色。首先在從太爺爺到終端的黑色節點個數不變，其次這個區域性沒有紅黑相間的情況。但是爺爺和太爺爺之間可能會出現2個連續紅色的情況，把爺爺設為新節點（current），繼續執行插入規律（上調）。

3.2 新節點的叔叔是黑色的

3.2.1 LL形式

這時候新的節點和父親出現了紅色相鄰的情況。這時候對爺爺進行右單旋，並且爺爺和父親交換顏色。注意的是可能會丟失父親的右孩子，它本來就是介於父親和爺爺的值，正好彌補了爺爺的左孩子。這樣依舊保證了紅黑樹性質，因為父親是黑色的，不需要上調。

3.2.2 LR形式

1. 先說一種一步到位的方法，就是讓父親和爺爺成為新節點的左兒子和右兒子，同時新節點的左子樹接到父親的右子樹，新節點的右子樹接到爺爺的左子樹。新節點和爺爺顏色交換，新節點設為黑色。
2. 顯然結果不存在連續的紅色節點，根節點到終端的黑色節點數也保持不變。
3. 新節點的左子樹本身大於父親小於新節點，新節點的右子樹小於爺爺大於新節點，旋轉後依然保持二元搜尋樹的性質

1. 再說一種兩步到位的方法，先對父親左單旋，注意新節點的左子樹接到父親的右子樹上，否則會丟失節點！這樣就轉換成了3.2.1 LL形式（對爺爺右單旋）。從程式設計的角度來說還是一步到位更有效率！

3.2.3 RR形式

是LL的映象對稱模式，一切取反即可，不再累述

3.2.4 RL形式

是LR的映象對稱模式，一切取反即可，不再累述

紅黑樹 vs AVL樹

1. 總結來說，AVL樹插入效率小於紅黑樹，AVL查詢效率大於紅黑樹
2. AVL可以保證左右子樹高度差絕對值不大於1並且是一顆二元搜尋樹
3. 插入時，AVL樹平衡性強，更容易引起不平衡觸發耗時的旋轉操作，紅黑樹只有在父親是紅色時才能觸發旋轉操作，「容納\忍耐」能力強一些，因此損耗更低。
4. 查詢時候，AVL可以保證左右子樹高度差絕對值不大於1，紅黑樹平衡性更差，所以深度略大，查詢效率略低一些。
5. 平均來說，紅黑樹效能>AVL效能
6. AVL樹介紹，參考我以前的部落格：AVL樹理解、證明

紅黑樹Java實現

參考我的實現：https://github.com/ghostorsoul/red_black_tree
程式碼解析未完待續。。。