Adslv ·1. 前言
在 JDK1.8 之后，HashMap 的底層是由數組、鏈表、紅黑樹來實現的，當數組長度到 64 的時候，或者鏈表長度到 8 的時候，會調用 treeifyBin 轉換為紅黑樹實現。因為紅黑樹是小伙伴們面試的時候經常被考到的知識點，因此我們本節就幫大家理解紅黑樹的性質和操作。充分理解后具體的代碼實現就很簡單了，大家可以自己去實現，也可以直接參考 java.util.HashMap 中的源碼。
2. 紅黑樹的前世今生
紅黑樹是一種接近平衡的二叉搜索樹，它能夠保證任意一個節點左右子樹的高度差不會超過較低子樹的高度，也就是兩棵子樹的高度比值不會超過 2 倍。這樣我們可以使搜索的時間復雜度更接近 O (logN)。為了保證樹的平衡，我們需要在添加或刪除元素的時候不斷的調整樹的結構，使每個節點的左右子樹上的節點個數盡可能相等。
3. 紅黑樹的性質
紅黑樹的性質有五點，這里需要大家牢牢記?。?/p>
- 每個節點不是紅色就是黑色；
- 根節點永遠是黑色；
- 紅色節點的子節點必須是黑色；
- 任意一個節點到每個葉子節點的路徑上都包含相同數量的黑色節點；
- 每次添加新節點都默認為紅色。
4. 紅黑樹調整的方式
如果每次添加節點都設置為紅色，當父節點已經是紅色時，會違背上面的第 3 條性質，這時候我們需要按照一定的方法去調整樹，調整的方式有三種：改變節點顏色、左旋和右旋。
- 改變節點顏色如下圖，我們依次做了以下嘗試：
① 默認紅色：違反性質 3；
② 默認黑色：違反性質 4；
③ 默認紅色，將父節點和父節點的兄弟節點改為黑色，滿足全部 5 條性質。
- 左旋：拎起左旋節點的右子節點，使左旋節點向左下沉，成為右子節點的左子節點，右子節點上升成為其父節點。
- 右旋：拎起右旋節點的左子節點，使右旋節點向右下沉，成為左子節點的右子節點，左子節點上升成為其父節點。
5. 紅黑樹的插入操作
插入元素會導致原本平衡的紅黑樹失去平衡，還會導致紅黑樹五大特性的不滿足。因此插入后我們需要做調整，使其重新成為一個紅黑樹。
5.1 把大象放冰箱的第一步是把冰箱門打開
把元素插進紅黑樹的第一步是找到要插入的位置。尋找位置的方法其實也比較簡單：
① 如果是空樹，直接插入到跟節點；
② 如果與當前節點的 key 值相等，則更新當前節點的 value 值；
③ 如果比當前節點的 key 值大，則繼續尋找當前節點的右子節點；
④ 如果比當前節點的 key 值小，則繼續尋找當前節點的左子節點；
⑤ 如果當前節點為 null（或 nil 節點），則插入在當前節點的父節點下。
5.2 插入后重新調整至平衡狀態
前面我們說了調整的方式，那么我們在什么情況下使用什么方式調整呢？
我們可以看 JDK1.8 的 HashMap 中對紅黑樹的調整源碼，來了解在什么情況下使用什么樣的調整方式來重新使樹恢復平衡。情況略顯復雜，我把說明以注釋的形式標在源碼上，大家可以根據 if 條件來梳理邏輯線。
static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root, TreeNode<K,V> x) {
x.red = true;
for (TreeNode<K,V> xp, xpp, xppl, xppr;;) {
//false條件：當前節點存在父節點
if ((xp = x.parent) == null) {
//父節點為空，當前節點是根節點，直接設置根節點為黑色后返回
x.red = false;
return x;
}
//false條件：且父節點是紅色，且存在爺爺節點
else if (!xp.red || (xpp = xp.parent) == null)
return root;
if (xp == (xppl = xpp.left)) {
//false條件：且叔叔節點為空，或者是黑色；
if ((xppr = xpp.right) != null && xppr.red) {
xppr.red = false;
xp.red = false;
xpp.red = true;
x = xpp;
}
else {
//true條件：當前節點是其父節點的右子節點；
if (x == xp.right) {
// 左旋父節點
root = rotateLeft(root, x = xp);
// 爺爺節點不存在則結束，存在則將指針指向父節點
xpp = (xp = x.parent) == null ? null : xp.parent;
}
// true條件：父節點不為空
if (xp != null) {
// 父節點變為黑色
xp.red = false;
// true條件：祖父節點不為空
if (xpp != null) {
// 祖父節點變為紅色
xpp.red = true;
// 右旋祖父節點
root = rotateRight(root, xpp);
}
}
}
}
else {
//false條件：且叔叔節點為空，或者是黑色；
if (xppl != null && xppl.red) {
// 當前節點的父節點以及左叔父節點都是紅色 則顏色變為黑色
xppl.red = false;
xp.red = false;
// 黑節點的父節點必須紅色
xpp.red = true;
x = xpp;
}
else {
//true條件：當前節點是其父節點的左子節點；
if (x == xp.left) {
// 右旋父節點
root = rotateRight(root, x = xp);
// 指針指向父節點
xpp = (xp = x.parent) == null ? null : xp.parent;
}
// true條件：父節點不為空
if (xp != null) {
// 父節點變為黑色
xp.red = false;
// true條件：祖父節點不為空
if (xpp != null) {
// 祖父節點變為紅色
xpp.red = true;
// 右旋祖父節點
root = rotateLeft(root, xpp);
}
}
}
}
}
}
6. 紅黑樹的刪除操作
刪除操作可能觸發的情況分為有子節點和無子節點，沒有子節點的情況非常簡單，直接刪除后執行自平衡即可。有子節點的時候我們要先找到替換節點，如果只有一個子節點，這個節點就是替換節點；如果有兩個子節點，要找到左子樹的最大節點或右子樹的最小節點作為替換節點。感興趣的小伙伴可以通過源碼中的 removeTreeNode 方法梳理一下，這里我們不做展開了。
7. 小結
本節我們學習了重要的樹形結構——紅黑樹，我們要牢記紅黑樹五大特性，結合動圖了解變色、左旋和右旋的思路和方法，再去了解紅黑樹插入和刪除操作的再平衡過程。學習紅黑樹一定要先理解再動手寫代碼，依據紅黑樹的五大特性，在插入和刪除操作中來調整結構使樹盡量保持平衡，來確保對整個數據結構的插入、刪除和查找效率。
在學習過程中，我們也可以更多的借助 JDK 源碼來幫助我們梳理思路，從而幫助我們更快速、清晰、準確的理解紅黑樹。
2025 imooc.com All Rights Reserved |