刪除操作詳解：從核心原理到Java實(shí)現(xiàn))
1. 紅黑樹(shù)刪除為什么它比插入更讓人“頭大”如果你已經(jīng)啃過(guò)紅黑樹(shù)的插入操作并且覺(jué)得那些左旋右旋、顏色翻轉(zhuǎn)的規(guī)則雖然繁瑣但還能理清那么恭喜你即將迎來(lái)真正的“硬骨頭”——?jiǎng)h除。在數(shù)據(jù)結(jié)構(gòu)與算法的世界里紅黑樹(shù)的刪除操作以其復(fù)雜的場(chǎng)景分支和精妙的修復(fù)邏輯長(zhǎng)期穩(wěn)坐“面試八股文難點(diǎn)”和“實(shí)際工程調(diào)試噩夢(mèng)”的寶座。很多朋友在學(xué)完插入后面對(duì)刪除那一長(zhǎng)串的case分析直接選擇了“戰(zhàn)略放棄”或者只記結(jié)論不問(wèn)緣由。但今天我想帶你換個(gè)角度不是去死記硬背那五六種情況而是嘗試?yán)斫馄浔澈蟮暮诵拿芘c設(shè)計(jì)哲學(xué)。刪除之所以復(fù)雜根本原因在于它要維護(hù)的平衡性約束比插入更多、更脆弱。插入一個(gè)新節(jié)點(diǎn)最壞情況是破壞“紅節(jié)點(diǎn)不能相鄰”和“根節(jié)點(diǎn)為黑”兩條規(guī)則通過(guò)有限的旋轉(zhuǎn)和變色就能修復(fù)。而刪除一個(gè)節(jié)點(diǎn)尤其是刪除一個(gè)黑色節(jié)點(diǎn)會(huì)直接導(dǎo)致它所在的路徑上“黑色節(jié)點(diǎn)數(shù)量”黑高減少這會(huì)動(dòng)搖紅黑樹(shù)五大核心法則的根基。修復(fù)過(guò)程本質(zhì)上是在不引入新破壞的前提下將這份“缺失的黑色”巧妙地轉(zhuǎn)移或抵消掉。我們即將用Java實(shí)現(xiàn)的就是這套精巧的“外科手術(shù)”過(guò)程。我會(huì)把重點(diǎn)放在“為什么需要這么做”的邏輯推導(dǎo)上而不僅僅是“怎么做”的步驟羅列。當(dāng)你理解了每個(gè)旋轉(zhuǎn)和變色操作背后的意圖那些看似繁雜的case就會(huì)變得清晰而有條理。2. 重溫紅黑樹(shù)為刪除操作奠定認(rèn)知基礎(chǔ)在動(dòng)刀之前我們必須對(duì)“病人”有清晰的了解。紅黑樹(shù)不是一顆普通的二叉搜索樹(shù)BST它是帶著嚴(yán)格平衡約束的BST。這些約束就是我們修復(fù)操作的“憲法”。2.1 五大核心法則再審視節(jié)點(diǎn)非黑即紅每個(gè)節(jié)點(diǎn)要么是紅色要么是黑色。根節(jié)點(diǎn)為黑樹(shù)的根節(jié)點(diǎn)必須是黑色。葉子節(jié)點(diǎn)NIL為黑所有葉子節(jié)點(diǎn)指為空的、不存儲(chǔ)數(shù)據(jù)的節(jié)點(diǎn)通常用NIL表示都是黑色。紅色不相鄰不能有兩個(gè)連續(xù)的紅色節(jié)點(diǎn)。即一個(gè)紅色節(jié)點(diǎn)的父節(jié)點(diǎn)和子節(jié)點(diǎn)都不能是紅色。黑高一致從任意一個(gè)節(jié)點(diǎn)到其所有后代葉子節(jié)點(diǎn)NIL的路徑上包含的黑色節(jié)點(diǎn)數(shù)量必須相同。這個(gè)數(shù)量稱為該節(jié)點(diǎn)的“黑高”。刪除操作最大的挑戰(zhàn)正是來(lái)自于對(duì)法則5的維護(hù)。當(dāng)我們刪除一個(gè)黑色節(jié)點(diǎn)時(shí)從根節(jié)點(diǎn)到某些葉子節(jié)點(diǎn)的路徑上就少了一個(gè)黑色節(jié)點(diǎn)導(dǎo)致黑高不一致樹(shù)就失去了平衡。2.2 二叉搜索樹(shù)的刪除邏輯所有故事的起點(diǎn)紅黑樹(shù)的刪除建立在BST刪除的基礎(chǔ)上。BST刪除一個(gè)節(jié)點(diǎn)有三種基本情況這是我們所有后續(xù)復(fù)雜修復(fù)的起點(diǎn)必須爛熟于心情況A刪除葉子節(jié)點(diǎn)或僅有一個(gè)子節(jié)點(diǎn)的節(jié)點(diǎn)。這是最簡(jiǎn)單的情況。如果它是葉子節(jié)點(diǎn)直接將其父節(jié)點(diǎn)對(duì)應(yīng)的指針置為NIL。如果它有一個(gè)子節(jié)點(diǎn)則用這個(gè)子節(jié)點(diǎn)“頂替”它的位置連接到它的父節(jié)點(diǎn)上。情況B刪除有兩個(gè)子節(jié)點(diǎn)的節(jié)點(diǎn)。這種情況不能直接刪除否則會(huì)破壞樹(shù)的結(jié)構(gòu)。標(biāo)準(zhǔn)的做法是找到它的中序遍歷后繼節(jié)點(diǎn)即右子樹(shù)中的最小節(jié)點(diǎn)或者中序遍歷前驅(qū)節(jié)點(diǎn)即左子樹(shù)中的最大節(jié)點(diǎn)。用這個(gè)后繼或前驅(qū)節(jié)點(diǎn)的值覆蓋要?jiǎng)h除的節(jié)點(diǎn)值然后問(wèn)題轉(zhuǎn)化為刪除那個(gè)后繼或前驅(qū)節(jié)點(diǎn)。關(guān)鍵在于這個(gè)后繼節(jié)點(diǎn)最多只有一個(gè)右子節(jié)點(diǎn)因?yàn)樗亲钚≈颠@就將問(wèn)題簡(jiǎn)化為了情況A。在紅黑樹(shù)的語(yǔ)境下我們真正從結(jié)構(gòu)上移除的節(jié)點(diǎn)記為removedNode只會(huì)是情況A中的節(jié)點(diǎn)即至多有一個(gè)非NIL子節(jié)點(diǎn)。而后續(xù)所有的修復(fù)工作都是圍繞著這個(gè)被移除節(jié)點(diǎn)的位置和顏色展開(kāi)的。3. 刪除情景框架與核心變量定義讓我們開(kāi)始構(gòu)建刪除的框架。在Java中我們首先定義節(jié)點(diǎn)類并引入一個(gè)關(guān)鍵的“哨兵”NIL節(jié)點(diǎn)它代表所有空的葉子節(jié)點(diǎn)顏色為黑。class RBTreeNode { int key; RBTreeNode left, right, parent; boolean color; // 我們用 true 表示 RED, false 表示 BLACK // 構(gòu)造函數(shù)等... static final RBTreeNode NIL new RBTreeNode(0); // 哨兵節(jié)點(diǎn) static { NIL.color BLACK; } }刪除的主入口方法如下public void delete(int key) { RBTreeNode node search(root, key); if (node NIL) return; // 節(jié)點(diǎn)不存在 deleteNode(node); }核心的deleteNode方法其邏輯與BST刪除一致但需要記錄關(guān)鍵信息以供修復(fù)private void deleteNode(RBTreeNode z) { RBTreeNode y z; // y 指向最終要被從樹(shù)中“結(jié)構(gòu)移除”的節(jié)點(diǎn) RBTreeNode x; // x 指向可能頂替 y 位置的節(jié)點(diǎn)也是后續(xù)修復(fù)的起點(diǎn) boolean yOriginalColor y.color; // 情況1 2z 至多有一個(gè)非NIL子節(jié)點(diǎn) if (z.left NIL) { x z.right; transplant(z, z.right); } else if (z.right NIL) { x z.left; transplant(z, z.left); } else { // 情況3z 有兩個(gè)子節(jié)點(diǎn) y minimum(z.right); // 找到后繼節(jié)點(diǎn) yOriginalColor y.color; x y.right; // 后繼節(jié)點(diǎn)的右子節(jié)點(diǎn)可能是NIL if (y.parent z) { // 特殊情況后繼節(jié)點(diǎn)y就是z的右孩子 x.parent y; // 重要確保x的父指針正確即使x是NIL } else { // 一般情況y在z的右子樹(shù)中但不是直接右孩子 transplant(y, y.right); y.right z.right; y.right.parent y; } // 用y替換z transplant(z, y); y.left z.left; y.left.parent y; y.color z.color; // 繼承z的顏色這是關(guān)鍵。 } // 如果被移除的原始節(jié)點(diǎn)y是黑色的則可能破壞紅黑樹(shù)性質(zhì) if (yOriginalColor BLACK) { deleteFixUp(x); } }這里有幾個(gè)至關(guān)重要的變量理解它們是你理清后續(xù)所有情況的關(guān)鍵z: 最初要?jiǎng)h除的目標(biāo)節(jié)點(diǎn)。y: 最終從樹(shù)結(jié)構(gòu)中被移除的節(jié)點(diǎn)。在情況A中y就是z在情況B中y是z的后繼節(jié)點(diǎn)。我們修復(fù)操作所關(guān)注的“被刪除節(jié)點(diǎn)”指的是這個(gè)y。yOriginalColor: 節(jié)點(diǎn)y在被移除前的顏色。只有yOriginalColor為BLACK時(shí)才需要進(jìn)行修復(fù)。因?yàn)閯h除紅色節(jié)點(diǎn)不影響任何路徑的黑高。x: 頂替y原來(lái)位置的節(jié)點(diǎn)。可能是y的唯一子節(jié)點(diǎn)也可能是NIL。x被提升到了y原來(lái)的位置x的父節(jié)點(diǎn)就是原來(lái)y的父節(jié)點(diǎn)。修復(fù)過(guò)程將從x節(jié)點(diǎn)開(kāi)始向上進(jìn)行。transplant(u, v): 一個(gè)輔助操作用子樹(shù)v替換子樹(shù)u僅處理父指針的關(guān)聯(lián)。核心洞見(jiàn)刪除修復(fù)deleteFixUp(x)的核心任務(wù)就是解決“因?yàn)閯h除了一個(gè)黑色節(jié)點(diǎn)y導(dǎo)致經(jīng)過(guò)x的路徑黑高少1”的問(wèn)題。x節(jié)點(diǎn)承載了這份“黑色缺失”修復(fù)過(guò)程就是圍繞x展開(kāi)的。4. 刪除修復(fù)的終極邏輯圍繞X的兄弟做文章現(xiàn)在進(jìn)入最核心的部分deleteFixUp(x)。此時(shí)x可能是紅也可能是黑或NIL視為黑。如果x是紅色我們直接把它染成黑色就能立刻補(bǔ)上缺失的黑色問(wèn)題解決。所以所有復(fù)雜情況都發(fā)生在x是黑色的時(shí)候。修復(fù)過(guò)程是一個(gè)從x開(kāi)始向上迭代的循環(huán)。循環(huán)的目標(biāo)是將額外的“黑色”向上推送直到遇到一個(gè)紅色節(jié)點(diǎn)將其變黑或者推到根節(jié)點(diǎn)循環(huán)結(jié)束。這個(gè)“額外的黑色”是一個(gè)邏輯概念意味著x節(jié)點(diǎn)現(xiàn)在“承載”了雙重黑色double black或紅黑色破壞了顏色規(guī)則我們需要通過(guò)調(diào)整來(lái)消除它。循環(huán)中的每一步我們都在審視x、x的兄弟節(jié)點(diǎn)w、以及它們的父親p之間的關(guān)系。根據(jù)w的顏色和w子樹(shù)的顏色分布我們分為四大主情況。請(qǐng)務(wù)必記住我們的視角始終固定在當(dāng)前節(jié)點(diǎn)x上。4.1 情況一X的兄弟W是紅色場(chǎng)景x是黑色其兄弟w是紅色。此時(shí)根據(jù)紅黑樹(shù)性質(zhì)父親p和w的兩個(gè)子節(jié)點(diǎn)必然都是黑色。目標(biāo)此情況的目標(biāo)是將問(wèn)題轉(zhuǎn)化為兄弟w是黑色的情況情況二、三、四因?yàn)楹罄m(xù)的操作都需要基于黑色兄弟進(jìn)行。操作將兄弟w染黑。將父親p染紅。對(duì)p進(jìn)行左旋如果x是左孩子或右旋如果x是右孩子。旋轉(zhuǎn)后x有了一個(gè)新的兄弟節(jié)點(diǎn)原w的某個(gè)黑孩子這個(gè)新兄弟變成了黑色。問(wèn)題進(jìn)入情況二、三或四。為什么這樣做旋轉(zhuǎn)操作改變了局部結(jié)構(gòu)但保持了子樹(shù)的黑高不變。將w變黑、p變紅是為了在旋轉(zhuǎn)后x所在路徑的黑高不增加而w所在路徑通過(guò)結(jié)構(gòu)調(diào)整為后續(xù)的“借調(diào)”操作做準(zhǔn)備。// 代碼片段示意 if (w.color RED) { w.color BLACK; x.parent.color RED; if (x x.parent.left) { leftRotate(x.parent); w x.parent.right; // 更新兄弟節(jié)點(diǎn)為新的黑色兄弟 } else { // 對(duì)稱操作... } }4.2 情況二X的兄弟W是黑色且W的兩個(gè)子節(jié)點(diǎn)都是黑色場(chǎng)景x是黑色兄弟w是黑色并且w的兩個(gè)孩子都是黑色或NIL。目標(biāo)此時(shí)無(wú)法從兄弟子樹(shù)“借”一個(gè)紅色節(jié)點(diǎn)或黑色節(jié)點(diǎn)過(guò)來(lái)。策略是將x和w各自“拿走”一層黑色將這層黑色“上交給”父親p。這樣x的“雙重黑色”問(wèn)題解決了但父親p可能變成了新的“雙重黑色”或“紅黑”節(jié)點(diǎn)。操作將兄弟w染紅。將x指向其父親p。結(jié)果原來(lái)x的“雙重黑色”被消除但p節(jié)點(diǎn)如果原來(lái)是紅色現(xiàn)在變成了“紅黑”實(shí)際表現(xiàn)為紅色但邏輯上多一層黑循環(huán)結(jié)束如果p原來(lái)是黑色現(xiàn)在則變成了新的“雙重黑色”節(jié)點(diǎn)循環(huán)繼續(xù)以p作為新的x向上處理。為什么這樣做這是一種“收縮”策略。通過(guò)將兄弟一側(cè)也減少一層黑色w由黑變紅使得以p為根的子樹(shù)整體黑高減1從而讓p來(lái)承擔(dān)黑高不平衡的問(wèn)題將矛盾上移。4.3 情況三X的兄弟W是黑色W的近侄子為紅遠(yuǎn)侄子為黑場(chǎng)景假設(shè)x是左孩子。其兄弟w是黑色w的左孩子x的“近侄子”是紅色w的右孩子x的“遠(yuǎn)侄子”是黑色。對(duì)稱情況同理。目標(biāo)此情況是一個(gè)過(guò)渡狀態(tài)目標(biāo)是通過(guò)旋轉(zhuǎn)將其轉(zhuǎn)換為情況四因?yàn)榍闆r四有更直接的修復(fù)方案。操作將w的近侄子紅色染黑。將w自身染紅。對(duì)w進(jìn)行右旋以近侄子為軸。旋轉(zhuǎn)后x的兄弟節(jié)點(diǎn)更新為原近侄子現(xiàn)在已變黑且新兄弟的遠(yuǎn)侄子變成了紅色。這完美符合情況四的條件。為什么這樣做這個(gè)操作像是一個(gè)“預(yù)備動(dòng)作”。它通過(guò)一次旋轉(zhuǎn)和變色在兄弟子樹(shù)內(nèi)部重新布局創(chuàng)造出一個(gè)紅色節(jié)點(diǎn)位于“遠(yuǎn)侄子”位置的條件為情況四的“終極借調(diào)”搭建好了舞臺(tái)。4.4 情況四X的兄弟W是黑色且W的遠(yuǎn)侄子為紅色場(chǎng)景x是左孩子其兄弟w是黑色且w的右孩子遠(yuǎn)侄子是紅色。這是修復(fù)操作的“終結(jié)者”情況。目標(biāo)通過(guò)一次旋轉(zhuǎn)和變色直接從兄弟子樹(shù)“借調(diào)”一個(gè)黑色節(jié)點(diǎn)過(guò)來(lái)徹底解決x的“雙重黑色”問(wèn)題并保持所有紅黑樹(shù)性質(zhì)。操作將兄弟w的顏色設(shè)置為父親p的顏色。將父親p染黑。將w的遠(yuǎn)侄子紅色染黑。對(duì)父親p進(jìn)行左旋。結(jié)果旋轉(zhuǎn)后x的“雙重黑色”被消除因?yàn)槠渌诼窂酵ㄟ^(guò)旋轉(zhuǎn)增加了一個(gè)黑色節(jié)點(diǎn)p。同時(shí)原來(lái)w的遠(yuǎn)侄子被染黑保證了該側(cè)路徑黑高不變。所有性質(zhì)恢復(fù)修復(fù)完成循環(huán)可以終止。為什么這樣做這是最精妙的一步。旋轉(zhuǎn)操作將父親p拉下來(lái)變成了x所在子樹(shù)的新根黑色相當(dāng)于給x的路徑“補(bǔ)”了一個(gè)黑色節(jié)點(diǎn)。而將w提升為新的局部根并繼承原p的顏色保證了整棵樹(shù)的結(jié)構(gòu)和顏色規(guī)則得以完美維持。5. Java完整實(shí)現(xiàn)與逐行解析理解了上述四種核心情況我們就可以拼裝出完整的deleteFixUp方法。以下是完整的Java實(shí)現(xiàn)包含了對(duì)稱情況的處理。private void deleteFixUp(RBTreeNode x) { while (x ! root x.color BLACK) { if (x x.parent.left) { // x 是左孩子的情況 RBTreeNode w x.parent.right; // 兄弟節(jié)點(diǎn) // 情況1兄弟是紅色 if (w.color RED) { w.color BLACK; x.parent.color RED; leftRotate(x.parent); w x.parent.right; // 更新兄弟節(jié)點(diǎn) } // 情況2兄弟是黑色且兄弟的兩個(gè)孩子都是黑色 if (w.left.color BLACK w.right.color BLACK) { w.color RED; x x.parent; // 矛盾上移 } else { // 情況3兄弟是黑色兄弟的左孩子紅右孩子黑 if (w.right.color BLACK) { w.left.color BLACK; w.color RED; rightRotate(w); w x.parent.right; } // 情況4兄弟是黑色兄弟的右孩子紅 w.color x.parent.color; x.parent.color BLACK; w.right.color BLACK; leftRotate(x.parent); x root; // 修復(fù)完成強(qiáng)制退出循環(huán) } } else { // 對(duì)稱情況x 是右孩子 RBTreeNode w x.parent.left; if (w.color RED) { w.color BLACK; x.parent.color RED; rightRotate(x.parent); w x.parent.left; } if (w.right.color BLACK w.left.color BLACK) { w.color RED; x x.parent; } else { if (w.left.color BLACK) { w.right.color BLACK; w.color RED; leftRotate(w); w x.parent.left; } w.color x.parent.color; x.parent.color BLACK; w.left.color BLACK; rightRotate(x.parent); x root; } } } x.color BLACK; // 最后無(wú)論x原本是什么顏色都將其設(shè)為黑色。 }關(guān)鍵點(diǎn)解析循環(huán)條件while (x ! root x.color BLACK)。如果x是根或者x是紅色循環(huán)結(jié)束。紅色節(jié)點(diǎn)可以直接染黑補(bǔ)足黑色。對(duì)稱處理代碼完全對(duì)稱地處理了x是左孩子和右孩子的情況這是紅黑樹(shù)操作的標(biāo)準(zhǔn)模式。情況之間的轉(zhuǎn)換代碼的邏輯流清晰地體現(xiàn)了情況之間的轉(zhuǎn)換關(guān)系。情況1轉(zhuǎn)換為情況2/3/4情況3轉(zhuǎn)換為情況4情況2可能使x上移進(jìn)入下一輪循環(huán)情況4直接修復(fù)完畢。最后的染色循環(huán)結(jié)束后無(wú)論因何退出都執(zhí)行x.color BLACK。如果x是因變?yōu)榧t色而退出此操作將其變黑補(bǔ)上缺失的黑色如果x是根此操作保證根節(jié)點(diǎn)為黑。6. 從理論到實(shí)踐調(diào)試、驗(yàn)證與常見(jiàn)陷阱實(shí)現(xiàn)代碼只是第一步能正確運(yùn)行和驗(yàn)證才是關(guān)鍵。紅黑樹(shù)的刪除極易因邊界條件處理不當(dāng)而產(chǎn)生難以察覺(jué)的Bug。6.1 如何驗(yàn)證你的實(shí)現(xiàn)是正確的性質(zhì)檢查編寫一個(gè)checkProperties()方法遍歷整棵樹(shù)暴力驗(yàn)證五大法則根節(jié)點(diǎn)為黑。紅色節(jié)點(diǎn)的子節(jié)點(diǎn)必須為黑。從根到每個(gè)NIL葉子的路徑黑色節(jié)點(diǎn)數(shù)相同。 在每次插入/刪除操作后都調(diào)用此方法是快速定位違規(guī)操作的最有效手段。中序遍歷紅黑樹(shù)首先是BST其中序遍歷結(jié)果必須是一個(gè)嚴(yán)格的遞增序列。這能保證基本搜索結(jié)構(gòu)的正確性。隨機(jī)測(cè)試生成大量隨機(jī)數(shù)進(jìn)行插入和刪除并混合進(jìn)行性質(zhì)檢查。這是暴露并發(fā)問(wèn)題和邊界條件的最粗暴有效的方法。public boolean checkProperties() { if (root NIL) return true; if (root.color RED) { System.err.println(Violation: Root is red.); return false; } // 檢查紅色節(jié)點(diǎn)不相鄰 if (!checkRedBlack(root)) return false; // 檢查黑高一致 int blackHeight -1; return checkBlackHeight(root, 0, blackHeight); } private boolean checkRedBlack(RBTreeNode node) { if (node NIL) return true; if (node.color RED) { if (node.left.color RED || node.right.color RED) { System.err.println(Violation: Double red at node node.key); return false; } } return checkRedBlack(node.left) checkRedBlack(node.right); } private boolean checkBlackHeight(RBTreeNode node, int currentHeight, int refHeight) { if (node NIL) { if (refHeight -1) refHeight currentHeight; else if (currentHeight ! refHeight) { System.err.println(Violation: Different black height.); return false; } return true; } if (node.color BLACK) currentHeight; return checkBlackHeight(node.left, currentHeight, refHeight) checkBlackHeight(node.right, currentHeight, refHeight); }6.2 實(shí)戰(zhàn)中極易踩中的坑NIL節(jié)點(diǎn)的處理這是最大的坑。必須確保所有葉子指針都指向同一個(gè)全局的、黑色的NIL哨兵節(jié)點(diǎn)而不是null。在比較顏色、訪問(wèn)父節(jié)點(diǎn)時(shí)NIL節(jié)點(diǎn)必須被正確處理。在上述代碼中w.left.color BLACK這樣的判斷當(dāng)w.left是NIL時(shí)其顏色屬性為BLACK判斷是安全的。指針更新的順序在transplant和旋轉(zhuǎn)操作中父指針和孩子指針的更新順序至關(guān)重要。錯(cuò)誤的順序可能導(dǎo)致樹(shù)中產(chǎn)生環(huán)或指針丟失。一個(gè)黃金法則是先處理被提升節(jié)點(diǎn)v與其新父親的關(guān)系再處理原父親u的父親與新孩子的關(guān)系最后處理u的子樹(shù)關(guān)系。“雙重黑色”的理解x可能是一個(gè)真實(shí)的黑色節(jié)點(diǎn)也可能是NIL視為黑。在修復(fù)循環(huán)中我們將其統(tǒng)稱為“黑色”。deleteFixUp開(kāi)始時(shí)x.color BLACK這個(gè)條件就涵蓋了NIL的情況。情況二的“上移”在情況二中x x.parent之后新的x可能是紅色。此時(shí)循環(huán)條件x.color BLACK不成立循環(huán)退出然后在循環(huán)外x.color BLACK將其染黑完成修復(fù)。這個(gè)細(xì)節(jié)很容易在手動(dòng)演算時(shí)忽略。對(duì)稱代碼的編寫錯(cuò)誤左右旋和左右孩子指針在對(duì)稱情況中極易寫反。建議先徹底理解并穩(wěn)定實(shí)現(xiàn)一邊如x是左孩子然后通過(guò)嚴(yán)格的“鏡像”規(guī)則來(lái)編寫另一邊并輔以大量的測(cè)試。紅黑樹(shù)的刪除實(shí)現(xiàn)是對(duì)程序員耐心和邏輯嚴(yán)謹(jǐn)性的一次絕佳鍛煉。它沒(méi)有捷徑唯有通過(guò)反復(fù)畫圖、代碼演練和測(cè)試才能將那些情況內(nèi)化為直覺(jué)。當(dāng)你能夠不參考任何資料在白板上清晰地畫出刪除修復(fù)的四種情況轉(zhuǎn)換圖時(shí)你對(duì)數(shù)據(jù)結(jié)構(gòu)和算法的理解就已經(jīng)超越了絕大多數(shù)人。這份深刻的理解不僅在面試中是無(wú)往不利的利器在日后設(shè)計(jì)復(fù)雜系統(tǒng)、進(jìn)行性能調(diào)優(yōu)時(shí)這種平衡與權(quán)衡的思想也會(huì)讓你受益匪淺。 紅黑樹(shù)刪除操作詳解：從核心原理到Java實(shí)現(xiàn)
1. 紅黑樹(shù)刪除為什么它比插入更讓人“頭大”如果你已經(jīng)啃過(guò)紅黑樹(shù)的插入操作并且覺(jué)得那些左旋右旋、顏色翻轉(zhuǎn)的規(guī)則雖然繁瑣但還能理清那么恭喜你即將迎來(lái)真正的“硬骨頭”——?jiǎng)h除。在數(shù)據(jù)結(jié)構(gòu)與算法的世界里紅黑樹(shù)的刪除操作以其復(fù)雜的場(chǎng)景分支和精妙的修復(fù)邏輯長(zhǎng)期穩(wěn)坐“面試八股文難點(diǎn)”和“實(shí)際工程調(diào)試噩夢(mèng)”的寶座。很多朋友在學(xué)完插入后面對(duì)刪除那一長(zhǎng)串的case分析直接選擇了“戰(zhàn)略放棄”或者只記結(jié)論不問(wèn)緣由。但今天我想帶你換個(gè)角度不是去死記硬背那五六種情況而是嘗試?yán)斫馄浔澈蟮暮诵拿芘c設(shè)計(jì)哲學(xué)。刪除之所以復(fù)雜根本原因在于它要維護(hù)的平衡性約束比插入更多、更脆弱。插入一個(gè)新節(jié)點(diǎn)最壞情況是破壞“紅節(jié)點(diǎn)不能相鄰”和“根節(jié)點(diǎn)為黑”兩條規(guī)則通過(guò)有限的旋轉(zhuǎn)和變色就能修復(fù)。而刪除一個(gè)節(jié)點(diǎn)尤其是刪除一個(gè)黑色節(jié)點(diǎn)會(huì)直接導(dǎo)致它所在的路徑上“黑色節(jié)點(diǎn)數(shù)量”黑高減少這會(huì)動(dòng)搖紅黑樹(shù)五大核心法則的根基。修復(fù)過(guò)程本質(zhì)上是在不引入新破壞的前提下將這份“缺失的黑色”巧妙地轉(zhuǎn)移或抵消掉。我們即將用Java實(shí)現(xiàn)的就是這套精巧的“外科手術(shù)”過(guò)程。我會(huì)把重點(diǎn)放在“為什么需要這么做”的邏輯推導(dǎo)上而不僅僅是“怎么做”的步驟羅列。當(dāng)你理解了每個(gè)旋轉(zhuǎn)和變色操作背后的意圖那些看似繁雜的case就會(huì)變得清晰而有條理。2. 重溫紅黑樹(shù)為刪除操作奠定認(rèn)知基礎(chǔ)在動(dòng)刀之前我們必須對(duì)“病人”有清晰的了解。紅黑樹(shù)不是一顆普通的二叉搜索樹(shù)BST它是帶著嚴(yán)格平衡約束的BST。這些約束就是我們修復(fù)操作的“憲法”。2.1 五大核心法則再審視節(jié)點(diǎn)非黑即紅每個(gè)節(jié)點(diǎn)要么是紅色要么是黑色。根節(jié)點(diǎn)為黑樹(shù)的根節(jié)點(diǎn)必須是黑色。葉子節(jié)點(diǎn)NIL為黑所有葉子節(jié)點(diǎn)指為空的、不存儲(chǔ)數(shù)據(jù)的節(jié)點(diǎn)通常用NIL表示都是黑色。紅色不相鄰不能有兩個(gè)連續(xù)的紅色節(jié)點(diǎn)。即一個(gè)紅色節(jié)點(diǎn)的父節(jié)點(diǎn)和子節(jié)點(diǎn)都不能是紅色。黑高一致從任意一個(gè)節(jié)點(diǎn)到其所有后代葉子節(jié)點(diǎn)NIL的路徑上包含的黑色節(jié)點(diǎn)數(shù)量必須相同。這個(gè)數(shù)量稱為該節(jié)點(diǎn)的“黑高”。刪除操作最大的挑戰(zhàn)正是來(lái)自于對(duì)法則5的維護(hù)。當(dāng)我們刪除一個(gè)黑色節(jié)點(diǎn)時(shí)從根節(jié)點(diǎn)到某些葉子節(jié)點(diǎn)的路徑上就少了一個(gè)黑色節(jié)點(diǎn)導(dǎo)致黑高不一致樹(shù)就失去了平衡。2.2 二叉搜索樹(shù)的刪除邏輯所有故事的起點(diǎn)紅黑樹(shù)的刪除建立在BST刪除的基礎(chǔ)上。BST刪除一個(gè)節(jié)點(diǎn)有三種基本情況這是我們所有后續(xù)復(fù)雜修復(fù)的起點(diǎn)必須爛熟于心情況A刪除葉子節(jié)點(diǎn)或僅有一個(gè)子節(jié)點(diǎn)的節(jié)點(diǎn)。這是最簡(jiǎn)單的情況。如果它是葉子節(jié)點(diǎn)直接將其父節(jié)點(diǎn)對(duì)應(yīng)的指針置為NIL。如果它有一個(gè)子節(jié)點(diǎn)則用這個(gè)子節(jié)點(diǎn)“頂替”它的位置連接到它的父節(jié)點(diǎn)上。情況B刪除有兩個(gè)子節(jié)點(diǎn)的節(jié)點(diǎn)。這種情況不能直接刪除否則會(huì)破壞樹(shù)的結(jié)構(gòu)。標(biāo)準(zhǔn)的做法是找到它的中序遍歷后繼節(jié)點(diǎn)即右子樹(shù)中的最小節(jié)點(diǎn)或者中序遍歷前驅(qū)節(jié)點(diǎn)即左子樹(shù)中的最大節(jié)點(diǎn)。用這個(gè)后繼或前驅(qū)節(jié)點(diǎn)的值覆蓋要?jiǎng)h除的節(jié)點(diǎn)值然后問(wèn)題轉(zhuǎn)化為刪除那個(gè)后繼或前驅(qū)節(jié)點(diǎn)。關(guān)鍵在于這個(gè)后繼節(jié)點(diǎn)最多只有一個(gè)右子節(jié)點(diǎn)因?yàn)樗亲钚≈颠@就將問(wèn)題簡(jiǎn)化為了情況A。在紅黑樹(shù)的語(yǔ)境下我們真正從結(jié)構(gòu)上移除的節(jié)點(diǎn)記為removedNode只會(huì)是情況A中的節(jié)點(diǎn)即至多有一個(gè)非NIL子節(jié)點(diǎn)。而后續(xù)所有的修復(fù)工作都是圍繞著這個(gè)被移除節(jié)點(diǎn)的位置和顏色展開(kāi)的。3. 刪除情景框架與核心變量定義讓我們開(kāi)始構(gòu)建刪除的框架。在Java中我們首先定義節(jié)點(diǎn)類并引入一個(gè)關(guān)鍵的“哨兵”NIL節(jié)點(diǎn)它代表所有空的葉子節(jié)點(diǎn)顏色為黑。class RBTreeNode { int key; RBTreeNode left, right, parent; boolean color; // 我們用 true 表示 RED, false 表示 BLACK // 構(gòu)造函數(shù)等... static final RBTreeNode NIL new RBTreeNode(0); // 哨兵節(jié)點(diǎn) static { NIL.color BLACK; } }刪除的主入口方法如下public void delete(int key) { RBTreeNode node search(root, key); if (node NIL) return; // 節(jié)點(diǎn)不存在 deleteNode(node); }核心的deleteNode方法其邏輯與BST刪除一致但需要記錄關(guān)鍵信息以供修復(fù)private void deleteNode(RBTreeNode z) { RBTreeNode y z; // y 指向最終要被從樹(shù)中“結(jié)構(gòu)移除”的節(jié)點(diǎn) RBTreeNode x; // x 指向可能頂替 y 位置的節(jié)點(diǎn)也是后續(xù)修復(fù)的起點(diǎn) boolean yOriginalColor y.color; // 情況1 2z 至多有一個(gè)非NIL子節(jié)點(diǎn) if (z.left NIL) { x z.right; transplant(z, z.right); } else if (z.right NIL) { x z.left; transplant(z, z.left); } else { // 情況3z 有兩個(gè)子節(jié)點(diǎn) y minimum(z.right); // 找到后繼節(jié)點(diǎn) yOriginalColor y.color; x y.right; // 后繼節(jié)點(diǎn)的右子節(jié)點(diǎn)可能是NIL if (y.parent z) { // 特殊情況后繼節(jié)點(diǎn)y就是z的右孩子 x.parent y; // 重要確保x的父指針正確即使x是NIL } else { // 一般情況y在z的右子樹(shù)中但不是直接右孩子 transplant(y, y.right); y.right z.right; y.right.parent y; } // 用y替換z transplant(z, y); y.left z.left; y.left.parent y; y.color z.color; // 繼承z的顏色這是關(guān)鍵。 } // 如果被移除的原始節(jié)點(diǎn)y是黑色的則可能破壞紅黑樹(shù)性質(zhì) if (yOriginalColor BLACK) { deleteFixUp(x); } }這里有幾個(gè)至關(guān)重要的變量理解它們是你理清后續(xù)所有情況的關(guān)鍵z: 最初要?jiǎng)h除的目標(biāo)節(jié)點(diǎn)。y: 最終從樹(shù)結(jié)構(gòu)中被移除的節(jié)點(diǎn)。在情況A中y就是z在情況B中y是z的后繼節(jié)點(diǎn)。我們修復(fù)操作所關(guān)注的“被刪除節(jié)點(diǎn)”指的是這個(gè)y。yOriginalColor: 節(jié)點(diǎn)y在被移除前的顏色。只有yOriginalColor為BLACK時(shí)才需要進(jìn)行修復(fù)。因?yàn)閯h除紅色節(jié)點(diǎn)不影響任何路徑的黑高。x: 頂替y原來(lái)位置的節(jié)點(diǎn)。可能是y的唯一子節(jié)點(diǎn)也可能是NIL。x被提升到了y原來(lái)的位置x的父節(jié)點(diǎn)就是原來(lái)y的父節(jié)點(diǎn)。修復(fù)過(guò)程將從x節(jié)點(diǎn)開(kāi)始向上進(jìn)行。transplant(u, v): 一個(gè)輔助操作用子樹(shù)v替換子樹(shù)u僅處理父指針的關(guān)聯(lián)。核心洞見(jiàn)刪除修復(fù)deleteFixUp(x)的核心任務(wù)就是解決“因?yàn)閯h除了一個(gè)黑色節(jié)點(diǎn)y導(dǎo)致經(jīng)過(guò)x的路徑黑高少1”的問(wèn)題。x節(jié)點(diǎn)承載了這份“黑色缺失”修復(fù)過(guò)程就是圍繞x展開(kāi)的。4. 刪除修復(fù)的終極邏輯圍繞X的兄弟做文章現(xiàn)在進(jìn)入最核心的部分deleteFixUp(x)。此時(shí)x可能是紅也可能是黑或NIL視為黑。如果x是紅色我們直接把它染成黑色就能立刻補(bǔ)上缺失的黑色問(wèn)題解決。所以所有復(fù)雜情況都發(fā)生在x是黑色的時(shí)候。修復(fù)過(guò)程是一個(gè)從x開(kāi)始向上迭代的循環(huán)。循環(huán)的目標(biāo)是將額外的“黑色”向上推送直到遇到一個(gè)紅色節(jié)點(diǎn)將其變黑或者推到根節(jié)點(diǎn)循環(huán)結(jié)束。這個(gè)“額外的黑色”是一個(gè)邏輯概念意味著x節(jié)點(diǎn)現(xiàn)在“承載”了雙重黑色double black或紅黑色破壞了顏色規(guī)則我們需要通過(guò)調(diào)整來(lái)消除它。循環(huán)中的每一步我們都在審視x、x的兄弟節(jié)點(diǎn)w、以及它們的父親p之間的關(guān)系。根據(jù)w的顏色和w子樹(shù)的顏色分布我們分為四大主情況。請(qǐng)務(wù)必記住我們的視角始終固定在當(dāng)前節(jié)點(diǎn)x上。4.1 情況一X的兄弟W是紅色場(chǎng)景x是黑色其兄弟w是紅色。此時(shí)根據(jù)紅黑樹(shù)性質(zhì)父親p和w的兩個(gè)子節(jié)點(diǎn)必然都是黑色。目標(biāo)此情況的目標(biāo)是將問(wèn)題轉(zhuǎn)化為兄弟w是黑色的情況情況二、三、四因?yàn)楹罄m(xù)的操作都需要基于黑色兄弟進(jìn)行。操作將兄弟w染黑。將父親p染紅。對(duì)p進(jìn)行左旋如果x是左孩子或右旋如果x是右孩子。旋轉(zhuǎn)后x有了一個(gè)新的兄弟節(jié)點(diǎn)原w的某個(gè)黑孩子這個(gè)新兄弟變成了黑色。問(wèn)題進(jìn)入情況二、三或四。為什么這樣做旋轉(zhuǎn)操作改變了局部結(jié)構(gòu)但保持了子樹(shù)的黑高不變。將w變黑、p變紅是為了在旋轉(zhuǎn)后x所在路徑的黑高不增加而w所在路徑通過(guò)結(jié)構(gòu)調(diào)整為后續(xù)的“借調(diào)”操作做準(zhǔn)備。// 代碼片段示意 if (w.color RED) { w.color BLACK; x.parent.color RED; if (x x.parent.left) { leftRotate(x.parent); w x.parent.right; // 更新兄弟節(jié)點(diǎn)為新的黑色兄弟 } else { // 對(duì)稱操作... } }4.2 情況二X的兄弟W是黑色且W的兩個(gè)子節(jié)點(diǎn)都是黑色場(chǎng)景x是黑色兄弟w是黑色并且w的兩個(gè)孩子都是黑色或NIL。目標(biāo)此時(shí)無(wú)法從兄弟子樹(shù)“借”一個(gè)紅色節(jié)點(diǎn)或黑色節(jié)點(diǎn)過(guò)來(lái)。策略是將x和w各自“拿走”一層黑色將這層黑色“上交給”父親p。這樣x的“雙重黑色”問(wèn)題解決了但父親p可能變成了新的“雙重黑色”或“紅黑”節(jié)點(diǎn)。操作將兄弟w染紅。將x指向其父親p。結(jié)果原來(lái)x的“雙重黑色”被消除但p節(jié)點(diǎn)如果原來(lái)是紅色現(xiàn)在變成了“紅黑”實(shí)際表現(xiàn)為紅色但邏輯上多一層黑循環(huán)結(jié)束如果p原來(lái)是黑色現(xiàn)在則變成了新的“雙重黑色”節(jié)點(diǎn)循環(huán)繼續(xù)以p作為新的x向上處理。為什么這樣做這是一種“收縮”策略。通過(guò)將兄弟一側(cè)也減少一層黑色w由黑變紅使得以p為根的子樹(shù)整體黑高減1從而讓p來(lái)承擔(dān)黑高不平衡的問(wèn)題將矛盾上移。4.3 情況三X的兄弟W是黑色W的近侄子為紅遠(yuǎn)侄子為黑場(chǎng)景假設(shè)x是左孩子。其兄弟w是黑色w的左孩子x的“近侄子”是紅色w的右孩子x的“遠(yuǎn)侄子”是黑色。對(duì)稱情況同理。目標(biāo)此情況是一個(gè)過(guò)渡狀態(tài)目標(biāo)是通過(guò)旋轉(zhuǎn)將其轉(zhuǎn)換為情況四因?yàn)榍闆r四有更直接的修復(fù)方案。操作將w的近侄子紅色染黑。將w自身染紅。對(duì)w進(jìn)行右旋以近侄子為軸。旋轉(zhuǎn)后x的兄弟節(jié)點(diǎn)更新為原近侄子現(xiàn)在已變黑且新兄弟的遠(yuǎn)侄子變成了紅色。這完美符合情況四的條件。為什么這樣做這個(gè)操作像是一個(gè)“預(yù)備動(dòng)作”。它通過(guò)一次旋轉(zhuǎn)和變色在兄弟子樹(shù)內(nèi)部重新布局創(chuàng)造出一個(gè)紅色節(jié)點(diǎn)位于“遠(yuǎn)侄子”位置的條件為情況四的“終極借調(diào)”搭建好了舞臺(tái)。4.4 情況四X的兄弟W是黑色且W的遠(yuǎn)侄子為紅色場(chǎng)景x是左孩子其兄弟w是黑色且w的右孩子遠(yuǎn)侄子是紅色。這是修復(fù)操作的“終結(jié)者”情況。目標(biāo)通過(guò)一次旋轉(zhuǎn)和變色直接從兄弟子樹(shù)“借調(diào)”一個(gè)黑色節(jié)點(diǎn)過(guò)來(lái)徹底解決x的“雙重黑色”問(wèn)題并保持所有紅黑樹(shù)性質(zhì)。操作將兄弟w的顏色設(shè)置為父親p的顏色。將父親p染黑。將w的遠(yuǎn)侄子紅色染黑。對(duì)父親p進(jìn)行左旋。結(jié)果旋轉(zhuǎn)后x的“雙重黑色”被消除因?yàn)槠渌诼窂酵ㄟ^(guò)旋轉(zhuǎn)增加了一個(gè)黑色節(jié)點(diǎn)p。同時(shí)原來(lái)w的遠(yuǎn)侄子被染黑保證了該側(cè)路徑黑高不變。所有性質(zhì)恢復(fù)修復(fù)完成循環(huán)可以終止。為什么這樣做這是最精妙的一步。旋轉(zhuǎn)操作將父親p拉下來(lái)變成了x所在子樹(shù)的新根黑色相當(dāng)于給x的路徑“補(bǔ)”了一個(gè)黑色節(jié)點(diǎn)。而將w提升為新的局部根并繼承原p的顏色保證了整棵樹(shù)的結(jié)構(gòu)和顏色規(guī)則得以完美維持。5. Java完整實(shí)現(xiàn)與逐行解析理解了上述四種核心情況我們就可以拼裝出完整的deleteFixUp方法。以下是完整的Java實(shí)現(xiàn)包含了對(duì)稱情況的處理。private void deleteFixUp(RBTreeNode x) { while (x ! root x.color BLACK) { if (x x.parent.left) { // x 是左孩子的情況 RBTreeNode w x.parent.right; // 兄弟節(jié)點(diǎn) // 情況1兄弟是紅色 if (w.color RED) { w.color BLACK; x.parent.color RED; leftRotate(x.parent); w x.parent.right; // 更新兄弟節(jié)點(diǎn) } // 情況2兄弟是黑色且兄弟的兩個(gè)孩子都是黑色 if (w.left.color BLACK w.right.color BLACK) { w.color RED; x x.parent; // 矛盾上移 } else { // 情況3兄弟是黑色兄弟的左孩子紅右孩子黑 if (w.right.color BLACK) { w.left.color BLACK; w.color RED; rightRotate(w); w x.parent.right; } // 情況4兄弟是黑色兄弟的右孩子紅 w.color x.parent.color; x.parent.color BLACK; w.right.color BLACK; leftRotate(x.parent); x root; // 修復(fù)完成強(qiáng)制退出循環(huán) } } else { // 對(duì)稱情況x 是右孩子 RBTreeNode w x.parent.left; if (w.color RED) { w.color BLACK; x.parent.color RED; rightRotate(x.parent); w x.parent.left; } if (w.right.color BLACK w.left.color BLACK) { w.color RED; x x.parent; } else { if (w.left.color BLACK) { w.right.color BLACK; w.color RED; leftRotate(w); w x.parent.left; } w.color x.parent.color; x.parent.color BLACK; w.left.color BLACK; rightRotate(x.parent); x root; } } } x.color BLACK; // 最后無(wú)論x原本是什么顏色都將其設(shè)為黑色。 }關(guān)鍵點(diǎn)解析循環(huán)條件while (x ! root x.color BLACK)。如果x是根或者x是紅色循環(huán)結(jié)束。紅色節(jié)點(diǎn)可以直接染黑補(bǔ)足黑色。對(duì)稱處理代碼完全對(duì)稱地處理了x是左孩子和右孩子的情況這是紅黑樹(shù)操作的標(biāo)準(zhǔn)模式。情況之間的轉(zhuǎn)換代碼的邏輯流清晰地體現(xiàn)了情況之間的轉(zhuǎn)換關(guān)系。情況1轉(zhuǎn)換為情況2/3/4情況3轉(zhuǎn)換為情況4情況2可能使x上移進(jìn)入下一輪循環(huán)情況4直接修復(fù)完畢。最后的染色循環(huán)結(jié)束后無(wú)論因何退出都執(zhí)行x.color BLACK。如果x是因變?yōu)榧t色而退出此操作將其變黑補(bǔ)上缺失的黑色如果x是根此操作保證根節(jié)點(diǎn)為黑。6. 從理論到實(shí)踐調(diào)試、驗(yàn)證與常見(jiàn)陷阱實(shí)現(xiàn)代碼只是第一步能正確運(yùn)行和驗(yàn)證才是關(guān)鍵。紅黑樹(shù)的刪除極易因邊界條件處理不當(dāng)而產(chǎn)生難以察覺(jué)的Bug。6.1 如何驗(yàn)證你的實(shí)現(xiàn)是正確的性質(zhì)檢查編寫一個(gè)checkProperties()方法遍歷整棵樹(shù)暴力驗(yàn)證五大法則根節(jié)點(diǎn)為黑。紅色節(jié)點(diǎn)的子節(jié)點(diǎn)必須為黑。從根到每個(gè)NIL葉子的路徑黑色節(jié)點(diǎn)數(shù)相同。 在每次插入/刪除操作后都調(diào)用此方法是快速定位違規(guī)操作的最有效手段。中序遍歷紅黑樹(shù)首先是BST其中序遍歷結(jié)果必須是一個(gè)嚴(yán)格的遞增序列。這能保證基本搜索結(jié)構(gòu)的正確性。隨機(jī)測(cè)試生成大量隨機(jī)數(shù)進(jìn)行插入和刪除并混合進(jìn)行性質(zhì)檢查。這是暴露并發(fā)問(wèn)題和邊界條件的最粗暴有效的方法。public boolean checkProperties() { if (root NIL) return true; if (root.color RED) { System.err.println(Violation: Root is red.); return false; } // 檢查紅色節(jié)點(diǎn)不相鄰 if (!checkRedBlack(root)) return false; // 檢查黑高一致 int blackHeight -1; return checkBlackHeight(root, 0, blackHeight); } private boolean checkRedBlack(RBTreeNode node) { if (node NIL) return true; if (node.color RED) { if (node.left.color RED || node.right.color RED) { System.err.println(Violation: Double red at node node.key); return false; } } return checkRedBlack(node.left) checkRedBlack(node.right); } private boolean checkBlackHeight(RBTreeNode node, int currentHeight, int refHeight) { if (node NIL) { if (refHeight -1) refHeight currentHeight; else if (currentHeight ! refHeight) { System.err.println(Violation: Different black height.); return false; } return true; } if (node.color BLACK) currentHeight; return checkBlackHeight(node.left, currentHeight, refHeight) checkBlackHeight(node.right, currentHeight, refHeight); }6.2 實(shí)戰(zhàn)中極易踩中的坑NIL節(jié)點(diǎn)的處理這是最大的坑。必須確保所有葉子指針都指向同一個(gè)全局的、黑色的NIL哨兵節(jié)點(diǎn)而不是null。在比較顏色、訪問(wèn)父節(jié)點(diǎn)時(shí)NIL節(jié)點(diǎn)必須被正確處理。在上述代碼中w.left.color BLACK這樣的判斷當(dāng)w.left是NIL時(shí)其顏色屬性為BLACK判斷是安全的。指針更新的順序在transplant和旋轉(zhuǎn)操作中父指針和孩子指針的更新順序至關(guān)重要。錯(cuò)誤的順序可能導(dǎo)致樹(shù)中產(chǎn)生環(huán)或指針丟失。一個(gè)黃金法則是先處理被提升節(jié)點(diǎn)v與其新父親的關(guān)系再處理原父親u的父親與新孩子的關(guān)系最后處理u的子樹(shù)關(guān)系。“雙重黑色”的理解x可能是一個(gè)真實(shí)的黑色節(jié)點(diǎn)也可能是NIL視為黑。在修復(fù)循環(huán)中我們將其統(tǒng)稱為“黑色”。deleteFixUp開(kāi)始時(shí)x.color BLACK這個(gè)條件就涵蓋了NIL的情況。情況二的“上移”在情況二中x x.parent之后新的x可能是紅色。此時(shí)循環(huán)條件x.color BLACK不成立循環(huán)退出然后在循環(huán)外x.color BLACK將其染黑完成修復(fù)。這個(gè)細(xì)節(jié)很容易在手動(dòng)演算時(shí)忽略。對(duì)稱代碼的編寫錯(cuò)誤左右旋和左右孩子指針在對(duì)稱情況中極易寫反。建議先徹底理解并穩(wěn)定實(shí)現(xiàn)一邊如x是左孩子然后通過(guò)嚴(yán)格的“鏡像”規(guī)則來(lái)編寫另一邊并輔以大量的測(cè)試。紅黑樹(shù)的刪除實(shí)現(xiàn)是對(duì)程序員耐心和邏輯嚴(yán)謹(jǐn)性的一次絕佳鍛煉。它沒(méi)有捷徑唯有通過(guò)反復(fù)畫圖、代碼演練和測(cè)試才能將那些情況內(nèi)化為直覺(jué)。當(dāng)你能夠不參考任何資料在白板上清晰地畫出刪除修復(fù)的四種情況轉(zhuǎn)換圖時(shí)你對(duì)數(shù)據(jù)結(jié)構(gòu)和算法的理解就已經(jīng)超越了絕大多數(shù)人。這份深刻的理解不僅在面試中是無(wú)往不利的利器在日后設(shè)計(jì)復(fù)雜系統(tǒng)、進(jìn)行性能調(diào)優(yōu)時(shí)這種平衡與權(quán)衡的思想也會(huì)讓你受益匪淺。