建站
咨詢
售后
建站咨詢
新聞中心
這里有您想知道的互聯(lián)網(wǎng)營(yíng)銷解決方案
逐行解讀HashMap源碼之紅黑樹篇
【稿件】
寫在前面
本文是之前發(fā)表的文章《逐行解讀HashMap源碼》的下一篇，也是最后一篇。在《逐行解讀HashMap源碼》文章中，筆者主要分析了 HashMap 類的成員變量與成員方法，未涉及對(duì) HashMap 中紅黑樹相關(guān)內(nèi)容的分析。于是，筆者經(jīng)過(guò)一段的時(shí)間的編寫與打磨，寫出了本文。本文主要內(nèi)容包括對(duì)上一篇文章的些許補(bǔ)充以及對(duì)紅黑樹源碼的詳細(xì)解讀。
如果讀者沒有閱讀過(guò)上一篇內(nèi)容，可以微信搜索公眾號(hào)“代碼藝術(shù)”搜索并閱讀文章。
1. 紅黑樹概述
從本章節(jié)開始，筆者將對(duì) HashMap 內(nèi)部的 TreeNode 內(nèi)部類源碼開始分析，這部分的內(nèi)容也就是我們所說(shuō)的紅黑樹。
紅黑樹是建立在二叉查找樹的基礎(chǔ)之上的，二叉查找樹又是建立在二叉樹的基礎(chǔ)之上。所以，我們需要從二叉樹開始學(xué)習(xí)紅黑樹的發(fā)展脈絡(luò)。
2. 二叉樹
二叉樹(英語(yǔ)：Binary tree)是每個(gè)節(jié)點(diǎn)最多只有兩個(gè)分支(即不存在分支度大于2的節(jié)點(diǎn))的樹結(jié)構(gòu)。通常分支被稱作“左子樹”或“右子樹”。二叉樹的分支具有左右次序，不能隨意顛倒。
3. 二叉查找樹
二叉查找樹(英語(yǔ)：Binary Search Tree)，也稱為二叉搜索樹、有序二叉樹(ordered binary tree)或排序二叉樹(sorted binary tree)，是指一棵空樹或者具有下列性質(zhì)的二叉樹：
- 若任意節(jié)點(diǎn)的左子樹不空，則左子樹上所有節(jié)點(diǎn)的值均小于它的根節(jié)點(diǎn)的值;
- 若任意節(jié)點(diǎn)的右子樹不空，則右子樹上所有節(jié)點(diǎn)的值均大于或等于它的根節(jié)點(diǎn)的值;
- 任意節(jié)點(diǎn)的左、右子樹也分別為二叉查找樹;
一顆二叉查找樹如下圖所示：
但是，當(dāng)我們順序插入一系列節(jié)點(diǎn)后，二叉查找樹就退化為線性表，如下圖所示：
雖然二叉查找樹退化為線性表之后，最壞效率降為 O(n)。但依舊有很多改進(jìn)版的二叉查找樹可以使樹高為O(log n)，從而將最壞效率降至O(log n)，如AVL樹、紅黑樹等。
4. AVL樹
AVL 樹是最早被發(fā)明的自平衡二叉查找樹。在AVL樹中，任一節(jié)點(diǎn)對(duì)應(yīng)的兩棵子樹的最大高度差為 1 ，因此它也被稱為高度平衡樹。查找、插入和刪除在平均和最壞情況下的時(shí)間復(fù)雜度都是 O(logn)。增加和刪除元素的操作則可能需要借由一次或多次樹旋轉(zhuǎn)，以實(shí)現(xiàn)樹的重新平衡。
在 AVL 樹中，節(jié)點(diǎn)的**平衡因子**是它的左子樹的高度減去它的右子樹的高度(有時(shí)相反)。帶有平衡因子 1、0 或 -1 的節(jié)點(diǎn)被認(rèn)為是平衡的。帶有平衡因子 -2 或 2 的節(jié)點(diǎn)被認(rèn)為是不平衡的，并需要重新平衡這個(gè)樹。平衡因子可以直接存儲(chǔ)在每個(gè)節(jié)點(diǎn)中，或從可能存儲(chǔ)在節(jié)點(diǎn)中的子樹高度計(jì)算出來(lái)。
AVL 樹自平衡的方式是做一次或多次所謂的"AVL旋轉(zhuǎn)"。
5. 紅黑樹
紅黑樹(英語(yǔ)：Red–black tree)也是一種自平衡二叉查找樹。紅黑樹在二叉查找樹的基礎(chǔ)之上，對(duì)每個(gè)節(jié)點(diǎn)都增加了顏色屬性，分為紅色或黑色。在二叉查找樹強(qiáng)制的一般要求以外，對(duì)于任何有效的紅黑樹增加了如下 5 條額外要求：
- 節(jié)點(diǎn)是紅色或黑色。
- 根節(jié)點(diǎn)是黑色。
- 所有葉子都是黑色(葉子是NIL節(jié)點(diǎn))。
- 每個(gè)紅色節(jié)點(diǎn)必須有兩個(gè)黑色的子節(jié)點(diǎn)。(從每個(gè)葉子到根的所有路徑上不能有兩個(gè)連續(xù)的紅色節(jié)點(diǎn)。)
- 從任一節(jié)點(diǎn)到其每個(gè)葉子的所有簡(jiǎn)單路徑都包含相同數(shù)目的黑色節(jié)點(diǎn)。
下面是一個(gè)具體的紅黑樹的圖例：
紅黑樹的這些特性，保證了紅黑樹**從根到葉子的最長(zhǎng)的可能路徑不多于最短的可能路徑的兩倍長(zhǎng)**，造成的結(jié)果是紅黑樹大致上是平衡的。如上圖所示，"nil葉子"或"空(null)葉子"不包含數(shù)據(jù)而只充當(dāng)樹在此結(jié)束的指示。
對(duì)于紅黑樹的讀與寫，因?yàn)槊恳粋€(gè)紅黑樹都是一個(gè)(特殊的)二叉查找樹，因此紅黑樹上的只讀操作與普通二叉查找樹上的只讀操作相同。然而，在紅黑樹上進(jìn)行插入操作和刪除操作會(huì)導(dǎo)致不再符合紅黑樹的性質(zhì)?；謴?fù)紅黑樹的性質(zhì)需要少量 O(log n) 的顏色變更(實(shí)際是非常快速的)和不超過(guò)三次的樹旋轉(zhuǎn)(對(duì)于插入操作是兩次)。雖然插入和刪除很復(fù)雜，但操作時(shí)間仍可以保持為 O(log n) 次。
本章節(jié)開始結(jié)合 HashMap 源碼講解紅黑樹的插入、紅黑樹的刪除、紅黑樹的自平衡、左旋、右旋等內(nèi)容。
6. 鏈表轉(zhuǎn)為紅黑樹的過(guò)程
HashMap 的桶類型除了 Node (鏈表)外，還有 TreeNode (樹)。
TreeNode 類包含成員方法 `treeify()` ，該方法的作用是形成以當(dāng)前 TreeNode 對(duì)象為根節(jié)點(diǎn)的紅黑樹。
樹化過(guò)程不外乎是循環(huán)遍歷鏈表，構(gòu)造一顆二叉查找樹，最后使用紅黑樹的平衡方法進(jìn)行自平衡。
該方法源碼如下：
- final void treeify(Node[] tab) {
- TreeNode root = null;
- // 步驟①：循環(huán)遍歷當(dāng)前TreeNode鏈表
- for (TreeNode x = this, next; x != null; x = next) {
- next = (TreeNode)x.next;
- x.left = x.right = null;
- // 步驟②：如果還未設(shè)置根節(jié)點(diǎn)..
- if (root == null) {
- x.parent = null;
- x.red = false;
- root = x;
- }
- // 步驟③：如果已設(shè)置根節(jié)點(diǎn)..
- else {
- K k = x.key;
- int h = x.hash;
- Class kc = null;
- // 步驟④：從根節(jié)點(diǎn)開始遍歷，插入新節(jié)點(diǎn)
- for (TreeNode p = root;;) {
- int dir, ph;
- K pk = p.key;
- // 步驟⑤：比較當(dāng)前節(jié)點(diǎn)的hash值與新節(jié)點(diǎn)的hash值
- // 若是新節(jié)點(diǎn)hash值較小
- if ((ph = p.hash) > h)
- dir = -1;
- // 若是新節(jié)點(diǎn)的hash值較大
- else if (ph < h)
- dir = 1;
- // 若是新節(jié)點(diǎn)與當(dāng)前節(jié)點(diǎn)的hash值相等
- else if (
- // 如果新節(jié)點(diǎn)的key沒有實(shí)現(xiàn)Comparable接口..
- (kc == null && (kc = comparableClassFor(k)) == null)
- // 或者實(shí)現(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é)點(diǎn)經(jīng)比較后小于等于當(dāng)前節(jié)點(diǎn)且當(dāng)前節(jié)點(diǎn)的左子節(jié)點(diǎn)為null，則插入新節(jié)點(diǎn)，反之亦然
- 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é)點(diǎn)是所在桶的第一個(gè)節(jié)點(diǎn)
- moveRootToFront(tab, root);
- }
7. 紅黑樹的左旋和右旋
紅黑樹的左旋和右旋其實(shí)很簡(jiǎn)單，所謂的左旋是把要平衡的節(jié)點(diǎn)向左下旋轉(zhuǎn)成一個(gè)葉子節(jié)點(diǎn)。
如下圖所示：
所謂的右旋是把要平衡的節(jié)點(diǎn)向右下旋轉(zhuǎn)成一個(gè)葉子節(jié)點(diǎn)。
如下圖所示：
在 HashMap 的源碼中，左旋的實(shí)現(xiàn)代碼如下：
- static TreeNode rotateLeft(TreeNode root,
- TreeNode p) {
- // p: 當(dāng)前節(jié)點(diǎn)
- // r: 當(dāng)前節(jié)點(diǎn)的右兒子
- // rl: 當(dāng)前節(jié)點(diǎn)的右兒子的左兒子
- TreeNode r, pp, rl;
- // 如果當(dāng)前節(jié)點(diǎn)和當(dāng)前節(jié)點(diǎn)的右兒子不為空，就左旋
- if (p != null && (r = p.right) != null) {
- // 步驟①：當(dāng)前節(jié)點(diǎn)的右兒子的左兒子成為當(dāng)前節(jié)點(diǎn)的右兒子
- if ((rl = p.right = r.left) != null)
- rl.parent = p;
- // 步驟②：當(dāng)前節(jié)點(diǎn)的右兒子成為當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)
- if ((pp = r.parent = p.parent) == null)
- // 如果當(dāng)前節(jié)點(diǎn)是根節(jié)點(diǎn)，那么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;
- }
右旋的實(shí)現(xiàn)代碼如下：
- static TreeNode rotateRight(TreeNode root,
- TreeNode p) {
- // p: 當(dāng)前節(jié)點(diǎn)
- // l: 當(dāng)前節(jié)點(diǎn)的左兒子
- // lr: 當(dāng)前節(jié)點(diǎn)的左兒子的右兒子
- TreeNode l, pp, lr;
- // 如果當(dāng)前節(jié)點(diǎn)和當(dāng)前節(jié)點(diǎn)的左兒子不為空，就右旋
- if (p != null && (l = p.left) != null) {
- // 步驟①：當(dāng)前節(jié)點(diǎn)的左兒子的右兒子成為當(dāng)前節(jié)點(diǎn)的左兒子
- if ((lr = p.left = l.right) != null)
- lr.parent = p;
- // 步驟②：當(dāng)前節(jié)點(diǎn)的左兒子成為當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)
- if ((pp = l.parent = p.parent) == null)
- // 如果當(dāng)前節(jié)點(diǎn)是根節(jié)點(diǎn)，那么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é)點(diǎn)與當(dāng)前節(jié)點(diǎn)的大小。如果插入節(jié)點(diǎn)大于或等于當(dāng)前節(jié)點(diǎn)，則插入當(dāng)前節(jié)點(diǎn)的右子樹;否則，插入到左子樹。循環(huán)此過(guò)程，直到找到為空的葉子節(jié)點(diǎn)放入即可。
- /**
- * 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é)點(diǎn)
- TreeNode root = (parent != null) ? root() : this;
- for (TreeNode p = root;;) {
- // p: 當(dāng)前節(jié)點(diǎn)
- // dir: 標(biāo)識(shí)新節(jié)點(diǎn)應(yīng)該插入到當(dāng)前節(jié)點(diǎn)的左子樹還是右子樹
- // ph: 當(dāng)前節(jié)點(diǎn)的hash值
- // pk: 當(dāng)前節(jié)點(diǎn)的key
- int dir, ph; K pk;
- // 步驟①：判斷新節(jié)點(diǎn)應(yīng)該插入到當(dāng)前節(jié)點(diǎn)的左子樹還是右子樹
- 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é)點(diǎn)，插入新節(jié)點(diǎn)
- if ((p = (dir <= 0) ? p.left : p.right) == null) {
- // 1.父節(jié)點(diǎn)指向新節(jié)點(diǎn)
- Node xpn = xp.next;
- TreeNode x = map.newTreeNode(h, k, v, xpn);
- // 新節(jié)點(diǎn)位置在左子樹還是右子樹
- if (dir <= 0)
- xp.left = x;
- else
- xp.right = x;
- xp.next = x;
- // 2.新節(jié)點(diǎn)指向父節(jié)點(diǎn)
- x.parent = x.prev = xp;
- if (xpn != null)
- // 如果有兄弟節(jié)點(diǎn)，兄弟節(jié)點(diǎn)的上一個(gè)節(jié)點(diǎn)指向新節(jié)點(diǎn)
- ((TreeNode)xpn).prev = x;
- // 最后平衡紅黑樹，并保證根節(jié)點(diǎn)在哈希桶的頭部
- moveRootToFront(tab, balanceInsertion(root, x));
- return null;
- }
- }
- }
紅黑樹的插入與二叉查找樹的不同之處，在于最后的平衡部分。
插入節(jié)點(diǎn)之后的紅黑樹平衡方法如下：
- /**
- * 平衡紅黑樹-當(dāng)新增后
- * x: 影響平衡的點(diǎn)(俗稱：當(dāng)前節(jié)點(diǎn))
- */
- static TreeNode balanceInsertion(TreeNode root,
- TreeNode x) {
- // 新增節(jié)點(diǎn)x默認(rèn)是紅色
- x.red = true;
- // xp父節(jié)點(diǎn) xpp祖父節(jié)點(diǎn) xppl祖父左節(jié)點(diǎn) xppr 祖父右節(jié)點(diǎn)(p: parent, l: left, r: right)
- for (TreeNode xp, xpp, xppl, xppr;;) {
- if ((xp = x.parent) == null) {
- // 步驟①：如果插入的是根節(jié)點(diǎn)，根據(jù)紅黑樹性質(zhì)之根節(jié)點(diǎn)是黑色，直接涂黑即可
- x.red = false;
- return x;
- }
- // 步驟②：插入節(jié)點(diǎn)的父節(jié)點(diǎn)是黑色或者父節(jié)點(diǎn)是根節(jié)點(diǎn)，紅黑樹沒有被破壞，不需要調(diào)整
- else if (!xp.red || (xpp = xp.parent) == null)
- return root;
- // 父節(jié)點(diǎn)是祖父節(jié)點(diǎn)的左子節(jié)點(diǎn)
- if (xp == (xppl = xpp.left)) {
- // 步驟③：當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)是紅色，且叔叔節(jié)點(diǎn)也是紅色
- if ((xppr = xpp.right) != null && xppr.red) {
- // 1.叔叔節(jié)點(diǎn)設(shè)置為黑色
- xppr.red = false;
- // 2.父節(jié)點(diǎn)設(shè)置為黑色
- xp.red = false;
- // 3.祖父節(jié)點(diǎn)設(shè)置為紅色
- xpp.red = true;
- // 4.將當(dāng)前節(jié)點(diǎn)指向祖父節(jié)點(diǎn)，從新的當(dāng)前節(jié)點(diǎn)重新開始算法
- x = xpp;
- }
- else {
- // 步驟④：當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)是紅色，且叔叔節(jié)點(diǎn)是黑色，當(dāng)前節(jié)點(diǎn)是其父右子節(jié)點(diǎn)
- if (x == xp.right) {
- // 當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)作為新的當(dāng)前節(jié)點(diǎn)，以新當(dāng)節(jié)點(diǎn)為支點(diǎn)左旋
- root = rotateLeft(root, x = xp);
- // 重新賦值
- xpp = (xp = x.parent) == null ? null : xp.parent;
- }
- if (xp != null) {
- // 父節(jié)點(diǎn)設(shè)置為黑色
- xp.red = false;
- if (xpp != null) {
- // 祖父節(jié)點(diǎn)設(shè)置為紅色
- xpp.red = true;
- // 以祖父節(jié)點(diǎn)為支點(diǎn)右旋
- root = rotateRight(root, xpp);
- }
- }
- }
- }
- // 父節(jié)點(diǎn)是祖父節(jié)點(diǎn)的右子節(jié)點(diǎn)
- else {
- // 步驟③：當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)是紅色，且叔叔節(jié)點(diǎn)也是紅色
- if (xppl != null && xppl.red) {
- // 1.叔叔節(jié)點(diǎn)設(shè)置為黑色
- xppl.red = false;
- // 2.父節(jié)點(diǎn)設(shè)置為黑色
- xp.red = false;
- // 3.祖父節(jié)點(diǎn)設(shè)置為紅色
- xpp.red = true;
- // 4.將當(dāng)前節(jié)點(diǎn)指向祖父節(jié)點(diǎn)，從新的當(dāng)前節(jié)點(diǎn)重新開始算法
- x = xpp;
- }
- else {
- // 步驟④：當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)是紅色，且叔叔節(jié)點(diǎn)是黑色，當(dāng)前節(jié)點(diǎn)是其父左子節(jié)點(diǎn)
- if (x == xp.left) {
- // 當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)作為新的當(dāng)前節(jié)點(diǎn)，以新當(dāng)節(jié)點(diǎn)為支點(diǎn)右旋
- root = rotateRight(root, x = xp);
- // 重新賦值
- xpp = (xp = x.parent) == null ? null : xp.parent;
- }
- if (xp != null) {
- // 父節(jié)點(diǎn)設(shè)置為黑色
- xp.red = false;
- if (xpp != null) {
- // 祖父節(jié)點(diǎn)設(shè)置為紅色
- xpp.red = true;
- // 以祖父節(jié)點(diǎn)為支點(diǎn)左旋
- root = rotateLeft(root, xpp);
- }
- }
- }
- }
- }
- }
10. 紅黑樹的刪除
紅黑樹的刪除相比插入更加復(fù)雜，需要先從鏈表結(jié)構(gòu)上進(jìn)行刪除，也就是處理當(dāng)前節(jié)點(diǎn)的 next 指針與 prev 指針。如果當(dāng)前樹的節(jié)點(diǎn)太少，那么就將樹退化為鏈表。然后，查找被刪除節(jié)點(diǎn)的后繼節(jié)點(diǎn)。所謂后繼節(jié)點(diǎn)，就是當(dāng)刪除節(jié)點(diǎn)p后，如果p有子節(jié)點(diǎn)，p的子節(jié)點(diǎn)上移繼承其位置。當(dāng)找到后繼節(jié)點(diǎn)，立即刪除節(jié)點(diǎn)，如果被刪除節(jié)點(diǎn)是紅色，那么不需要平衡，否則平衡紅黑樹。
紅黑樹的刪除方法代碼如下：
- final void removeTreeNode(HashMap map, Node[] tab,
- boolean movable) {
- int n;
- if (tab == null || (n = tab.length) == 0)
- // 不處理空的哈希表
- return;
- // 第 1 部分: 處理鏈表結(jié)構(gòu)
- // 通過(guò)被刪除的key的哈希值查找桶(紅黑樹)的位置
- int index = (n - 1) & hash;
- // first、root: 紅黑樹的根節(jié)點(diǎn)
- TreeNode first = (TreeNode)tab[index], root = first, rl;
- // succ: 當(dāng)前節(jié)點(diǎn)(被刪除節(jié)點(diǎn))的下一個(gè)節(jié)點(diǎn)
- // pred: 當(dāng)前節(jié)點(diǎn)(被刪除節(jié)點(diǎn))的上一個(gè)節(jié)點(diǎn)
- TreeNode succ = (TreeNode)next, pred = prev;
- // 步驟①：從鏈表結(jié)構(gòu)上刪除當(dāng)前節(jié)點(diǎn)(處理上一個(gè)節(jié)點(diǎn)的 next 指針與下一個(gè)節(jié)點(diǎn)的 prev 指針)
- if (pred == null)
- // 上一個(gè)節(jié)點(diǎn)為空，說(shuō)明是要?jiǎng)h除的是根節(jié)點(diǎn)，將紅黑樹的根節(jié)點(diǎn)索引改為當(dāng)前節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)
- tab[index] = first = succ;
- else
- // 刪除的不是根節(jié)點(diǎn)，就把當(dāng)前節(jié)點(diǎn)的上一個(gè)節(jié)點(diǎn)的next指向當(dāng)前節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)
- pred.next = succ;
- if (succ != null)
- // 當(dāng)前節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)不為空，就把下一個(gè)節(jié)點(diǎn)的prev指向當(dāng)前節(jié)點(diǎn)的上一個(gè)節(jié)點(diǎn)
- succ.prev = pred;
- // 步驟②：刪除節(jié)點(diǎn)完畢后，紅黑樹為空，直接返回
- 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é)點(diǎn); replacement: 后繼節(jié)點(diǎn)(刪除節(jié)點(diǎn)p后，如果p有子節(jié)點(diǎn)，p的子節(jié)點(diǎn)上移繼承其位置)
- // pl: 被刪除節(jié)點(diǎn)的左兒子; pr: 被刪除節(jié)點(diǎn)的右兒子
- TreeNode p = this, pl = left, pr = right, replacement;
- // 步驟①：查找被刪除節(jié)點(diǎn)的后繼節(jié)點(diǎn)，分以下幾種情況
- // ⑴ 被刪除節(jié)點(diǎn)有左子樹和右子樹
- if (pl != null && pr != null) {
- TreeNode s = pr, sl;
- // 1.查找右子樹最左葉子節(jié)點(diǎn)s與待刪除節(jié)點(diǎn)p進(jìn)行位置互換
- while ((sl = s.left) != null) // find successor
- s = sl;
- // 2.交換最左葉子節(jié)點(diǎn)和待刪除節(jié)點(diǎn)的顏色
- boolean c = s.red; s.red = p.red; p.red = c; // swap colors
- // sr：最左葉子節(jié)點(diǎn)的右兒子
- TreeNode sr = s.right;
- // pp：被刪除節(jié)點(diǎn)的父節(jié)點(diǎn)
- TreeNode pp = p.parent;
- // 3.交換被刪除節(jié)點(diǎn)p和最左葉子節(jié)點(diǎn)s的位置
- // 判斷最左葉子節(jié)點(diǎn)是否是被刪除節(jié)點(diǎn)的右兒子(即右子樹是否只有一個(gè)節(jié)點(diǎn))分別處理節(jié)點(diǎn)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é)點(diǎn)和被刪除節(jié)點(diǎn)的位置完成
- // 此時(shí)被刪除節(jié)點(diǎn)p在原最左葉子節(jié)點(diǎn)的位置，現(xiàn)在被刪除節(jié)點(diǎn)p沒有左子樹，如果有右子樹，那么右兒子sr就是后繼節(jié)點(diǎn)，否則后繼節(jié)點(diǎn)指向自身
- if (sr != null)
- replacement = sr;
- else
- replacement = p;
- }
- // ⑵ 被刪除節(jié)點(diǎn)只有左子樹，后繼節(jié)點(diǎn)就是左兒子
- else if (pl != null)
- replacement = pl;
- // ⑶ 被刪除節(jié)點(diǎn)只有右子樹，后繼節(jié)點(diǎn)就是右兒子
- else if (pr != null)
- replacement = pr;
- // ⑷ 被刪除節(jié)點(diǎn)沒有子樹，那么后繼節(jié)點(diǎn)就指向自身
- else
- replacement = p;
- // 步驟②：已經(jīng)找到刪除節(jié)點(diǎn)后的后繼節(jié)點(diǎn)，這一步將從樹中徹底刪除節(jié)點(diǎn)p。
- if (replacement != p) {
- // 1.修改替代節(jié)點(diǎn)的父節(jié)點(diǎn)引用
- TreeNode pp = replacement.parent = p.parent;
- // 2.將被刪除節(jié)點(diǎn)的父節(jié)點(diǎn)對(duì)其的引用進(jìn)行修改
- if (pp == null)
- root = replacement;
- else if (p == pp.left)
- pp.left = replacement;
- else
- pp.right = replacement;
- // 3.徹底刪除節(jié)點(diǎn)p
- p.left = p.right = p.parent = null;
- }
- // 步驟③：刪除節(jié)點(diǎn)完成，刪除的是紅色節(jié)點(diǎn)，不需要平衡;否則，平衡
- TreeNode r = p.red ? root : balanceDeletion(root, replacement);
- // 步驟④：若沒有后繼節(jié)點(diǎn)，直接刪除節(jié)點(diǎn)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é)點(diǎn)r是樹根
- moveRootToFront(tab, r);
- }
刪除紅黑樹節(jié)點(diǎn)之后的平衡代碼如下，筆者認(rèn)為，應(yīng)當(dāng)重點(diǎn)關(guān)注紅黑樹的變色、旋轉(zhuǎn)邏輯。
- /**
- * 平衡紅黑樹-當(dāng)刪除后
- * x: 影響平衡的點(diǎn)(俗稱：當(dāng)前節(jié)點(diǎn))
- */
- static TreeNode balanceDeletion(TreeNode root,
- TreeNode x) {
- // xp: 當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)
- // xpl: 當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)的左兒子
- // xpr: 當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)的右兒子
- for (TreeNode xp, xpl, xpr;;) {
- // 步驟①：當(dāng)前節(jié)點(diǎn)是null或者是根節(jié)點(diǎn)，不改變紅黑樹的結(jié)構(gòu)，不需要改變
- if (x == null || x == root)
- return root;
- // 步驟②：當(dāng)前節(jié)點(diǎn)成為根節(jié)點(diǎn)，置為黑色
- else if ((xp = x.parent) == null) {
- x.red = false;
- return x;
- }
- // 步驟③：當(dāng)前節(jié)點(diǎn)為紅色，改為黑色后，不影響路徑上黑色的數(shù)量，不需要改變
- else if (x.red) {
- x.red = false;
- return root;
- }
- // 步驟④：當(dāng)前節(jié)點(diǎn)為父節(jié)點(diǎn)的左兒子
- else if ((xpl = xp.left) == x) {
- // 如果兄弟節(jié)點(diǎn)是紅色，那么父節(jié)點(diǎn)一定是黑色
- if ((xpr = xp.right) != null && xpr.red) {
- // 1.兄弟節(jié)點(diǎn)置為黑色
- xpr.red = false;
- // 2.父節(jié)點(diǎn)置為紅色
- xp.red = true;
- // 3.以父節(jié)點(diǎn)為支點(diǎn)左旋
- root = rotateLeft(root, xp);
- // 4.刷新兄弟節(jié)點(diǎn)
- xpr = (xp = x.parent) == null ? null : xp.right;
- }
- // 如果兄弟節(jié)點(diǎn)為空，將當(dāng)前節(jié)點(diǎn)向上調(diào)整為父節(jié)點(diǎn)，繼續(xù)循環(huán)
- if (xpr == null)
- x = xp;
- else {
- // sl: 兄弟節(jié)點(diǎn)的左兒子
- // sr: 兄弟節(jié)點(diǎn)的右兒子
- TreeNode sl = xpr.left, sr = xpr.right;
- if ((sr == null || !sr.red) &&
- (sl == null || !sl.red)) {
- // 如果兄弟節(jié)點(diǎn)沒有紅色孩子，則兄弟節(jié)點(diǎn)置為紅色
- xpr.red = true;
- // 本輪結(jié)束，將當(dāng)前節(jié)點(diǎn)向上調(diào)整為父節(jié)點(diǎn)，繼續(xù)循環(huán)
- x = xp;
- }
- else {
- if (sr == null || !sr.red) {
- // 如果兄弟節(jié)點(diǎn)的左兒子是紅色就改為黑色
- if (sl != null)
- sl.red = false;
- // 并將兄弟節(jié)點(diǎn)置為紅色
- xpr.red = true;
- // 以兄弟節(jié)點(diǎn)為支點(diǎn)右旋
- root = rotateRight(root, xpr);
- // 刷新兄弟節(jié)點(diǎn)
- xpr = (xp = x.parent) == null ?
- null : xp.right;
- }
- if (xpr != null) {
- // 將兄弟節(jié)點(diǎn)的顏色染成和父節(jié)點(diǎn)一樣
- xpr.red = (xp == null) ? false : xp.red;
- // 將兄弟節(jié)點(diǎn)的右兒子染成黑色，防止出現(xiàn)兩個(gè)紅色節(jié)點(diǎn)相連
- if ((sr = xpr.right) != null)
- sr.red = false;
- }
- if (xp != null) {
- // 父節(jié)點(diǎn)置為黑色，并對(duì)其左旋，這樣就能保證被刪除的節(jié)點(diǎn)所在的路徑又多了一個(gè)黑色節(jié)點(diǎn)，從而達(dá)到恢復(fù)平衡的目的
- xp.red = false;
- root = rotateLeft(root, xp);
- }
- // 調(diào)整完畢，下一次循環(huán)直接退出
- x = root;
- }
- }
- }
- // 步驟⑤：當(dāng)前節(jié)點(diǎn)為父節(jié)點(diǎn)的右兒子，同上
- 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;
- }
網(wǎng)站標(biāo)題：逐行解讀HashMap源碼之紅黑樹篇
本文地址：http://m.fisionsoft.com.cn/article/cojpdgp.html
