JDK集合源碼之解析TreeMap(二)
刪除元素
刪除元素本身比較簡單，就是采用二叉樹的刪除規則。
- 如果刪除的位置有兩個葉子節點，則從其右子樹中取最小的元素放到刪除的位置，然後把刪除位置移到替代元素的位置，進入下一步。
- 如果刪除的位置隻有一個葉子節點（有可能是經過第一步轉換後的刪除位置），則把那個葉子節點作為替代元素，放到刪除的位置，然後把這個葉子節點刪除。
- 如果刪除的位置沒有葉子節點，則直接把這個刪除位置的元素刪除即可。
- 針對紅黑樹，如果刪除位置是黑色節點，還需要做再平衡。
- 如果有替代元素，則以替代元素作為當前節點進入再平衡。
- 如果沒有替代元素，則以刪除的位置的元素作為當前節點進入再平衡，平衡之後再刪除這個節點。
public V remove(Object key) {
// 獲取節點
Entry<K,V> p = getEntry(key);
if (p == null)
return null;
V oldValue = p.value;
// 刪除節點
deleteEntry(p);
// 返回刪除的value
return oldValue;
}
private void deleteEntry(Entry<K,V> p) {
// 修改次數加1
modCount++;
// 元素個數減1
size--;
if (p.left != null && p.right != null) {
// 如果當前節點既有左子節點，又有右子節點
// 取其右子樹中最小的節點
Entry<K,V> s = successor(p);
// 用右子樹中最小節點的值替換當前節點的值
p.key = s.key;
p.value = s.value;
// 把右子樹中最小節點設為當前節點
p = s;
// 這種情況實際上並沒有刪除p節點，而是把p節點的值改瞭，實際刪除的是p的後繼節點
}
// 如果原來的當前節點（p）有2個子節點，則當前節點已經變成原來p的右子樹中的最小節點瞭，也就是說其沒有左子節點瞭
// 到這一步，p肯定隻有一個子節點瞭
// 如果當前節點有子節點，則用子節點替換當前節點
Entry<K,V> replacement = (p.left != null ? p.left : p.right);
if (replacement != null) {
// 把替換節點直接放到當前節點的位置上（相當於刪除瞭p，並把替換節點移動過來瞭）
replacement.parent = p.parent;
if (p.parent == null)
root = replacement;
else if (p == p.parent.left)
p.parent.left = replacement;
else
p.parent.right = replacement;
// 將p的各項屬性都設為空
p.left = p.right = p.parent = null;
// 如果p是黑節點，則需要再平衡
if (p.color == BLACK)
fixAfterDeletion(replacement);
} else if (p.parent == null) {
// 如果當前節點就是根節點，則直接將根節點設為空即可
root = null;
} else {
// 如果當前節點沒有子節點且其為黑節點，則把自己當作虛擬的替換節點進行再平衡
if (p.color == BLACK)
fixAfterDeletion(p);
// 平衡完成後刪除當前節點（與父節點斷絕關系）
if (p.parent != null) {
if (p == p.parent.left)
p.parent.left = null;
else if (p == p.parent.right)
p.parent.right = null;
p.parent = null;
}
}
}
刪除再平衡
經過上面的處理，真正刪除的肯定是黑色節點才會進入到再平衡階段。
因為刪除的是黑色節點，導致整顆樹不平衡瞭，所以這裡我們假設把刪除的黑色賦予當前節點，這樣當前節點除瞭它自已的顏色還多瞭一個黑色，那麼：
（1）如果當前節點是根節點，則直接塗黑即可，不需要再平衡；
（2）如果當前節點是紅+黑節點，則直接塗黑即可，不需要平衡；
（3）如果當前節點是黑+黑節點，則我們隻要通過旋轉把這個多出來的黑色不斷的向上傳遞到一個紅色節點即可，這又可能會出現以下四種情況：
（假設當前節點為父節點的左子節點）
| 情況 | 策略 |
|---|---|
| 1）x是黑+黑節點，x的兄弟是紅節點 | （1）將兄弟節點設為黑色； （2）將父節點設為紅色； （3）以父節點為支點進行左旋； （4）重新設置x的兄弟節點，進入下一步； |
| 2）x是黑+黑節點，x的兄弟是黑節點，且兄弟節點的兩個子節點都是黑色 | （1）將兄弟節點設置為紅色； （2）將x的父節點作為新的當前節點，進入下一次循環； |
| 3）x是黑+黑節點，x的兄弟是黑節點，且兄弟節點的右子節點為黑色，左子節點為紅色 | （1）將兄弟節點的左子節點設為黑色； （2）將兄弟節點設為紅色； （3）以兄弟節點為支點進行右旋； （4）重新設置x的兄弟節點，進入下一步； |
| 3）x是黑+黑節點，x的兄弟是黑節點，且兄弟節點的右子節點為紅色，左子節點任意顏色 | （1）將兄弟節點的顏色設為父節點的顏色； （2）將父節點設為黑色； （3）將兄弟節點的右子節點設為黑色； （4）以父節點為支點進行左旋； （5）將root作為新的當前節點（退出循環）； |
（假設當前節點為父節點的右子節點，正好反過來）
| 情況 | 策略 |
|---|---|
| 1）x是黑+黑節點，x的兄弟是紅節點 | （1）將兄弟節點設為黑色； （2）將父節點設為紅色； （3）以父節點為支點進行右旋； （4）重新設置x的兄弟節點，進入下一步； |
| 2）x是黑+黑節點，x的兄弟是黑節點，且兄弟節點的兩個子節點都是黑色 | （1）將兄弟節點設置為紅色； （2）將x的父節點作為新的當前節點，進入下一次循環； |
| 3）x是黑+黑節點，x的兄弟是黑節點，且兄弟節點的左子節點為黑色，右子節點為紅色 | （1）將兄弟節點的右子節點設為黑色； （2）將兄弟節點設為紅色； （3）以兄弟節點為支點進行左旋； （4）重新設置x的兄弟節點，進入下一步； |
| 3）x是黑+黑節點，x的兄弟是黑節點，且兄弟節點的左子節點為紅色，右子節點任意顏色 | （1）將兄弟節點的顏色設為父節點的顏色； （2）將父節點設為黑色； （3）將兄弟節點的左子節點設為黑色； （4）以父節點為支點進行右旋； （5）將root作為新的當前節點（退出循環）； |
讓我們來看看TreeMap中的實現：
/**
* 刪除再平衡
*（1）每個節點或者是黑色，或者是紅色。
*（2）根節點是黑色。
*（3）每個葉子節點（NIL）是黑色。（註意：這裡葉子節點，是指為空(NIL或NULL)的葉子節點！）
*（4）如果一個節點是紅色的，則它的子節點必須是黑色的。
*（5）從一個節點到該節點的子孫節點的所有路徑上包含相同數目的黑節點。
*/
private void fixAfterDeletion(Entry<K,V> x) {
// 隻有當前節點不是根節點且當前節點是黑色時才進入循環
while (x != root && colorOf(x) == BLACK) {
if (x == leftOf(parentOf(x))) {
// 如果當前節點是其父節點的左子節點
// sib是當前節點的兄弟節點
Entry<K,V> sib = rightOf(parentOf(x));
// 情況1）如果兄弟節點是紅色
if (colorOf(sib) == RED) {
// （1）將兄弟節點設為黑色
setColor(sib, BLACK);
// （2）將父節點設為紅色
setColor(parentOf(x), RED);
// （3）以父節點為支點進行左旋
rotateLeft(parentOf(x));
// （4）重新設置x的兄弟節點，進入下一步
sib = rightOf(parentOf(x));
}
if (colorOf(leftOf(sib)) == BLACK &&
colorOf(rightOf(sib)) == BLACK) {
// 情況2）如果兄弟節點的兩個子節點都是黑色
// （1）將兄弟節點設置為紅色
setColor(sib, RED);
// （2）將x的父節點作為新的當前節點，進入下一次循環
x = parentOf(x);
} else {
if (colorOf(rightOf(sib)) == BLACK) {
// 情況3）如果兄弟節點的右子節點為黑色
// （1）將兄弟節點的左子節點設為黑色
setColor(leftOf(sib), BLACK);
// （2）將兄弟節點設為紅色
setColor(sib, RED);
// （3）以兄弟節點為支點進行右旋
rotateRight(sib);
// （4）重新設置x的兄弟節點
sib = rightOf(parentOf(x));
}
// 情況4）
// （1）將兄弟節點的顏色設為父節點的顏色
setColor(sib, colorOf(parentOf(x)));
// （2）將父節點設為黑色
setColor(parentOf(x), BLACK);
// （3）將兄弟節點的右子節點設為黑色
setColor(rightOf(sib), BLACK);
// （4）以父節點為支點進行左旋
rotateLeft(parentOf(x));
// （5）將root作為新的當前節點（退出循環）
x = root;
}
} else { // symmetric
// 如果當前節點是其父節點的右子節點
// sib是當前節點的兄弟節點
Entry<K,V> sib = leftOf(parentOf(x));
// 情況1）如果兄弟節點是紅色
if (colorOf(sib) == RED) {
// （1）將兄弟節點設為黑色
setColor(sib, BLACK);
// （2）將父節點設為紅色
setColor(parentOf(x), RED);
// （3）以父節點為支點進行右旋
rotateRight(parentOf(x));
// （4）重新設置x的兄弟節點
sib = leftOf(parentOf(x));
}
if (colorOf(rightOf(sib)) == BLACK &&
colorOf(leftOf(sib)) == BLACK) {
// 情況2）如果兄弟節點的兩個子節點都是黑色
// （1）將兄弟節點設置為紅色
setColor(sib, RED);
// （2）將x的父節點作為新的當前節點，進入下一次循環
x = parentOf(x);
} else {
if (colorOf(leftOf(sib)) == BLACK) {
// 情況3）如果兄弟節點的左子節點為黑色
// （1）將兄弟節點的右子節點設為黑色
setColor(rightOf(sib), BLACK);
// （2）將兄弟節點設為紅色
setColor(sib, RED);
// （3）以兄弟節點為支點進行左旋
rotateLeft(sib);
// （4）重新設置x的兄弟節點
sib = leftOf(parentOf(x));
}
// 情況4）
// （1）將兄弟節點的顏色設為父節點的顏色
setColor(sib, colorOf(parentOf(x)));
// （2）將父節點設為黑色
setColor(parentOf(x), BLACK);
// （3）將兄弟節點的左子節點設為黑色
setColor(leftOf(sib), BLACK);
// （4）以父節點為支點進行右旋
rotateRight(parentOf(x));
// （5）將root作為新的當前節點（退出循環）
x = root;
}
}
}
// 退出條件為多出來的黑色向上傳遞到瞭根節點或者紅節點
// 則將x設為黑色即可滿足紅黑樹規則
setColor(x, BLACK);
}
刪除元素舉例
假設我們有下面這樣一顆紅黑樹。
我們刪除6號元素，則從右子樹中找到瞭最小元素7，7又沒有子節點瞭，所以把7作為當前節點進行再平衡。
我們看到7是黑節點，且其兄弟為黑節點，且其兄弟的兩個子節點都是紅色，滿足情況4），平衡之後如下圖所示。
我們再刪除7號元素，則從右子樹中找到瞭最小元素8，8有子節點且為黑色，所以8的子節點9是替代節點，以9為當前節點進行再平衡。
我們發現9是紅節點，則直接把它塗成黑色即滿足瞭紅黑樹的特性，不需要再過多的平衡瞭。
這次我們來個狠的，把根節點刪除，從右子樹中找到瞭最小的元素5，5沒有子節點，所以把5作為當前節點進行再平衡。
我們看到5是黑節點，且其兄弟為紅色，符合情況1），平衡之後如下圖所示，然後進入情況2）。
對情況2）進行再平衡後如下圖所示。
然後進入下一次循環，發現不符合循環條件瞭，直接把x塗為黑色即可，退出這個方法之後會把舊x刪除掉（見deleteEntry()方法），最後的結果就是下面這樣。
二叉樹的遍歷
我們知道二叉查找樹的遍歷有前序遍歷、中序遍歷、後序遍歷。
（1）前序遍歷，先遍歷我，再遍歷我的左子節點，最後遍歷我的右子節點；
（2）中序遍歷，先遍歷我的左子節點，再遍歷我，最後遍歷我的右子節點；
（3）後序遍歷，先遍歷我的左子節點，再遍歷我的右子節點，最後遍歷我；
這裡的前中後都是以“我”的順序為準的，我在前就是前序遍歷，我在中就是中序遍歷，我在後就是後序遍歷。
下面讓我們看看經典的中序遍歷是怎麼實現的：
public class TreeMapTest {
public static void main(String[] args) {
// 構建一顆10個元素的樹
TreeNode<Integer> node = new TreeNode<>(1, null).insert(2)
.insert(6).insert(3).insert(5).insert(9)
.insert(7).insert(8).insert(4).insert(10);
// 中序遍歷，打印結果為1到10的順序
node.root().inOrderTraverse();
}
}
/**
* 樹節點，假設不存在重復元素
* @param <T>
*/
class TreeNode<T extends Comparable<T>> {
T value;
TreeNode<T> parent;
TreeNode<T> left, right;
public TreeNode(T value, TreeNode<T> parent) {
this.value = value;
this.parent = parent;
}
/**
* 獲取根節點
*/
TreeNode<T> root() {
TreeNode<T> cur = this;
while (cur.parent != null) {
cur = cur.parent;
}
return cur;
}
/**
* 中序遍歷
*/
void inOrderTraverse() {
if(this.left != null) this.left.inOrderTraverse();
System.out.println(this.value);
if(this.right != null) this.right.inOrderTraverse();
}
/**
* 經典的二叉樹插入元素的方法
*/
TreeNode<T> insert(T value) {
// 先找根元素
TreeNode<T> cur = root();
TreeNode<T> p;
int dir;
// 尋找元素應該插入的位置
do {
p = cur;
if ((dir=value.compareTo(p.value)) < 0) {
cur = cur.left;
} else {
cur = cur.right;
}
} while (cur != null);
// 把元素放到找到的位置
if (dir < 0) {
p.left = new TreeNode<>(value, p);
return p.left;
} else {
p.right = new TreeNode<>(value, p);
return p.right;
}
}
}
TreeMap的遍歷
從上面二叉樹的遍歷我們很明顯地看到，它是通過遞歸的方式實現的，但是遞歸會占用額外的空間，直接到線程棧整個釋放掉才會把方法中申請的變量銷毀掉，所以當元素特別多的時候是一件很危險的事。
（上面的例子中，沒有申請額外的空間，如果有聲明變量，則可以理解為直到方法完成才會銷毀變量）
那麼，有沒有什麼方法不用遞歸呢？
讓我們來看看java中的實現：
@Override
public void forEach(BiConsumer<? super K, ? super V> action) {
Objects.requireNonNull(action);
// 遍歷前的修改次數
int expectedModCount = modCount;
// 執行遍歷，先獲取第一個元素的位置，再循環遍歷後繼節點
for (Entry<K, V> e = getFirstEntry(); e != null; e = successor(e)) {
// 執行動作
action.accept(e.key, e.value);
// 如果發現修改次數變瞭，則拋出異常
if (expectedModCount != modCount) {
throw new ConcurrentModificationException();
}
}
}
是不是很簡單？！
（1）尋找第一個節點；
從根節點開始找最左邊的節點，即最小的元素。
final Entry<K,V> getFirstEntry() {
Entry<K,V> p = root;
// 從根節點開始找最左邊的節點，即最小的元素
if (p != null)
while (p.left != null)
p = p.left;
return p;
}
（2）循環遍歷後繼節點；
尋找後繼節點這個方法我們在刪除元素的時候也用到過，當時的場景是有右子樹，則從其右子樹中尋找最小的節點。
static <K,V> TreeMap.Entry<K,V> successor(Entry<K,V> t) {
if (t == null)
// 如果當前節點為空，返回空
return null;
else if (t.right != null) {
// 如果當前節點有右子樹，取右子樹中最小的節點
Entry<K,V> p = t.right;
while (p.left != null)
p = p.left;
return p;
} else {
// 如果當前節點沒有右子樹
// 如果當前節點是父節點的左子節點，直接返回父節點
// 如果當前節點是父節點的右子節點，一直往上找，直到找到一個祖先節點是其父節點的左子節點為止，返回這個祖先節點的父節點
Entry<K,V> p = t.parent;
Entry<K,V> ch = t;
while (p != null && ch == p.right) {
ch = p;
p = p.parent;
}
return p;
}
}
讓我們一起來分析下這種方式的時間復雜度吧。
首先，尋找第一個元素，因為紅黑樹是接近平衡的二叉樹，所以找最小的節點，相當於是從頂到底瞭，時間復雜度為O(log n)；
其次，尋找後繼節點，因為紅黑樹插入元素的時候會自動平衡，最壞的情況就是尋找右子樹中最小的節點，時間復雜度為O(log k)，k為右子樹元素個數；
最後，需要遍歷所有元素，時間復雜度為O(n)；
所以，總的時間復雜度為 O(log n) + O(n * log k) ≈ O(n)。
雖然遍歷紅黑樹的時間復雜度是O(n)，但是它實際是要比跳表要慢一點的，啥？跳表是啥？安心，後面會講到跳表的。
總結
到這裡紅黑樹就整個講完瞭，讓我們再回顧下紅黑樹的特性：
- 每個節點或者是黑色，或者是紅色。
- 根節點是黑色。
- 每個葉子節點（NIL）是黑色。（註意：這裡葉子節點，是指為空(NIL或NULL)的葉子節點！）
- 如果一個節點是紅色的，則它的子節點必須是黑色的。
- 從一個節點到該節點的子孫節點的所有路徑上包含相同數目的黑節點。
除瞭上述這些標準的紅黑樹的特性，你還能講出來哪些TreeMap的特性呢？
- TreeMap的存儲結構隻有一顆紅黑樹；
- TreeMap中的元素是有序的，按key的順序排列；
- TreeMap比HashMap要慢一些，因為HashMap前面還做瞭一層桶，尋找元素要快很多；
- TreeMap沒有擴容的概念；
- TreeMap的遍歷不是采用傳統的遞歸式遍歷；
- TreeMap可以按范圍查找元素，查找最近的元素；
總結
本篇文章就到這裡瞭，希望能給你帶來幫助，也希望您能夠多多關註WalkonNet的更多內容！