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