紅黑書的删除本質上是一個窮舉的過程
删除情況說明
-
删除的節點沒有子節點的情況
a) 如果為紅色，直接删除即可，不會影響黑色節點的數量
b) 如果為黑色，删除的時候需要進行平衡操作
- 删除的節點隻有一個子節點時，删除節點隻能是黑色，子節點也隻能是紅色。否則無法滿足紅黑樹黑色節點完全平衡的特性（從任一節點到其每個葉子的所有簡單路徑都包含相同數目的黑色節點）
- 如果删除節點有兩個子節點時，使用後繼節點作為替換的删除節點，然後再按照前面兩種情況處理
删除情況具體分析
1. 删除的節點沒有子節點（非null節點）的情況
a、如果為紅色，直接删除即可，不會影響黑色節點的數量
删除紅色節點（13）示例（不影響黑色節點數量，不需要平衡操作）
b、如果為黑色，删除的時候需要進行平衡操作
删除示例，删除節點11（平衡操作後面會介紹到）
2. 删除的節點隻有一個子節點時，删除節點隻能是黑色，子節點也隻能是紅色。
為什麼該情況下，删除節點隻能是黑色，子節點隻能是紅色,如圖所示:
由于該情況下删除節點的子節點隻有一個，并且是紅色，删除後直接将删除節點的子節點的顔色變黑，父節點和子節點連接配接即可。由于删除的黑色節點被變成黑色的紅色子節點頂上，整體不影響黑色節點的數量，還是符合紅黑樹的特性，是以不需要進行平衡操作。
删除節點動态示例，删除節點11（分别是含左子樹和右子樹的情況）：
左
右
3. 如果删除節點有兩個子節點時，使用前驅節點或後繼節點作為替換的删除節點，然後再按照前面兩種情況處理（本文示例以前驅節點為例）
找到的前驅節點有兩種情況，分别是前驅節點無子節點的情況和前驅節點隻有左子節點的情況.
同時删除節點和找到的前驅節點的顔色都不固定，是以又區分了好多情況。
下面示範示例隻示範其中一種，大概了解一下變化規則。具體的平衡邏輯在後面會介紹到。
比如删除節點100，首先會找到前驅節點60，然後替換内容後，将後繼節點删除。即将删除情況轉變成上面介紹到的兩種情況。删除完成後,再做節點平衡操作（後面會介紹具體平衡細節）。
删除示例，删除100節點
紅黑樹删除平衡情況分析
前面分析的三種情況，1.a 和 2 這兩種情況下删除比較簡單，不需要做紅黑樹節點平衡操作，而 3 這種情況之前也分析了，通過用前驅節點或者後繼節點替換被删除的節點，将删除情況轉換成1、2這種情況然後再删除，又由于1.a 和 2 不需要進行平衡處理，是以後面删除平衡操作主要圍繞1.b的情況分析。
首先為了友善後面的描述，對節點進行一個名稱的限制，如下圖所示：
對于删除平衡操作也是一個窮舉的過程（删除黑色節點引起的平衡問題）
分析： 删除節點的時候，找到前驅節點，并替換兩個節點的内容
- 如果找到要删除前驅節點含有子節點的情況時，前驅節點一定是黑色，前驅節點的子節點一定是紅色，這種情況就是上述第2種情況，删除前驅節點，将前驅節點變成黑色，不需要進行平衡操作。
- 如果找到要删除的前驅節點沒有子節點，并且前驅節點是紅色時。這種情況就是上述1.a 的情況，替換内容後直接删除即可，由于是紅色節點，不影響黑色節點的數量。是以不需要進行平衡操作。
- 如果找到要删除的前驅節點沒有子節點，并且前驅節點是黑色時，這種情況就是上述1.b的情況。因為删除的的是黑色節點，直接影響到紅黑樹中黑色節點的數量，需要進行數的平衡。這種情況比較複雜，後面内容就隻針對這種情況處理。
以下内容是删除的節點找到的前驅節點是沒有子節點的黑色節點的情況（也就是删除删除黑色葉子節點的情況）
-
S 是黑色的情況
a、 當 P 是 紅 色 \color{red}{當P是紅色} 當P是紅色，SL和SR是 NULL 時，删掉節點4
删掉節點4後，P變黑色，S變紅色即可完成黑色節點平衡。
HashMap源碼（七） —— 紅黑樹删除原理分析 動态圖解析！！！ b、 當 P 是 紅 色 \color{red}{當P是紅色} 當P是紅色，SL是紅色，SR是NULL
删除節點12，因為删除的是黑色節點，SL又是紅色的節點，可以利用這個紅色節點補充删除的黑色節點達到局部黑色節點平衡。
先已SL為圓心，右旋S節點，更改SL和S的顔色
再已SL為圓心，左旋P節點，再次更改P和SL節點的顔色即可
HashMap源碼（七） —— 紅黑樹删除原理分析 動态圖解析！！！ c、 當 P 是 紅 色 \color{red}{當P是紅色} 當P是紅色，SL是null，SR是紅色
類似上面一種場景
删除節點14後
以S為圓心，左旋P節點 即可達到平衡操作
HashMap源碼（七） —— 紅黑樹删除原理分析 動态圖解析！！！ d、當P是黑色，SL是null，SR是null
由于删除的是一個黑色節點，并且相鄰兄弟節點沒有紅色節點
是以在删除後左側這一塊是不可能平衡，就會影響到叔叔節點的顔色
HashMap源碼（七） —— 紅黑樹删除原理分析 動态圖解析！！！ d、當P是黑色，SL是紅色，SR是null
删除節點16 後，已SL為圓心，右旋S 節點，SL和S均變色
然後再以SL為原型左旋P節點 最終三個節點的顔色都變成黑色
HashMap源碼（七） —— 紅黑樹删除原理分析 動态圖解析！！！ ==d、當P是黑色，SL是null，SR是null紅色
同上面類似，以S為圓心，左旋P節點 最後都紅色節點變成黑色節點即可
HashMap源碼（七） —— 紅黑樹删除原理分析 動态圖解析！！！ -
S 是紅色的情況
和上面類似
具體變化細節可以用下面的網站工具實踐：
http://www.u396.com/wp-content/collection/data-structure-visualizations/RedBlack.html
保持平衡的原則就是節點的每個分支的黑色節點數是相同的
HashMap紅黑樹删除源碼分析
remove方法
/**
* 從HashMap中删除掉指定key對應的鍵值對，并傳回被删除的鍵值對的值
* 如果傳回空，說明key可能不存在，也可能key對應的值就是null
* 如果想确定到底key是否存在可以使用containsKey方法
*/
public V remove(Object key) {
Node<K,V> e; // 定義節點變量，用來存儲要被删除的節點（鍵值對）
return (e = removeNode(hash(key), key, null, false, true)) == null ?
null : e.value; // 調用removeNode方法
}
removeNode 方法
final Node<K,V> removeNode(int hash, Object key, Object value,boolean matchValue, boolean movable) {
/**
* tab 目前目前結點數組
* hash 對應的節點
* n 數組長度
* index 節點索引，通過hash 和 n計算得到
*/
Node<K,V>[] tab; Node<K,V> p; int n, index;
// 根據hash找到 index位置的節點，即樹的根節點或者連結清單的首節點
if ((tab = table) != null && (n = tab.length) > 0 &&
(p = tab[index = (n - 1) & hash]) != null) {
Node<K,V> node = null, e; K k; V v;
// 首節點或者根節點是目前key對應的節點的情況
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
node = p;
else if ((e = p.next) != null) { // 首節點或者根節點不是目前要删除對象的情況
// 樹結構的處理邏輯
if (p instanceof TreeNode)
node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
else { // 連結清單結構 周遊找到連結清單中目前key 對應的node節點
do {
if (e.hash == hash &&
((k = e.key) == key ||
(key != null && key.equals(k)))) {
node = e;
break;
}
p = e;
} while ((e = e.next) != null);
}
}
if (node != null && (!matchValue || (v = node.value) == value ||
(value != null && value.equals(v)))) {
if (node instanceof TreeNode)
// 樹節點的删除邏輯
// 窮舉删除節點以及紅黑書的平衡邏輯
((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
else if (node == p) // 連結清單結構的情況，并且是首節點
tab[index] = node.next; //直接将資料位置指向下一個節點即可
else //不是首節點的情況，将p的下一個節點指向要删除的下一個節點
p.next = node.next;
++modCount; //修改次數+1
--size; //size -1
afterNodeRemoval(node);
return node; // 傳回要删除的node節點
}
}
return null;
}