日韩无码专区无码一级三级片|91人人爱网站中日韩无码电影|厨房大战丰满熟妇|AV高清无码在线免费观看|另类AV日韩少妇熟女|中文日本大黄一级黄色片|色情在线视频免费|亚洲成人特黄a片|黄片wwwav色图欧美|欧亚乱色一区二区三区

【稿件】

寫在前面

本文是之前發(fā)表的文章《逐行解讀HashMap源碼》的下一篇，也是最后一篇。在《逐行解讀HashMap源碼》文章中，筆者主要分析了 HashMap 類的成員變量與成員方法，未涉及對 HashMap 中紅黑樹相關(guān)內(nèi)容的分析。于是，筆者經(jīng)過一段的時間的編寫與打磨，寫出了本文。本文主要內(nèi)容包括對上一篇文章的些許補充以及對紅黑樹源碼的詳細解讀。

如果讀者沒有閱讀過上一篇內(nèi)容，可以微信搜索公眾號“代碼藝術(shù)”搜索并閱讀文章。

1. 紅黑樹概述

從本章節(jié)開始，筆者將對 HashMap 內(nèi)部的 TreeNode 內(nèi)部類源碼開始分析，這部分的內(nèi)容也就是我們所說的紅黑樹。

紅黑樹是建立在二叉查找樹的基礎(chǔ)之上的，二叉查找樹又是建立在二叉樹的基礎(chǔ)之上。所以，我們需要從二叉樹開始學(xué)習紅黑樹的發(fā)展脈絡(luò)。

2. 二叉樹

二叉樹(英語：Binary tree)是每個節(jié)點最多只有兩個分支(即不存在分支度大于2的節(jié)點)的樹結(jié)構(gòu)。通常分支被稱作“左子樹”或“右子樹”。二叉樹的分支具有左右次序，不能隨意顛倒。

3. 二叉查找樹

二叉查找樹(英語：Binary Search Tree)，也稱為二叉搜索樹、有序二叉樹(ordered binary tree)或排序二叉樹(sorted binary tree)，是指一棵空樹或者具有下列性質(zhì)的二叉樹：

1. 若任意節(jié)點的左子樹不空，則左子樹上所有節(jié)點的值均小于它的根節(jié)點的值;
2. 若任意節(jié)點的右子樹不空，則右子樹上所有節(jié)點的值均大于或等于它的根節(jié)點的值;
3. 任意節(jié)點的左、右子樹也分別為二叉查找樹;

一顆二叉查找樹如下圖所示：

但是，當我們順序插入一系列節(jié)點后，二叉查找樹就退化為線性表，如下圖所示：

雖然二叉查找樹退化為線性表之后，最壞效率降為 O(n)。但依舊有很多改進版的二叉查找樹可以使樹高為O(log n)，從而將最壞效率降至O(log n)，如AVL樹、紅黑樹等。

4. AVL樹

AVL 樹是最早被發(fā)明的自平衡二叉查找樹。在AVL樹中，任一節(jié)點對應(yīng)的兩棵子樹的最大高度差為 1 ，因此它也被稱為高度平衡樹。查找、插入和刪除在平均和最壞情況下的時間復(fù)雜度都是 O(logn)。增加和刪除元素的操作則可能需要借由一次或多次樹旋轉(zhuǎn)，以實現(xiàn)樹的重新平衡。

在 AVL 樹中，節(jié)點的**平衡因子**是它的左子樹的高度減去它的右子樹的高度(有時相反)。帶有平衡因子 1、0 或 -1 的節(jié)點被認為是平衡的。帶有平衡因子 -2 或 2 的節(jié)點被認為是不平衡的，并需要重新平衡這個樹。平衡因子可以直接存儲在每個節(jié)點中，或從可能存儲在節(jié)點中的子樹高度計算出來。

AVL 樹自平衡的方式是做一次或多次所謂的"AVL旋轉(zhuǎn)"。

5. 紅黑樹

紅黑樹(英語：Red–black tree)也是一種自平衡二叉查找樹。紅黑樹在二叉查找樹的基礎(chǔ)之上，對每個節(jié)點都增加了顏色屬性，分為紅色或黑色。在二叉查找樹強制的一般要求以外，對于任何有效的紅黑樹增加了如下 5 條額外要求：

1. 節(jié)點是紅色或黑色。
2. 根節(jié)點是黑色。
3. 所有葉子都是黑色(葉子是NIL節(jié)點)。
4. 每個紅色節(jié)點必須有兩個黑色的子節(jié)點。(從每個葉子到根的所有路徑上不能有兩個連續(xù)的紅色節(jié)點。)
5. 從任一節(jié)點到其每個葉子的所有簡單路徑都包含相同數(shù)目的黑色節(jié)點。

下面是一個具體的紅黑樹的圖例：

紅黑樹的這些特性，保證了紅黑樹**從根到葉子的最長的可能路徑不多于最短的可能路徑的兩倍長**，造成的結(jié)果是紅黑樹大致上是平衡的。如上圖所示，"nil葉子"或"空(null)葉子"不包含數(shù)據(jù)而只充當樹在此結(jié)束的指示。

