紅黑樹：自平衡的排序二叉樹。
特性：它是一顆空樹或它的左右兩個(gè)子樹的高度差的絕對(duì)值不超過1悬荣，并且左右兩個(gè)子樹都是一棵平衡二叉樹骑冗。即對(duì)于其中任意一個(gè)子節(jié)點(diǎn)，其左右子樹的高度都相近隆豹。
一棵有效的紅黑樹規(guī)則有5點(diǎn)：
（1）每個(gè)節(jié)點(diǎn)都只能是紅色或者黑色
（2）根節(jié)點(diǎn)是黑色
（3）每個(gè)葉節(jié)點(diǎn)（NIL節(jié)點(diǎn)椭岩，空節(jié)點(diǎn)）是黑色的
（4）如果一個(gè)結(jié)點(diǎn)是紅的，則它兩個(gè)子節(jié)點(diǎn)都是黑的璃赡。也就是說一條路徑上不能出現(xiàn)相鄰的兩個(gè)紅色結(jié)點(diǎn)
（5）從任一節(jié)點(diǎn)到其每個(gè)葉子的所有路徑都包含相同數(shù)目的黑色節(jié)點(diǎn)判哥。
紅黑樹主要三大操作：左旋、右旋碉考、著色塌计。
重點(diǎn)在于其節(jié)點(diǎn)的增刪時(shí)旋轉(zhuǎn)的選擇問題，這也是最大的難點(diǎn)侯谁。（需要多研究）
TreeMap繼承AbstractMap锌仅，實(shí)現(xiàn)NavigableMap、Cloneable墙贱、Serializable三個(gè)接口热芹。其中AbstractMap表明TreeMap為一個(gè)Map即支持key-value的集合，
NavigableMap則意外著其支持一系列的導(dǎo)航方法惨撇，具備針對(duì)給定搜索目標(biāo)返回最接近匹配項(xiàng)的導(dǎo)航方法伊脓。
TreeMap中幾個(gè)重要的屬性
//比較器，因?yàn)門reeMap是有序的串纺，通過comparator接口我們可以對(duì)TreeMap的內(nèi)部排序進(jìn)行精密的控制
private final Comparator<? super K> comparator;
//TreeMap紅-黑節(jié)點(diǎn)丽旅，為TreeMap的內(nèi)部類
private transient Entry<K,V> root = null;
//容器大小
private transient int size = 0;
//TreeMap修改次數(shù)
private transient int modCount = 0;
//紅黑樹的節(jié)點(diǎn)顏色--紅色
private static final boolean RED = false;
//紅黑樹的節(jié)點(diǎn)顏色--黑色
private static final boolean BLACK = true;
鏈接：# Comparable和Comparator的區(qū)別
Comparable
Comparable可以認(rèn)為是一個(gè)內(nèi)比較器，實(shí)現(xiàn)了Comparable接口的類有一個(gè)特點(diǎn)纺棺，就是這些類是可以和自己比較的榄笙，至于具體和另一個(gè)實(shí)現(xiàn)了Comparable接口的類如何比較，則依賴compareTo方法的實(shí)現(xiàn)祷蝌，compareTo方法也被稱為自然比較方法茅撞。如果開發(fā)者add進(jìn)入一個(gè)Collection的對(duì)象想要Collections的sort方法幫你自動(dòng)進(jìn)行排序的話，那么這個(gè)對(duì)象必須實(shí)現(xiàn)Comparable接口。compareTo方法的返回值是int米丘，有三種情況：
1剑令、比較者大于被比較者（也就是compareTo方法里面的對(duì)象），那么返回正整數(shù)
2拄查、比較者等于被比較者吁津，那么返回0
3、比較者小于被比較者堕扶，那么返回負(fù)整數(shù)
Comparator
Comparator可以認(rèn)為是是一個(gè)外比較器碍脏，個(gè)人認(rèn)為有兩種情況可以使用實(shí)現(xiàn)Comparator接口的方式：
1、一個(gè)對(duì)象不支持自己和自己比較（沒有實(shí)現(xiàn)Comparable接口）稍算，但是又想對(duì)兩個(gè)對(duì)象進(jìn)行比較
2典尾、一個(gè)對(duì)象實(shí)現(xiàn)了Comparable接口，但是開發(fā)者認(rèn)為compareTo方法中的比較方式并不是自己想要的那種比較方式
Comparator接口里面有一個(gè)compare方法糊探，方法有兩個(gè)參數(shù)T o1和T o2钾埂，是泛型的表示方式，分別表示待比較的兩個(gè)對(duì)象科平，方法返回值和Comparable接口一樣是int褥紫，有三種情況：
1、o1大于o2匠抗，返回正整數(shù)
2故源、o1等于o2，返回0
3汞贸、o1小于o3绳军，返回負(fù)整數(shù)
對(duì)于葉子節(jié)點(diǎn)Entry是TreeMap的內(nèi)部類，它有幾個(gè)重要的屬性：
//鍵
K key;
//值
V value;
//左孩子
Entry<K,V> left = null;
//右孩子
Entry<K,V> right = null;
//父親
Entry<K,V> parent;
//顏色
boolean color = BLACK;
紅黑樹插入新節(jié)點(diǎn)的三個(gè)關(guān)鍵地方：
1矢腻、插入新節(jié)點(diǎn)總是紅色節(jié)點(diǎn)门驾。
2、插入節(jié)點(diǎn)的父節(jié)點(diǎn)是黑色多柑，能維持性質(zhì)奶是。
3、如果插入節(jié)點(diǎn)的父節(jié)點(diǎn)是紅色竣灌，破壞了性質(zhì)聂沙。故插入算法就是通過重新著色或旋轉(zhuǎn)，來維持性質(zhì)初嘹。
插入新節(jié)點(diǎn)的五種情況：
1及汉、新節(jié)點(diǎn)N為根節(jié)點(diǎn)：
直接插入，將顏色設(shè)置為黑色屯烦。
2坷随、父節(jié)點(diǎn)P為黑色：
新節(jié)點(diǎn)N同樣直接插入房铭，同時(shí)顏色為紅色，由于根據(jù)規(guī)則四它會(huì)存在兩個(gè)黑色的葉子節(jié)點(diǎn)温眉，值為null缸匪。同時(shí)由于通過它的子節(jié)點(diǎn)的路徑依然會(huì)保存著相同的黑色節(jié)點(diǎn)數(shù)，同樣滿足規(guī)則5.
3类溢、若父節(jié)點(diǎn)P和P的兄弟節(jié)點(diǎn)U都為紅色
對(duì)于這種情況若直接插入肯定出現(xiàn)不平衡現(xiàn)象凌蔬，如何處理？
P豌骏、U節(jié)點(diǎn)變黑龟梦、G節(jié)點(diǎn)變紅。這時(shí)由于經(jīng)過節(jié)點(diǎn)P窃躲、U的路徑都必須經(jīng)過G。所以在這些路徑上的黑色節(jié)點(diǎn)數(shù)目還是相同的钦睡。但是經(jīng)過上面的處理蒂窒，可能G節(jié)點(diǎn)的父節(jié)點(diǎn)也是紅色，這個(gè)時(shí)候需要將G節(jié)點(diǎn)當(dāng)做新增節(jié)點(diǎn)遞歸處理荞怒。
4洒琢、若父節(jié)點(diǎn)P為紅色，父節(jié)點(diǎn)兄弟節(jié)點(diǎn)U為黑色或者缺少褐桌，則新增節(jié)點(diǎn)N為P節(jié)點(diǎn)的右孩子
對(duì)于這種情況衰抑，對(duì)新增節(jié)點(diǎn)N、P進(jìn)行一次左旋轉(zhuǎn)荧嵌。這里所產(chǎn)生的結(jié)果其實(shí)并沒有完成呛踊，還是不平衡的（違反了規(guī)則四），這時(shí)我們需要進(jìn)行情況5的操作啦撮。
5谭网、父節(jié)點(diǎn)P為紅色，父節(jié)點(diǎn)兄弟節(jié)點(diǎn)U為黑色或者缺少赃春，則新增節(jié)點(diǎn)N為P節(jié)點(diǎn)的左孩子
這種情況可能由于情況四產(chǎn)生愉择，也有可能不是。對(duì)于這種情況织中，先以P為中心進(jìn)行右旋轉(zhuǎn)锥涕，在旋轉(zhuǎn)后產(chǎn)生的樹中，節(jié)點(diǎn)P是節(jié)點(diǎn)N狭吼、G的父節(jié)點(diǎn)层坠。但是這棵樹并不規(guī)范，它違反了規(guī)則4搏嗡，所以將P窿春、G節(jié)點(diǎn)的顏色進(jìn)行交換拉一，使之其滿足規(guī)范。開始時(shí)所有的路徑都需要經(jīng)過G,其它的黑色節(jié)點(diǎn)數(shù)一樣旧乞，但是現(xiàn)在所有的路徑改為經(jīng)過P蔚润，且P為整棵樹的唯一黑色節(jié)點(diǎn)，所以調(diào)整后的樹同樣滿足規(guī)范5尺栖。
上面展示了紅黑樹新增節(jié)點(diǎn)的五種情況嫡纠，這五種情況覆蓋了所有的新增可能，不管這棵紅黑樹多么復(fù)雜延赌，都可以根據(jù)這五種情況進(jìn)行生成除盏。
來源：https://blog.csdn.net/chenssy/article/details/26668941
詳情看連接，博主寫的挺好
