線程不安全，但是因為需要排序，進行key的compareTo方法，是以key是不能null中，value是可以的。
首先庖丁解牛,類似于如何把大象裝入冰箱,分三步走:
-
以排序二叉樹的方式新增節點
因為紅黑樹首先本身就是一個排序二叉樹
-
标記它為紅色
如果設為黑色，就會導緻根到葉的路徑上有一條路上，多一個額外的黑節點，打破性質 5,這個很難調整
但設為紅色節點後，可能會導緻出現兩個連續紅色節點的沖突，那麼可以通過
-
顔色調換（color flips）和樹旋轉
調整
之後再要進行什麼操作就取決于其他臨近節點的顔色
注意到:
- 性質1/2/3總是保持
- 性質4隻在增加紅色節點、重繪黑色節點為紅色，或做旋轉時受到威脅
- 性質5隻在增加黑色節點、重繪紅色節點為黑色，或做旋轉時受到威脅
在下面的示意圖中，
- 要插入的節點标為N
- N的父節點标為P
- N的祖節點标為G
- N的叔節點标為U
圖中展示的任何顔色要麼是由它所處情形這些所作的假定，要麼就是由假定所自然推出的
插入情境分類
1 N 位于樹的根,即無父節點
直接将新插入節點設定為根即可.
這種情形下，把它繪為黑色 - 滿足性質2
它在每個路徑上對黑節點數目加一 - 滿足性質5
2 P 是黑色
直接将N插入即可，不會破壞性質4(N 是紅色的).
在這種情形下,性質5未受到威脅，盡管N有兩個黑色葉子子節點；但由于N是紅色，通過它的每個子節點的路徑就都有同通過它所取代的黑色的葉子的路徑同樣數目的黑色節點，是以依然滿足這個性質。
在下面情境下,假定P為紅色，是以它有祖節點G.
因為若P是根，則P就應是黑色。是以N總有一個叔節點，盡管在情形4和5下它可能是葉節點
這種情況下會破壞性質 4,是以又分為如下幾種情境:
3 P 和 U都是紅色
此時N做為P的左孩子或右孩子都屬于本情境.
- 這裡僅圖解N做為P左孩子的情境
将G設為紅色，P和U設為黑色 - 以保持性質5.
現在N有了一個黑色的父節點P。因為通過父節點P或叔節點U的任何路徑都必定通過祖節點G，在這些路徑上的黑節點數目沒有改變.
But!
紅色的祖節點G可能是根,破壞性質2
也可能祖節點G的父節點是紅色的，破壞性質4
為了解決這個問題，在祖節點G遞歸進行情境1.
以下情境，假定P是G的左子節點
4 P是紅色,U是黑色或缺少,N是P的右孩子
左旋P,調換 N 和 P 的角色
這個改變會導緻某些路徑通過它們以前不通過的N（比如圖中的1号葉節點）或不通過P（比如圖中3号葉節點），但由于這兩個節點都是紅色，性質5仍有效
但P和N還是連續的兩個紅色節點，破壞性質 4還，怎麼辦?看情境5
5 P是紅色,U是黑色或缺少，N是P的左子節點
操作前G是黑色，否則P不可能是紅色(如果P和G都是紅色就破壞了性質4)
右旋G，将P設為黑色，G設為紅色，達到平衡.此時P是黑色，不用擔心P的父節點是紅色.
圖解完畢,我們來看源碼吧!
public V put(K key, V value) {
// 根節點
Entry<K,V> t = root;
// 若根為空
if (t == null) {
compare(key, key); // 類型校驗(可能是 null)
// 建立一個根
root = new Entry<>(key, value, null);
// 有一個根元素了
size = 1;
// 修改計數器勿忘加一
modCount++;
// 傳回
return null;
}
// 記錄比較結果
int cmp;
Entry<K,V> parent;
// split comparator and comparable paths
// 目前使用的比較器
Comparator<? super K> cpr = comparator;
// 若比較器字段非空，直接使用指定的比較器
if (cpr != null) {
// 循環查找key要插入的位置(也就是新節點的父節點)
do {
// 記錄上次循環的節點t
parent = t;
// 比較目前節點key和新插入節點key的大小
cmp = cpr.compare(key, t.key);
// 新key小，以目前節點的左孩子節點為新的比較節點
if (cmp < 0)
t = t.left;
// 新key大，則以目前節點的右孩子節點為新的比較節點
else if (cmp > 0)
t = t.right;
else
// 目前節點key和新key相等，則覆寫value并傳回
return t.setValue(value);
// 當t為null，即沒有要比較節點時，表已找到新節點要插入位置
} while (t != null);
}
// 比較器為空,使用 key 的比較器
else {
// 是以要求key不能為null，并且須實作Comparable接口
if (key == null)
throw new NullPointerException();
@SuppressWarnings("unchecked")
Comparable<? super K> k = (Comparable<? super K>) key;
// 和之前類似，循環查找要插入的位置
do {
parent = t;
cmp = k.compareTo(t.key);
if (cmp < 0)
t = t.left;
else if (cmp > 0)
t = t.right;
else
return t.setValue(value);
} while (t != null);
}
// 找到新節點的父節點後，建立節點
Entry<K,V> e = new Entry<>(key, value, parent);
// 新節點key值小于父節點key
if (cmp < 0)
// 插在父節點左子處
parent.left = e;
// 如果新節點key值大于父節點key
else
// 插在父節點的右子處
parent.right = e;
// 插入新節點後，為維持平衡，調整紅黑樹
fixAfterInsertion(e);
// 元素數量加一
size++;
// 修改計數器加一
modCount++;
return null;
} 下面來看新增節點後對紅黑樹的調整方法
private void fixAfterInsertion(Entry<K,V> x) {
// 将新插入節點的顔色設定為紅色
x.color = RED;
// 循環保證新插入節點x不是根或其父節點不是紅色(這兩種情況無需調整)
while (x != null && x != root && x. parent.color == RED) {
// 若x的父節點是祖節點的左孩子
if (parentOf(x) == leftOf(parentOf (parentOf(x)))) {
// 擷取x的叔節點
Entry<K,V> y = rightOf(parentOf (parentOf(x)));
// 若x的父節點是紅色
if (colorOf(y) == RED) {
// 将x的父節點設為黑色
setColor(parentOf (x), BLACK);
// 将x的叔叔節點設定為黑色
setColor(y, BLACK);
// 将x的祖節點設為紅色
setColor(parentOf (parentOf(x)), RED);
// 将x指向祖節點
// 若x的祖節點的父節點是紅色，按照之前流程繼續循環
x = parentOf(parentOf (x));
} else {
// 若x的叔節點是黑色或缺少，且x的父節點是祖節點的右孩子
if (x == rightOf( parentOf(x))) {
// 左旋父節點
x = parentOf(x);
rotateLeft(x);
}
// 若x的叔叔節點是黑色或缺少，且x的父節點是祖父節點的左孩子
// 将x的父節點設為黑色
setColor(parentOf (x), BLACK);
// 将x的祖節點設為紅色
setColor(parentOf (parentOf(x)), RED);
// 右旋x的祖節點
rotateRight( parentOf(parentOf (x)));
}
// 若x的父節點是祖節點的右孩子，流程和上面類似，隻是左旋右旋區分，不再贅述
} else {
Entry<K,V> y = leftOf(parentOf (parentOf(x)));
if (colorOf(y) == RED) {
setColor(parentOf (x), BLACK);
setColor(y, BLACK);
setColor(parentOf (parentOf(x)), RED);
x = parentOf(parentOf (x));
} else {
if (x == leftOf( parentOf(x))) {
x = parentOf(x);
rotateRight(x);
}
setColor(parentOf (x), BLACK);
setColor(parentOf (parentOf(x)), RED);
rotateLeft( parentOf(parentOf (x)));
}
}
}
// 最後将根設定為黑色,反正根節點就得是黑色
root.color = BLACK;
} 下面來看下左旋和右旋的代碼
/**
* 左旋示意圖:
* px px
* / /
* x y
* / \ --(左旋)-- / \
* lx y x ry
* / \ / \
* ly ry lx ly
*
*/
private void rotateLeft(Entry<K,V> p) {
if (p != null) {
// 擷取p的右孩子
Entry<K,V> r = p.right;
// 将 r的左孩子 設為 p的右孩子
p.right = r.left ;
// 若r的左孩子非空，将p設為r的左孩子的父
if (r.left != null)
r.left.parent = p;
// 将p的父設為y的父
r.parent = p.parent;
// 若p的父為空，則将r設為根
if (p.parent == null)
root = r;
// 若p是其父的左孩子，則将r設為p的父節點的左孩子
else if (p.parent.left == p)
p.parent.left = r;
else
// 若p是其父的右孩子，則将r設為p的父節點的右孩子
p.parent.right = r;
// 将p設為r的左孩子
r.left = p;
// 将p的父設為r
p.parent = r;
}
} /**
* 右旋示意圖(對節點y右旋)：
* py py
* / /
* y x
* / \ --(右旋)-- / \
* x ry lx y
* / \ / \
* lx rx rx ry
*
*/
private void rotateRight(Entry<K,V> p) {
if (p != null) {
// 擷取p的左孩子
Entry<K,V> l = p. left;
// 将l的右孩子設為p的左孩子
p.left = l.right ;
// 若l的右孩子非空，将p設為l的右孩子的父
if (l.right != null) l. right.parent = p;
// 将p的父設為l的父
l.parent = p.parent ;
// 若p的父為空,則将l設為根
if (p.parent == null)
root = l;
// 若p是其父的右孩子，則将l設為p的父節點的右孩子
else if (p.parent.right == p)
p.parent.right = l;
// 若p是其父節點的左孩子,将l設為p的父節點的左孩子
else p.parent.left = l;
// 将p設為l的右孩子
l.right = p;
// 将l設為p父節點
p.parent = l;
}
}