對于紅黑樹的讀與寫，因為每一個紅黑樹都是一個(特殊的)二叉查找樹，因此紅黑樹上的只讀操作與普通二叉查找樹上的只讀操作相同。然而，在紅黑樹上進行插入操作和刪除操作會導(dǎo)致不再符合紅黑樹的性質(zhì)。恢復(fù)紅黑樹的性質(zhì)需要少量 O(log n) 的顏色變更(實際是非?？焖俚?和不超過三次的樹旋轉(zhuǎn)(對于插入操作是兩次)。雖然插入和刪除很復(fù)雜，但操作時間仍可以保持為 O(log n) 次。

本章節(jié)開始結(jié)合 HashMap 源碼講解紅黑樹的插入、紅黑樹的刪除、紅黑樹的自平衡、左旋、右旋等內(nèi)容。

6. 鏈表轉(zhuǎn)為紅黑樹的過程

HashMap 的桶類型除了 Node (鏈表)外，還有 TreeNode (樹)。

TreeNode 類包含成員方法 `treeify()` ，該方法的作用是形成以當前 TreeNode 對象為根節(jié)點的紅黑樹。

樹化過程不外乎是循環(huán)遍歷鏈表，構(gòu)造一顆二叉查找樹，最后使用紅黑樹的平衡方法進行自平衡。

該方法源碼如下：

 
 
 
 

  
  
  
  
final void treeify(Node[] tab) { 
  
  
  
  
TreeNode root = null; 
  
  
  
  
// 步驟①：循環(huán)遍歷當前TreeNode鏈表 
  
  
  
  
for (TreeNode x = this, next; x != null; x = next) { 
  
  
  
  
next = (TreeNode)x.next; 
  
  
  
  
x.left = x.right = null; 
  
  
  
  
// 步驟②：如果還未設(shè)置根節(jié)點.. 
  
  
  
  
if (root == null) { 
  
  
  
  
x.parent = null; 
  
  
  
  
x.red = false; 
  
  
  
  
root = x; 
  
  
  
  
} 
  
  
  
  
// 步驟③：如果已設(shè)置根節(jié)點.. 
  
  
  
  
else { 
  
  
  
  
K k = x.key; 
  
  
  
  
int h = x.hash; 
  
  
  
  
Class kc = null; 
  
  
  
  
// 步驟④：從根節(jié)點開始遍歷，插入新節(jié)點 
  
  
  
  
for (TreeNode p = root;;) { 
  
  
  
  
int dir, ph; 
  
  
  
  
K pk = p.key; 
  
  
  
  
// 步驟⑤：比較當前節(jié)點的hash值與新節(jié)點的hash值 
  
  
  
  
// 若是新節(jié)點hash值較小 
  
  
  
  
if ((ph = p.hash) > h) 
  
  
  
  
dir = -1; 
  
  
  
  
// 若是新節(jié)點的hash值較大 
  
  
  
  
else if (ph < h) 
  
  
  
  
dir = 1; 
  
  
  
  
// 若是新節(jié)點與當前節(jié)點的hash值相等 
  
  
  
  
else if ( 
  
  
  
  
// 如果新節(jié)點的key沒有實現(xiàn)Comparable接口.. 
  
  
  
  
(kc == null && (kc = comparableClassFor(k)) == null) 
  
  
  
  
// 或者實現(xiàn)了Comparable接口但是k.compareTo(pk)結(jié)果為0 
  
  
  
  
||(dir = compareComparables(kc, k, pk)) == 0) 
  
  
  
  
// 則調(diào)用tieBreakOrder繼續(xù)比較大小 
  
  
  
  
dir = tieBreakOrder(k, pk); 
  
  
  
  
TreeNode xp = p; 
  
  
  
  
// 步驟⑥：如果新節(jié)點經(jīng)比較后小于等于當前節(jié)點且當前節(jié)點的左子節(jié)點為null，則插入新節(jié)點，反之亦然 
  
  
  
  
if ((p = (dir <= 0) ? p.left : p.right) == null) { 
  
  
  
  
x.parent = xp; 
  
  
  
  
if (dir <= 0) 
  
  
  
  
xp.left = x; 
  
  
  
  
else 
  
  
  
  
xp.right = x; 
  
  
  
  
// 步驟⑦：平衡紅黑樹 
  
  
  
  
root = balanceInsertion(root, x); 
  
  
  
  
break; 
  
  
  
  
} 
  
  
  
  
} 
  
  
  
  
} 
  
  
  
  
} 
  
  
  
  
// 步驟⑧：確保給定的根節(jié)點是所在桶的第一個節(jié)點 
  
  
  
  
moveRootToFront(tab, root); 
  
  
  
  
} 
 
 
 
 

7. 紅黑樹的左旋和右旋

紅黑樹的左旋和右旋其實很簡單，所謂的左旋是把要平衡的節(jié)點向左下旋轉(zhuǎn)成一個葉子節(jié)點。

如下圖所示：

所謂的右旋是把要平衡的節(jié)點向右下旋轉(zhuǎn)成一個葉子節(jié)點。

如下圖所示：

在 HashMap 的源碼中，左旋的實現(xiàn)代碼如下：

 
 
 
 

  
  
  
  
static TreeNode rotateLeft(TreeNode root, 
  
  
  
  
TreeNode p) { 
  
  
  
  
// p: 當前節(jié)點 
  
  
  
  
// r: 當前節(jié)點的右兒子 
  
  
  
  
// rl: 當前節(jié)點的右兒子的左兒子 
  
  
  
  
TreeNode r, pp, rl; 
  
  
  
  
// 如果當前節(jié)點和當前節(jié)點的右兒子不為空，就左旋 
  
  
  
  
if (p != null && (r = p.right) != null) { 
  
  
  
  
// 步驟①：當前節(jié)點的右兒子的左兒子成為當前節(jié)點的右兒子 
  
  
  
  
if ((rl = p.right = r.left) != null) 
  
  
  
  
rl.parent = p; 
  
  
  
  
// 步驟②：當前節(jié)點的右兒子成為當前節(jié)點的父節(jié)點 
  
  
  
  
if ((pp = r.parent = p.parent) == null) 
  
  
  
  
// 如果當前節(jié)點是根節(jié)點，那么r的顏色必須是黑色 
  
  
  
  
(root = r).red = false; 
  
  
  
  
else if (pp.left == p) 
  
  
  
  
pp.left = r; 
  
  
  
  
else 
  
  
  
  
pp.right = r; 
  
  
  
  
r.left = p; 
  
  
  
  
p.parent = r; 
  
  
  
  
} 
  
  
  
  
return root; 
  
  
  
  
} 
 
 
 
 

右旋的實現(xiàn)代碼如下：

 
 
 
 

  
  
  
  
static TreeNode rotateRight(TreeNode root, 
  
  
  
  
TreeNode p) { 
  
  
  
  
// p: 當前節(jié)點 
  
  
  
  
// l: 當前節(jié)點的左兒子 
  
  
  
  
// lr: 當前節(jié)點的左兒子的右兒子 
  
  
  
  
TreeNode l, pp, lr; 
  
  
  
  
// 如果當前節(jié)點和當前節(jié)點的左兒子不為空，就右旋 
  
  
  
  
if (p != null && (l = p.left) != null) { 
  
  
  
  
// 步驟①：當前節(jié)點的左兒子的右兒子成為當前節(jié)點的左兒子 
  
  
  
  
if ((lr = p.left = l.right) != null) 
  
  
  
  
lr.parent = p; 
  
  
  
  
// 步驟②：當前節(jié)點的左兒子成為當前節(jié)點的父節(jié)點 
  
  
  
  
if ((pp = l.parent = p.parent) == null) 
  
  
  
  
// 如果當前節(jié)點是根節(jié)點，那么r的顏色必須是黑色 
  
  
  
  
(root = l).red = false; 
  
  
  
  
else if (pp.right == p) 
  
  
  
  
pp.right = l; 
  
  
  
  
else 
  
  
  
  
pp.left = l; 
  
  
  
  
l.right = p; 
  
  
  
  
p.parent = l; 
  
  
  
  
} 
  
  
  
  
return root; 
  
  
  
  
} 
 
 
 
 

 8. 紅黑樹的插入

紅黑樹是一棵特殊的二叉查找樹，如同二叉查找樹的插入一樣，紅黑樹的插入，也需要判斷插入節(jié)點與當前節(jié)點的大小。如果插入節(jié)點大于或等于當前節(jié)點，則插入當前節(jié)點的右子樹;否則，插入到左子樹。循環(huán)此過程，直到找到為空的葉子節(jié)點放入即可。

 
 
 
 

  
  
  
  
/** 
  
  
  
  
* Tree version of putVal. 
  
  
  
  
*/ 
  
  
  
  
final TreeNode putTreeVal(HashMap map, Node[] tab, 
  
  
  
  
int h, K k, V v) { 
  
  
  
  
Class kc = null; 
  
  
  
  
boolean searched = false; 
  
  
  
  
// root: 樹根節(jié)點 
  
  
  
  
TreeNode root = (parent != null) ? root() : this; 
  
  
  
  
for (TreeNode p = root;;) { 
  
  
  
  
// p: 當前節(jié)點 
  
  
  
  
// dir: 標識新節(jié)點應(yīng)該插入到當前節(jié)點的左子樹還是右子樹 
  
  
  
  
// ph: 當前節(jié)點的hash值 
  
  
  
  
// pk: 當前節(jié)點的key 
  
  
  
  
int dir, ph; K pk; 
  
  
  
  
// 步驟①：判斷新節(jié)點應(yīng)該插入到當前節(jié)點的左子樹還是右子樹 
  
  
  
  
if ((ph = p.hash) > h) 
  
  
  
  
dir = -1; 
  
  
  
  
else if (ph < h) 
  
  
  
  
dir = 1; 
  
  
  
  
else if ((pk = p.key) == k || (k != null && k.equals(pk))) 
  
  
  
  
return p; 
  
  
  
  
else if ((kc == null && 
  
  
  
  
(kc = comparableClassFor(k)) == null) || 
  
  
  
  
(dir = compareComparables(kc, k, pk)) == 0) { 
  
  
  
  
if (!searched) { 
  
  
  
  
TreeNode q, ch; 
  
  
  
  
searched = true; 
  
  
  
  
if (((ch = p.left) != null && 
  
  
  
  
(q = ch.find(h, k, kc)) != null) || 
  
  
  
  
((ch = p.right) != null && 
  
  
  
  
(q = ch.find(h, k, kc)) != null)) 
  
  
  
  
return q; 
  
  
  
  
} 
  
  
  
  
dir = tieBreakOrder(k, pk); 
  
  
  
  
} 
  
  
  
  
TreeNode xp = p; 
  
  
  
  
// 步驟②：終于從上向下遍歷到了空的葉子節(jié)點，插入新節(jié)點 
  
  
  
  
if ((p = (dir <= 0) ? p.left : p.right) == null) { 
  
  
  
  
// 1.父節(jié)點指向新節(jié)點 
  
  
  
  
Node xpn = xp.next; 
  
  
  
  
TreeNode x = map.newTreeNode(h, k, v, xpn); 
  
  
  
  
// 新節(jié)點位置在左子樹還是右子樹 
  
  
  
  
if (dir <= 0) 
  
  
  
  
xp.left = x; 
  
  
  
  
else 
  
  
  
  
xp.right = x; 
  
  
  
  
xp.next = x; 
  
  
  
  
// 2.新節(jié)點指向父節(jié)點 
  
  
  
  
x.parent = x.prev = xp; 
  
  
  
  
if (xpn != null) 
  
  
  
  
// 如果有兄弟節(jié)點，兄弟節(jié)點的上一個節(jié)點指向新節(jié)點 
  
  
  
  
((TreeNode)xpn).prev = x; 
  
  
  
  
// 最后平衡紅黑樹，并保證根節(jié)點在哈希桶的頭部 
  
  
  
  
moveRootToFront(tab, balanceInsertion(root, x)); 
  
  
  
  
return null; 
  
  
  
  
} 
  
  
  
  
} 
  
  
  
  
} 
 
 
 
 

紅黑樹的插入與二叉查找樹的不同之處，在于最后的平衡部分。

插入節(jié)點之后的紅黑樹平衡方法如下：

 
 
 
 

  
  
  
  
/** 
  
  
  
  
* 平衡紅黑樹-當新增后 
  
  
  
  
* x: 影響平衡的點(俗稱：當前節(jié)點) 
  
  
  
  
*/ 
  
  
  
  
static TreeNode balanceInsertion(TreeNode root, 
  
  
  
  
TreeNode x) { 
  
  
  
  
// 新增節(jié)點x默認是紅色 
  
  
  
  
x.red = true; 
  
  
  
  
// xp父節(jié)點 xpp祖父節(jié)點 xppl祖父左節(jié)點 xppr 祖父右節(jié)點(p: parent, l: left, r: right) 
  
  
  
  
for (TreeNode xp, xpp, xppl, xppr;;) { 
  
  
  
  
if ((xp = x.parent) == null) { 
  
  
  
  
// 步驟①：如果插入的是根節(jié)點，根據(jù)紅黑樹性質(zhì)之根節(jié)點是黑色，直接涂黑即可 
  
  
  
  
x.red = false; 
  
  
  
  
return x; 
  
  
  
  
} 
  
  
  
  
// 步驟②：插入節(jié)點的父節(jié)點是黑色或者父節(jié)點是根節(jié)點，紅黑樹沒有被破壞，不需要調(diào)整 
  
  
  
  
else if (!xp.red || (xpp = xp.parent) == null) 
  
  
  
  
return root; 
  
  
  
  
// 父節(jié)點是祖父節(jié)點的左子節(jié)點 
  
  
  
  
if (xp == (xppl = xpp.left)) { 
  
  
  
  
// 步驟③：當前節(jié)點的父節(jié)點是紅色，且叔叔節(jié)點也是紅色 
  
  
  
  
if ((xppr = xpp.right) != null && xppr.red) { 
  
  
  
  
// 1.叔叔節(jié)點設(shè)置為黑色 
  
  
  
  
xppr.red = false; 
  
  
  
  
// 2.父節(jié)點設(shè)置為黑色 
  
  
  
  
xp.red = false; 
  
  
  
  
// 3.祖父節(jié)點設(shè)置為紅色 
  
  
  
  
xpp.red = true; 
  
  
  
  
// 4.將當前節(jié)點指向祖父節(jié)點，從新的當前節(jié)點重新開始算法 
  
  
  
  
x = xpp; 
  
  
  
  
} 
  
  
  
  
else { 
  
  
  
  
// 步驟④：當前節(jié)點的父節(jié)點是紅色，且叔叔節(jié)點是黑色，當前節(jié)點是其父右子節(jié)點 
  
  
  
  
if (x == xp.right) { 
  
  
  
  
// 當前節(jié)點的父節(jié)點作為新的當前節(jié)點，以新當節(jié)點為支點左旋 
  
  
  
  
root = rotateLeft(root, x = xp); 
  
  
  
  
// 重新賦值 
  
  
  
  
xpp = (xp = x.parent) == null ? null : xp.parent; 
  
  
  
  
} 
  
  
  
  
if (xp != null) { 
  
  
  
  
// 父節(jié)點設(shè)置為黑色 
  
  
  
  
xp.red = false; 
  
  
  
  
if (xpp != null) { 
  
  
  
  
// 祖父節(jié)點設(shè)置為紅色 
  
  
  
  
xpp.red = true; 
  
  
  
  
// 以祖父節(jié)點為支點右旋 
  
  
  
  
root = rotateRight(root, xpp); 
  
  
  
  
} 
  
  
  
  
} 
  
  
  
  
} 
  
  
  
  
} 
  
  
  
  
// 父節(jié)點是祖父節(jié)點的右子節(jié)點 
  
  
  
  
else { 
  
  
  
  
// 步驟③：當前節(jié)點的父節(jié)點是紅色，且叔叔節(jié)點也是紅色 
  
  
  
  
if (xppl != null && xppl.red) { 
  
  
  
  
// 1.叔叔節(jié)點設(shè)置為黑色 
  
  
  
  
xppl.red = false; 
  
  
  
  
// 2.父節(jié)點設(shè)置為黑色 
  
  
  
  
xp.red = false; 
  
  
  
  
// 3.祖父節(jié)點設(shè)置為紅色 
  
  
  
  
xpp.red = true; 
  
  
  
  
// 4.將當前節(jié)點指向祖父節(jié)點，從新的當前節(jié)點重新開始算法 
  
  
  
  
x = xpp; 
  
  
  
  
} 
  
  
  
  
else { 
  
  
  
  
// 步驟④：當前節(jié)點的父節(jié)點是紅色，且叔叔節(jié)點是黑色，當前節(jié)點是其父左子節(jié)點 
  
  
  
  
if (x == xp.left) { 
  
  
  
  
// 當前節(jié)點的父節(jié)點作為新的當前節(jié)點，以新當節(jié)點為支點右旋 
  
  
  
  
root = rotateRight(root, x = xp); 
  
  
  
  
// 重新賦值 
  
  
  
  
xpp = (xp = x.parent) == null ? null : xp.parent; 
  
  
  
  
} 
  
  
  
  
if (xp != null) { 
  
  
  
  
// 父節(jié)點設(shè)置為黑色 
  
  
  
  
xp.red = false; 
  
  
  
  
if (xpp != null) { 
  
  
  
  
// 祖父節(jié)點設(shè)置為紅色 
  
  
  
  
xpp.red = true; 
  
  
  
  
// 以祖父節(jié)點為支點左旋 
  
  
  
  
root = rotateLeft(root, xpp); 
  
  
  
  
} 
  
  
  
  
} 
  
  
  
  
} 
  
  
  
  
} 
  
  
  
  
} 
  
  
  
  
} 
 
 
 
 

10. 紅黑樹的刪除

紅黑樹的刪除相比插入更加復(fù)雜，需要先從鏈表結(jié)構(gòu)上進行刪除，也就是處理當前節(jié)點的 next 指針與 prev 指針。如果當前樹的節(jié)點太少，那么就將樹退化為鏈表。然后，查找被刪除節(jié)點的后繼節(jié)點。所謂后繼節(jié)點，就是當刪除節(jié)點p后，如果p有子節(jié)點，p的子節(jié)點上移繼承其位置。當找到后繼節(jié)點，立即刪除節(jié)點，如果被刪除節(jié)點是紅色，那么不需要平衡，否則平衡紅黑樹。

紅黑樹的刪除方法代碼如下：

 
 
 
 

  
  
  
  
final void removeTreeNode(HashMap map, Node[] tab, 
  
  
  
  
boolean movable) { 
  
  
  
  
int n; 
  
  
  
  
if (tab == null || (n = tab.length) == 0)
  
  
  
  

  
  
  
  
// 不處理空的哈希表
  
  
  
  

  
  
  
  
return;
  
  
  
  

  
  
  
  
// 第 1 部分: 處理鏈表結(jié)構(gòu) 
  
  
  
  
// 通過被刪除的key的哈希值查找桶(紅黑樹)的位置
  
  
  
  

  
  
  
  
int index = (n - 1) & hash; 
  
  
  
  
// first、root: 紅黑樹的根節(jié)點 
  
  
  
  
TreeNode first = (TreeNode)tab[index], root = first, rl;
  
  
  
  

  
  
  
  
// succ: 當前節(jié)點(被刪除節(jié)點)的下一個節(jié)點
  
  
  
  

  
  
  
  
// pred: 當前節(jié)點(被刪除節(jié)點)的上一個節(jié)點 
  
  
  
  
TreeNode succ = (TreeNode)next, pred = prev;
  
  
  
  

  
  
  
  
// 步驟①：從鏈表結(jié)構(gòu)上刪除當前節(jié)點(處理上一個節(jié)點的 next 指針與下一個節(jié)點的 prev 指針)
  
  
  
  

  
  
  
  
if (pred == null) 
  
  
  
  
// 上一個節(jié)點為空，說明是要刪除的是根節(jié)點，將紅黑樹的根節(jié)點索引改為當前節(jié)點的下一個節(jié)點 
  
  
  
  
tab[index] = first = succ; 
  
  
  
  
else 
  
  
  
  
// 刪除的不是根節(jié)點，就把當前節(jié)點的上一個節(jié)點的next指向當前節(jié)點的下一個節(jié)點
  
  
  
  
pred.next = succ;
  
  
  
  

  
  
  
  
if (succ != null) 
  
  
  
  
// 當前節(jié)點的下一個節(jié)點不為空，就把下一個節(jié)點的prev指向當前節(jié)點的上一個節(jié)點 
  
  
  
  
succ.prev = pred;
  
  
  
  

  
  
  
  
// 步驟②：刪除節(jié)點完畢后，紅黑樹為空，直接返回
  
  
  
  

  
  
  
  
if (first == null) 
  
  
  
  
return;
  
  
  
  

  
  
  
  
// 步驟③：更新root指針，并判斷是否需要將樹轉(zhuǎn)為鏈表結(jié)構(gòu)
  
  
  
  

  
  
  
  
if (root.parent != null) 
  
  
  
  
root = root.root(); 
  
  
  
  
if (root == null || root.right == null || 
  
  
  
  
(rl = root.left) == null || rl.left == null) { 
  
  
  
  
tab[index] = first.untreeify(map); // too small 
  
  
  
  
return;
  
  
  
  

  
  
  
  
}
  
  
  
  

  
  
  
  
// 第 2 部分: 處理樹結(jié)構(gòu) 
  
  
  
  
// p: 被刪除的節(jié)點; replacement: 后繼節(jié)點(刪除節(jié)點p后，如果p有子節(jié)點，p的子節(jié)點上移繼承其位置) 
  
  
  
  
// pl: 被刪除節(jié)點的左兒子; pr: 被刪除節(jié)點的右兒子
  
  
  
  

  
  
  
  
TreeNode p = this, pl = left, pr = right, replacement;
  
  
  
  

  
  
  
  
// 步驟①：查找被刪除節(jié)點的后繼節(jié)點，分以下幾種情況 
  
  
  
  
// ⑴ 被刪除節(jié)點有左子樹和右子樹
  
  
  
  

  
  
  
  
if (pl != null && pr != null) { 
  
  
  
  
TreeNode s = pr, sl;
  
  
  
  

  
  
  
  
// 1.查找右子樹最左葉子節(jié)點s與待刪除節(jié)點p進行位置互換 
  
  
  
  
while ((sl = s.left) != null) // find successor 
  
  
  
  
s = sl; 
  
  
  
  
// 2.交換最左葉子節(jié)點和待刪除節(jié)點的顏色 
  
  
  
  
boolean c = s.red; s.red = p.red; p.red = c; // swap colors 
  
  
  
  
// sr：最左葉子節(jié)點的右兒子 
  
  
  
  
TreeNode sr = s.right; 
  
  
  
  
// pp：被刪除節(jié)點的父節(jié)點 
  
  
  
  
TreeNode pp = p.parent;
  
  
  
  
// 3.交換被刪除節(jié)點p和最左葉子節(jié)點s的位置 
  
  
  
  
// 判斷最左葉子節(jié)點是否是被刪除節(jié)點的右兒子(即右子樹是否只有一個節(jié)點)分別處理節(jié)點s.right和p.parent的引用 
  
  
  
  
if (s == pr) { // p was s's direct parent 
  
  
  
  
p.parent = s; 
  
  
  
  
s.right = p; 
  
  
  
  
} 
  
  
  
  
else { 
  
  
  
  
TreeNode sp = s.parent; 
  
  
  
  
if ((p.parent = sp) != null) { 
  
  
  
  
if (s == sp.left) 
  
  
  
  
sp.left = p; 
  
  
  
  
else 
  
  
  
  
sp.right = p; 
  
  
  
  
} 
  
  
  
  
if ((s.right = pr) != null) 
  
  
  
  
pr.parent = s; 
  
  
  
  
} 
  
  
  
  
p.left = null;
  
  
  
  
// 處理p.right和sr.parent的引用 
  
  
  
  
if ((p.right = sr) != null) 
  
  
  
  
sr.parent = p; 
  
  
  
  
// 處理s.left和pl.parent的引用 
  
  
  
  
if ((s.left = pl) != null) 
  
  
  
  
pl.parent = s; 
  
  
  
  
// 處理s.parent的引用和pp.left或pp.right 
  
  
  
  
if ((s.parent = pp) == null) 
  
  
  
  
root = s; 
  
  
  
  
else if (p == pp.left) 
  
  
  
  
pp.left = s; 
  
  
  
  
else 
  
  
  
  
pp.right = s;
  
  
  
  

  
  
  
  
// 4.交換最左葉子節(jié)點和被刪除節(jié)點的位置完成 
  
  
  
  
// 此時被刪除節(jié)點p在原最左葉子節(jié)點的位置，現(xiàn)在被刪除節(jié)點p沒有左子樹，如果有右子樹，那么右兒子sr就是后繼節(jié)點，否則后繼節(jié)點指向自身
  
  
  
  

  
  
  
  
if (sr != null) 
  
  
  
  
replacement = sr; 
  
  
  
  
else 
  
  
  
  
replacement = p; 
  
  
  
  
} 
  
  
  
  
// ⑵ 被刪除節(jié)點只有左子樹，后繼節(jié)點就是左兒子
  
  
  
  

  
  
  
  
else if (pl != null) 
  
  
  
  
replacement = pl; 
  
  
  
  
// ⑶ 被刪除節(jié)點只有右子樹，后繼節(jié)點就是右兒子 
  
  
  
  
else if (pr != null) 
  
  
  
  
replacement = pr; 
  
  
  
  
// ⑷ 被刪除節(jié)點沒有子樹，那么后繼節(jié)點就指向自身 
  
  
  
  
else 
  
  
  
  
replacement = p; 
  
  
  
  
// 步驟②：已經(jīng)找到刪除節(jié)點后的后繼節(jié)點，這一步將從樹中徹底刪除節(jié)點p。
  
  
  
  

  
  
  
  
if (replacement != p) { 
  
  
  
  
// 1.修改替代節(jié)點的父節(jié)點引用 
  
  
  
  
TreeNode pp = replacement.parent = p.parent;
  
  
  
  

  
  
  
  
// 2.將被刪除節(jié)點的父節(jié)點對其的引用進行修改 
  
  
  
  
if (pp == null) 
  
  
  
  
root = replacement; 
  
  
  
  
else if (p == pp.left) 
  
  
  
  
pp.left = replacement; 
  
  
  
  
else 
  
  
  
  
pp.right = replacement; 
  
  
  
  
// 3.徹底刪除節(jié)點p 
  
  
  
  
p.left = p.right = p.parent = null; 
  
  
  
  
} 
  
  
  
  
// 步驟③：刪除節(jié)點完成，刪除的是紅色節(jié)點，不需要平衡;否則，平衡 
  
  
  
  
TreeNode r = p.red ? root : balanceDeletion(root, replacement); 
  
  
  
  
// 步驟④：若沒有后繼節(jié)點，直接刪除節(jié)點p 
  
  
  
  
if (replacement == p) { // detach 
  
  
  
  
TreeNode pp = p.parent; 
  
  
  
  
p.parent = null; 
  
  
  
  
if (pp != null) {
  
  
  
  

  
  
  
  
if (p == pp.left) 
  
  
  
  
pp.left = null; 
  
  
  
  
else if (p == pp.right) 
  
  
  
  
pp.right = null; 
  
  
  
  
} 
  
  
  
  
} 
  
  
  
  
if (movable) 
  
  
  
  
// 確保節(jié)點r是樹根 
  
  
  
  
moveRootToFront(tab, r); 
  
  
  
  
} 
 
 
 
 

刪除紅黑樹節(jié)點之后的平衡代碼如下，筆者認為，應(yīng)當重點關(guān)注紅黑樹的變色、旋轉(zhuǎn)邏輯。

 
 
 
 

  
  
  
  
/** 
  
  
  
  
* 平衡紅黑樹-當刪除后 
  
  
  
  
* x: 影響平衡的點(俗稱：當前節(jié)點) 
  
  
  
  
*/
  
  
  
  

  
  
  
  
static TreeNode balanceDeletion(TreeNode root, 
  
  
  
  
TreeNode x) {
  
  
  
  

  
  
  
  
// xp: 當前節(jié)點的父節(jié)點
  
  
  
  

  
  
  
  
// xpl: 當前節(jié)點的父節(jié)點的左兒子
  
  
  
  

  
  
  
  
// xpr: 當前節(jié)點的父節(jié)點的右兒子
  
  
  
  

  
  
  
  
for (TreeNode xp, xpl, xpr;;) {
  
  
  
  

  
  
  
  
// 步驟①：當前節(jié)點是null或者是根節(jié)點，不改變紅黑樹的結(jié)構(gòu)，不需要改變
  
  
  
  

  
  
  
  
if (x == null || x == root)
  
  
  
  

  
  
  
  
return root;
  
  
  
  

  
  
  
  
// 步驟②：當前節(jié)點成為根節(jié)點，置為黑色
  
  
  
  

  
  
  
  
else if ((xp = x.parent) == null) {
  
  
  
  

  
  
  
  
x.red = false;
  
  
  
  

  
  
  
  
return x;
  
  
  
  

  
  
  
  
}
  
  
  
  

  
  
  
  
// 步驟③：當前節(jié)點為紅色，改為黑色后，不影響路徑上黑色的數(shù)量，不需要改變
  
  
  
  

  
  
  
  
else if (x.red) {
  
  
  
  

  
  
  
  
x.red = false;
  
  
  
  

  
  
  
  
return root;
  
  
  
  

  
  
  
  
}
  
  
  
  

  
  
  
  
// 步驟④：當前節(jié)點為父節(jié)點的左兒子
  
  
  
  

  
  
  
  
else if ((xpl = xp.left) == x) {
  
  
  
  

  
  
  
  
// 如果兄弟節(jié)點是紅色，那么父節(jié)點一定是黑色
  
  
  
  

  
  
  
  
if ((xpr = xp.right) != null && xpr.red) {
  
  
  
  

  
  
  
  
// 1.兄弟節(jié)點置為黑色
  
  
  
  

  
  
  
  
xpr.red = false;
  
  
  
  

  
  
  
  
// 2.父節(jié)點置為紅色
  
  
  
  

  
  
  
  
xp.red = true;
  
  
  
  

  
  
  
  
// 3.以父節(jié)點為支點左旋 
  
  
  
  
root = rotateLeft(root, xp);
  
  
  
  

  
  
  
  
// 4.刷新兄弟節(jié)點 
  
  
  
  
xpr = (xp = x.parent) == null ? null : xp.right;
  
  
  
  

  
  
  
  
}
  
  
  
  

  
  
  
  
// 如果兄弟節(jié)點為空，將當前節(jié)點向上調(diào)整為父節(jié)點，繼續(xù)循環(huán)
  
  
  
  

  
  
  
  
if (xpr == null)
  
  
  
  

  
  
  
  
x = xp;
  
  
  
  

  
  
  
  
else {
  
  
  
  

  
  
  
  
// sl: 兄弟節(jié)點的左兒子 
  
  
  
  
// sr: 兄弟節(jié)點的右兒子 
  
  
  
  
TreeNode sl = xpr.left, sr = xpr.right; 
  
  
  
  
if ((sr == null || !sr.red) && 
  
  
  
  
(sl == null || !sl.red)) { 
  
  
  
  
// 如果兄弟節(jié)點沒有紅色孩子，則兄弟節(jié)點置為紅色 
  
  
  
  
xpr.red = true; 
  
  
  
  
// 本輪結(jié)束，將當前節(jié)點向上調(diào)整為父節(jié)點，繼續(xù)循環(huán) 
  
  
  
  
x = xp;
  
  
  
  

  
  
  
  
}
  
  
  
  

  
  
  
  
else {
  
  
  
  

  
  
  
  
if (sr == null || !sr.red) { 
  
  
  
  
// 如果兄弟節(jié)點的左兒子是紅色就改為黑色 
  
  
  
  
if (sl != null) 
  
  
  
  
sl.red = false; 
  
  
  
  
// 并將兄弟節(jié)點置為紅色 
  
  
  
  
xpr.red = true; 
  
  
  
  
// 以兄弟節(jié)點為支點右旋 
  
  
  
  
root = rotateRight(root, xpr); 
  
  
  
  
// 刷新兄弟節(jié)點 
  
  
  
  
xpr = (xp = x.parent) == null ? 
  
  
  
  
null : xp.right; 
  
  
  
  
}
  
  
  
  

  
  
  
  
if (xpr != null) { 
  
  
  
  
// 將兄弟節(jié)點的顏色染成和父節(jié)點一樣 
  
  
  
  
xpr.red = (xp == null) ? false : xp.red;
  
  
  
  

  
  
  
  
// 將兄弟節(jié)點的右兒子染成黑色，防止出現(xiàn)兩個紅色節(jié)點相連 
  
  
  
  
if ((sr = xpr.right) != null) 
  
  
  
  
sr.red = false; 
  
  
  
  
}
  
  
  
  

  
  
  
  
if (xp != null) { 
  
  
  
  
// 父節(jié)點置為黑色，并對其左旋，這樣就能保證被刪除的節(jié)點所在的路徑又多了一個黑色節(jié)點，從而達到恢復(fù)平衡的目的 
  
  
  
  
xp.red = false; 
  
  
  
  
root = rotateLeft(root, xp); 
  
  
  
  
}
  
  
  
  

  
  
  
  
// 調(diào)整完畢，下一次循環(huán)直接退出 
  
  
  
  
x = root; 
  
  
  
  
} 
  
  
  
  
} 
  
  
  
  
}
  
  
  
  

  
  
  
  
// 步驟⑤：當前節(jié)點為父節(jié)點的右兒子，同上
  
  
  
  

  
  
  
  
else { // symmetric 
  
  
  
  
if (xpl != null && xpl.red) { 
  
  
  
  
xpl.red = false; 
  
  
  
  
xp.red = true; 
  
  
  
  
root = rotateRight(root, xp); 
  
  
  
  
xpl = (xp = x.parent) == null ? null : xp.left; 
  
  
  
  
}
  
  
  
  

  
  
  
  
if (xpl == null) 
  
  
  
  
x = xp;
  
  
  
  

  
  
  
  
else { 
  
  
  
  
TreeNode sl = xpl.left, sr = xpl.right; 
  
  
  
  
if ((sl == null || !sl.red) &&
  
  
  
  

  
  
  
  
(sr == null || !sr.red)) { 
  
  
  
  
xpl.red = true; 
  
  
  
  
x = xp;
  
  
  
  

  
  
  
  
}
  
  
  
  

  
  
  
  
else { 
  
  
  
  
if (sl == null || !sl.red) { 
  
  
  
  
if (sr != null) 
  
  
  
  
sr.red = false; 
  
  
  
  
xpl.red = true; 
  
  
  
  
root = rotateLeft(root, xpl); 
  
  
  
  
xpl = (xp = x.parent) == null ? 
  
  
  
  
null : xp.left;
  
  
  
  

  
  
  
  
}
  
  
  
  

  
  
  
  
                                                

                                                文章題目：逐行解讀HashMap源碼之紅黑樹篇                                                

                                                網(wǎng)站網(wǎng)址：http://www.5511xx.com/article/cojpdgp.html