紅黑樹的插入與刪除操作手冊一、紅黑樹概述

紅黑樹是一種自平衡的二叉搜索樹，通過維護(hù)節(jié)點(diǎn)的顏色屬性（紅色或黑色）和特定的性質(zhì)，確保樹的高度保持在平衡狀態(tài)，從而實(shí)現(xiàn)高效的插入和刪除操作。

（一）紅黑樹的基本性質(zhì)

1.每個節(jié)點(diǎn)要么是紅色，要么是黑色。

2.根節(jié)點(diǎn)是黑色。

3.每個葉子節(jié)點(diǎn)（NIL節(jié)點(diǎn)）是黑色。

4.如果一個節(jié)點(diǎn)是紅色的，則它的兩個子節(jié)點(diǎn)都是黑色的（從每個葉子到根的所有路徑上不能有兩個連續(xù)的紅色節(jié)點(diǎn)）。

5.從任一節(jié)點(diǎn)到其每個葉子的所有簡單路徑都包含相同數(shù)目的黑色節(jié)點(diǎn)。

二、紅黑樹的插入操作

（一）插入步驟

1.標(biāo)準(zhǔn)BST插入：按照二叉搜索樹的規(guī)則將節(jié)點(diǎn)插入到樹中。

2.更新顏色：新插入的節(jié)點(diǎn)默認(rèn)為紅色。

3.修復(fù)紅黑樹性質(zhì)：通過旋轉(zhuǎn)和重新著色操作，確保樹滿足紅黑樹的性質(zhì)。

（二）修復(fù)操作

當(dāng)插入紅色節(jié)點(diǎn)后，可能破壞紅黑樹的性質(zhì)，需要通過以下步驟修復(fù)：

(1)情況1：叔叔節(jié)點(diǎn)是紅色

-將父節(jié)點(diǎn)和叔叔節(jié)點(diǎn)變?yōu)楹谏娓腹?jié)點(diǎn)變?yōu)榧t色。

-將當(dāng)前節(jié)點(diǎn)移動到祖父節(jié)點(diǎn)，繼續(xù)修復(fù)。

(2)情況2：叔叔節(jié)點(diǎn)是黑色

-根據(jù)當(dāng)前節(jié)點(diǎn)與父節(jié)點(diǎn)的位置，分為左左、左右、右右、右左四種情況，通過旋轉(zhuǎn)和重新著色修復(fù)。

示例：插入節(jié)點(diǎn)15（假設(shè)樹已平衡），插入后路徑為10（黑）→15（紅），叔叔節(jié)點(diǎn)為空（黑色），屬于左右情況，需進(jìn)行左旋和著色修復(fù)。

三、紅黑樹的刪除操作

（一）刪除步驟

1.標(biāo)準(zhǔn)BST刪除：刪除節(jié)點(diǎn)時，考慮三種情況：

-刪除葉子節(jié)點(diǎn)。

-刪除一個子節(jié)點(diǎn)為葉子的節(jié)點(diǎn)。

-刪除兩個子節(jié)點(diǎn)都存在的節(jié)點(diǎn)（用后繼替換）。

2.修復(fù)顏色：刪除操作可能導(dǎo)致紅黑樹性質(zhì)被破壞，需通過旋轉(zhuǎn)和重新著色修復(fù)。

（二）修復(fù)操作

刪除操作可能導(dǎo)致兩種性質(zhì)被破壞：

(1)黑高度不匹配

-刪除黑色節(jié)點(diǎn)后，可能導(dǎo)致路徑上的黑高度減少，需通過“紅黑樹剪切”修復(fù)。

(2)紅節(jié)點(diǎn)相鄰

-如果刪除后相鄰節(jié)點(diǎn)為紅色，需通過旋轉(zhuǎn)和著色修復(fù)。

示例：刪除節(jié)點(diǎn)10（黑），導(dǎo)致其子路徑黑高度減少，需通過將子節(jié)點(diǎn)變?yōu)榧t色并旋轉(zhuǎn)修復(fù)。

四、總結(jié)

紅黑樹的插入和刪除操作通過維護(hù)樹的平衡和性質(zhì)，確保操作的時間復(fù)雜度為O(logn)。修復(fù)操作需根據(jù)具體情況進(jìn)行旋轉(zhuǎn)和著色，但總體流程清晰且高效。掌握這些操作對于理解和應(yīng)用紅黑樹至關(guān)重要。

二、紅黑樹的插入操作（續(xù)）

（二）修復(fù)操作（詳細(xì)步驟）

在插入節(jié)點(diǎn)后，若紅黑樹的性質(zhì)被破壞，需通過以下旋轉(zhuǎn)和著色操作進(jìn)行修復(fù)。修復(fù)過程通常從靠近根節(jié)點(diǎn)的最低違規(guī)路徑開始，并向上傳播至根節(jié)點(diǎn)。

1.叔叔節(jié)點(diǎn)是紅色（情況1）

當(dāng)插入紅色節(jié)點(diǎn)后，若其父節(jié)點(diǎn)為紅色且叔叔節(jié)點(diǎn)也為紅色，說明其祖父節(jié)點(diǎn)必然為黑色（否則已違反性質(zhì)4）。此時，可以通過以下步驟修復(fù)：

(1)著色操作

-將當(dāng)前節(jié)點(diǎn)、父節(jié)點(diǎn)和叔叔節(jié)點(diǎn)均設(shè)置為黑色。

-將祖父節(jié)點(diǎn)設(shè)置為紅色。

(2)重新定位當(dāng)前節(jié)點(diǎn)

-將當(dāng)前節(jié)點(diǎn)移動到祖父節(jié)點(diǎn)，因?yàn)樽娓腹?jié)點(diǎn)可能成為新的違規(guī)節(jié)點(diǎn)。

-繼續(xù)向上檢查，直到根節(jié)點(diǎn)或不再違反性質(zhì)為止。

2.叔叔節(jié)點(diǎn)是黑色（情況2）

當(dāng)叔叔節(jié)點(diǎn)為黑色時，需根據(jù)當(dāng)前節(jié)點(diǎn)與父節(jié)點(diǎn)的相對位置進(jìn)行不同操作。分為四種子情況：

(1)左左情況（LL）

當(dāng)前節(jié)點(diǎn)是紅色，父節(jié)點(diǎn)是紅色，叔叔節(jié)點(diǎn)是黑色，且當(dāng)前節(jié)點(diǎn)位于父節(jié)點(diǎn)的左側(cè)。

修復(fù)步驟：

(a)右旋祖父節(jié)點(diǎn)

-以祖父節(jié)點(diǎn)為軸，進(jìn)行右旋操作。

(b)重新著色

-將父節(jié)點(diǎn)設(shè)置為黑色。

-將祖父節(jié)點(diǎn)設(shè)置為紅色。

(2)左右情況（LR）

當(dāng)前節(jié)點(diǎn)是紅色，父節(jié)點(diǎn)是紅色，叔叔節(jié)點(diǎn)是黑色，且當(dāng)前節(jié)點(diǎn)位于父節(jié)點(diǎn)的右側(cè)。

修復(fù)步驟：

(a)左旋父節(jié)點(diǎn)

-以父節(jié)點(diǎn)為軸，進(jìn)行左旋操作。

(b)進(jìn)入左左情況

-旋轉(zhuǎn)后，當(dāng)前節(jié)點(diǎn)與父節(jié)點(diǎn)的關(guān)系變?yōu)樽笞笄闆r，可應(yīng)用LL情況的修復(fù)步驟。

(c)右旋祖父節(jié)點(diǎn)

-以祖父節(jié)點(diǎn)為軸，進(jìn)行右旋操作。

(d)重新著色

-將父節(jié)點(diǎn)設(shè)置為黑色。

-將祖父節(jié)點(diǎn)設(shè)置為紅色。

(3)右右情況（RR）

當(dāng)前節(jié)點(diǎn)是紅色，父節(jié)點(diǎn)是紅色，叔叔節(jié)點(diǎn)是黑色，且當(dāng)前節(jié)點(diǎn)位于父節(jié)點(diǎn)的右側(cè)。

修復(fù)步驟：

(a)左旋祖父節(jié)點(diǎn)

-以祖父節(jié)點(diǎn)為軸，進(jìn)行左旋操作。

(b)重新著色

-將父節(jié)點(diǎn)設(shè)置為黑色。

-將祖父節(jié)點(diǎn)設(shè)置為紅色。

(4)右左情況（RL）

當(dāng)前節(jié)點(diǎn)是紅色，父節(jié)點(diǎn)是紅色，叔叔節(jié)點(diǎn)是黑色，且當(dāng)前節(jié)點(diǎn)位于父節(jié)點(diǎn)的左側(cè)。

修復(fù)步驟：

(a)右旋父節(jié)點(diǎn)

-以父節(jié)點(diǎn)為軸，進(jìn)行右旋操作。

(b)進(jìn)入右右情況

-旋轉(zhuǎn)后，當(dāng)前節(jié)點(diǎn)與父節(jié)點(diǎn)的關(guān)系變?yōu)橛矣仪闆r，可應(yīng)用RR情況的修復(fù)步驟。

(c)左旋祖父節(jié)點(diǎn)

-以祖父節(jié)點(diǎn)為軸，進(jìn)行左旋操作。

(d)重新著色

-將父節(jié)點(diǎn)設(shè)置為黑色。

-將祖父節(jié)點(diǎn)設(shè)置為紅色。

示例：假設(shè)插入節(jié)點(diǎn)15，樹結(jié)構(gòu)如下：

10(B)

/\

5(B)20(R)

/\

17(R)25(B)

插入15后，路徑為10→20→17，若20和17均為紅色，則需修復(fù)：

-20和17為紅色，10為黑色，叔叔節(jié)點(diǎn)為17（黑色），屬于左右情況（LR）。

-先左旋20，再右旋10，最后重新著色。

（三）插入后的最終狀態(tài)

修復(fù)完成后，紅黑樹的性質(zhì)應(yīng)完全恢復(fù)：

1.所有節(jié)點(diǎn)為紅色或黑色。

2.根節(jié)點(diǎn)為黑色。

3.葉子節(jié)點(diǎn)為黑色。

4.紅色節(jié)點(diǎn)的子節(jié)點(diǎn)為黑色。

5.從任一節(jié)點(diǎn)到葉子的所有路徑包含相同數(shù)目的黑色節(jié)點(diǎn)。

三、紅黑樹的刪除操作（續(xù)）

（一）刪除步驟（詳細(xì)情況）

紅黑樹的刪除操作分為三種情況，需根據(jù)目標(biāo)節(jié)點(diǎn)的子節(jié)點(diǎn)數(shù)量進(jìn)行處理。

1.刪除葉子節(jié)點(diǎn)

若刪除的節(jié)點(diǎn)為葉子節(jié)點(diǎn)（無子節(jié)點(diǎn)），直接將其替換為NIL節(jié)點(diǎn)（黑色），可能引發(fā)黑高度問題，需后續(xù)修復(fù)。

2.刪除一個子節(jié)點(diǎn)的節(jié)點(diǎn)

若刪除的節(jié)點(diǎn)有一個子節(jié)點(diǎn)，用其子節(jié)點(diǎn)替換該節(jié)點(diǎn)，并刪除原子節(jié)點(diǎn)。此操作可能破壞性質(zhì)5（黑高度），需修復(fù)。

3.刪除兩個子節(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)，可轉(zhuǎn)化為前兩種情況處理。

（二）修復(fù)操作（詳細(xì)步驟）

刪除操作可能導(dǎo)致兩種主要問題：黑高度不匹配和紅節(jié)點(diǎn)相鄰。

1.黑高度不匹配（修復(fù)方法：紅黑樹剪切）

當(dāng)刪除黑色節(jié)點(diǎn)后，部分路徑的黑高度減少，需通過以下步驟修復(fù)：

(1)引入“紅色鏈接”

-在黑高度減少的路徑上，將NIL節(jié)點(diǎn)臨時設(shè)為紅色，形成“紅色鏈接”。

-紅色鏈接相當(dāng)于將黑高度“借出”，使路徑黑高度恢復(fù)一致。

(2)處理紅色鏈接

根據(jù)紅色鏈接的位置，分為以下情況：

(a)紅色鏈接在祖父節(jié)點(diǎn)

-若紅色鏈接位于祖父節(jié)點(diǎn)，直接刪除紅色鏈接（即恢復(fù)NIL節(jié)點(diǎn)為黑色），問題解決。

(b)紅色鏈接在父節(jié)點(diǎn)或當(dāng)前節(jié)點(diǎn)

-通過旋轉(zhuǎn)和著色操作，將紅色鏈接向上傳播或消除。

-具體操作類似插入修復(fù)中的旋轉(zhuǎn)和著色步驟。

示例：刪除節(jié)點(diǎn)10（黑），路徑為10→15→20，若15為紅色，需引入紅色鏈接（將20設(shè)為紅色），然后處理紅色鏈接。

2.紅節(jié)點(diǎn)相鄰（修復(fù)方法：旋轉(zhuǎn)和著色）

若刪除操作導(dǎo)致相鄰節(jié)點(diǎn)為紅色，需通過旋轉(zhuǎn)和著色修復(fù)：

(1)左旋或右旋操作

-根據(jù)相鄰節(jié)點(diǎn)的位置，選擇合適的旋轉(zhuǎn)操作，使紅節(jié)點(diǎn)分離。

(2)重新著色

-將部分節(jié)點(diǎn)設(shè)置為黑色，避免連續(xù)紅色節(jié)點(diǎn)。

示例：刪除節(jié)點(diǎn)10（黑），路徑為10→15→20（紅），若15變?yōu)榧t色，可左旋15，使20變?yōu)楹谏?，并重新著色?/p>

（三）刪除后的最終狀態(tài)

修復(fù)完成后，紅黑樹的性質(zhì)應(yīng)完全恢復(fù)，且滿足以下條件：

1.所有節(jié)點(diǎn)為紅色或黑色。

2.根節(jié)點(diǎn)為黑色。

3.葉子節(jié)點(diǎn)為黑色。

4.紅色節(jié)點(diǎn)的子節(jié)點(diǎn)為黑色。

5.從任一節(jié)點(diǎn)到葉子的所有路徑包含相同數(shù)目的黑色節(jié)點(diǎn)。

四、紅黑樹操作的應(yīng)用場景

紅黑樹的高效性和平衡性使其適用于以下場景：

(1)數(shù)據(jù)庫索引

-紅黑樹用于實(shí)現(xiàn)B樹索引，確保查詢效率。

(2)緩存淘汰算法

-LRU（最近最少使用）緩存可基于紅黑樹實(shí)現(xiàn)。

(3)編譯器符號表

-用于快速插入、刪除和查找標(biāo)識符。

(4)通用搜索樹

-在需要動態(tài)數(shù)據(jù)集合的場景中廣泛應(yīng)用。

一、紅黑樹概述

紅黑樹是一種自平衡的二叉搜索樹，通過維護(hù)節(jié)點(diǎn)的顏色屬性（紅色或黑色）和特定的性質(zhì)，確保樹的高度保持在平衡狀態(tài)，從而實(shí)現(xiàn)高效的插入和刪除操作。

（一）紅黑樹的基本性質(zhì)

1.每個節(jié)點(diǎn)要么是紅色，要么是黑色。

2.根節(jié)點(diǎn)是黑色。

3.每個葉子節(jié)點(diǎn)（NIL節(jié)點(diǎn)）是黑色。

4.如果一個節(jié)點(diǎn)是紅色的，則它的兩個子節(jié)點(diǎn)都是黑色的（從每個葉子到根的所有路徑上不能有兩個連續(xù)的紅色節(jié)點(diǎn)）。

5.從任一節(jié)點(diǎn)到其每個葉子的所有簡單路徑都包含相同數(shù)目的黑色節(jié)點(diǎn)。

二、紅黑樹的插入操作

（一）插入步驟

1.標(biāo)準(zhǔn)BST插入：按照二叉搜索樹的規(guī)則將節(jié)點(diǎn)插入到樹中。

2.更新顏色：新插入的節(jié)點(diǎn)默認(rèn)為紅色。

3.修復(fù)紅黑樹性質(zhì)：通過旋轉(zhuǎn)和重新著色操作，確保樹滿足紅黑樹的性質(zhì)。

（二）修復(fù)操作

當(dāng)插入紅色節(jié)點(diǎn)后，可能破壞紅黑樹的性質(zhì)，需要通過以下步驟修復(fù)：

(1)情況1：叔叔節(jié)點(diǎn)是紅色

-將父節(jié)點(diǎn)和叔叔節(jié)點(diǎn)變?yōu)楹谏?，祖父?jié)點(diǎn)變?yōu)榧t色。

-將當(dāng)前節(jié)點(diǎn)移動到祖父節(jié)點(diǎn)，繼續(xù)修復(fù)。

(2)情況2：叔叔節(jié)點(diǎn)是黑色

-根據(jù)當(dāng)前節(jié)點(diǎn)與父節(jié)點(diǎn)的位置，分為左左、左右、右右、右左四種情況，通過旋轉(zhuǎn)和重新著色修復(fù)。

示例：插入節(jié)點(diǎn)15（假設(shè)樹已平衡），插入后路徑為10（黑）→15（紅），叔叔節(jié)點(diǎn)為空（黑色），屬于左右情況，需進(jìn)行左旋和著色修復(fù)。

三、紅黑樹的刪除操作

（一）刪除步驟

1.標(biāo)準(zhǔn)BST刪除：刪除節(jié)點(diǎn)時，考慮三種情況：

-刪除葉子節(jié)點(diǎn)。

-刪除一個子節(jié)點(diǎn)為葉子的節(jié)點(diǎn)。

-刪除兩個子節(jié)點(diǎn)都存在的節(jié)點(diǎn)（用后繼替換）。

2.修復(fù)顏色：刪除操作可能導(dǎo)致紅黑樹性質(zhì)被破壞，需通過旋轉(zhuǎn)和重新著色修復(fù)。

（二）修復(fù)操作

刪除操作可能導(dǎo)致兩種性質(zhì)被破壞：

(1)黑高度不匹配

-刪除黑色節(jié)點(diǎn)后，可能導(dǎo)致路徑上的黑高度減少，需通過“紅黑樹剪切”修復(fù)。

(2)紅節(jié)點(diǎn)相鄰

-如果刪除后相鄰節(jié)點(diǎn)為紅色，需通過旋轉(zhuǎn)和著色修復(fù)。

示例：刪除節(jié)點(diǎn)10（黑），導(dǎo)致其子路徑黑高度減少，需通過將子節(jié)點(diǎn)變?yōu)榧t色并旋轉(zhuǎn)修復(fù)。

四、總結(jié)

紅黑樹的插入和刪除操作通過維護(hù)樹的平衡和性質(zhì)，確保操作的時間復(fù)雜度為O(logn)。修復(fù)操作需根據(jù)具體情況進(jìn)行旋轉(zhuǎn)和著色，但總體流程清晰且高效。掌握這些操作對于理解和應(yīng)用紅黑樹至關(guān)重要。

二、紅黑樹的插入操作（續(xù)）

（二）修復(fù)操作（詳細(xì)步驟）

在插入節(jié)點(diǎn)后，若紅黑樹的性質(zhì)被破壞，需通過以下旋轉(zhuǎn)和著色操作進(jìn)行修復(fù)。修復(fù)過程通常從靠近根節(jié)點(diǎn)的最低違規(guī)路徑開始，并向上傳播至根節(jié)點(diǎn)。

1.叔叔節(jié)點(diǎn)是紅色（情況1）

當(dāng)插入紅色節(jié)點(diǎn)后，若其父節(jié)點(diǎn)為紅色且叔叔節(jié)點(diǎn)也為紅色，說明其祖父節(jié)點(diǎn)必然為黑色（否則已違反性質(zhì)4）。此時，可以通過以下步驟修復(fù)：

(1)著色操作

-將當(dāng)前節(jié)點(diǎn)、父節(jié)點(diǎn)和叔叔節(jié)點(diǎn)均設(shè)置為黑色。

-將祖父節(jié)點(diǎn)設(shè)置為紅色。

(2)重新定位當(dāng)前節(jié)點(diǎn)

-將當(dāng)前節(jié)點(diǎn)移動到祖父節(jié)點(diǎn)，因?yàn)樽娓腹?jié)點(diǎn)可能成為新的違規(guī)節(jié)點(diǎn)。

-繼續(xù)向上檢查，直到根節(jié)點(diǎn)或不再違反性質(zhì)為止。

2.叔叔節(jié)點(diǎn)是黑色（情況2）

當(dāng)叔叔節(jié)點(diǎn)為黑色時，需根據(jù)當(dāng)前節(jié)點(diǎn)與父節(jié)點(diǎn)的相對位置進(jìn)行不同操作。分為四種子情況：

(1)左左情況（LL）

當(dāng)前節(jié)點(diǎn)是紅色，父節(jié)點(diǎn)是紅色，叔叔節(jié)點(diǎn)是黑色，且當(dāng)前節(jié)點(diǎn)位于父節(jié)點(diǎn)的左側(cè)。

修復(fù)步驟：

(a)右旋祖父節(jié)點(diǎn)

-以祖父節(jié)點(diǎn)為軸，進(jìn)行右旋操作。

(b)重新著色

-將父節(jié)點(diǎn)設(shè)置為黑色。

-將祖父節(jié)點(diǎn)設(shè)置為紅色。

(2)左右情況（LR）

當(dāng)前節(jié)點(diǎn)是紅色，父節(jié)點(diǎn)是紅色，叔叔節(jié)點(diǎn)是黑色，且當(dāng)前節(jié)點(diǎn)位于父節(jié)點(diǎn)的右側(cè)。

修復(fù)步驟：

(a)左旋父節(jié)點(diǎn)

-以父節(jié)點(diǎn)為軸，進(jìn)行左旋操作。

(b)進(jìn)入左左情況

-旋轉(zhuǎn)后，當(dāng)前節(jié)點(diǎn)與父節(jié)點(diǎn)的關(guān)系變?yōu)樽笞笄闆r，可應(yīng)用LL情況的修復(fù)步驟。

(c)右旋祖父節(jié)點(diǎn)

-以祖父節(jié)點(diǎn)為軸，進(jìn)行右旋操作。

(d)重新著色

-將父節(jié)點(diǎn)設(shè)置為黑色。

-將祖父節(jié)點(diǎn)設(shè)置為紅色。

(3)右右情況（RR）

當(dāng)前節(jié)點(diǎn)是紅色，父節(jié)點(diǎn)是紅色，叔叔節(jié)點(diǎn)是黑色，且當(dāng)前節(jié)點(diǎn)位于父節(jié)點(diǎn)的右側(cè)。

修復(fù)步驟：

(a)左旋祖父節(jié)點(diǎn)

-以祖父節(jié)點(diǎn)為軸，進(jìn)行左旋操作。

(b)重新著色

-將父節(jié)點(diǎn)設(shè)置為黑色。

-將祖父節(jié)點(diǎn)設(shè)置為紅色。

(4)右左情況（RL）

當(dāng)前節(jié)點(diǎn)是紅色，父節(jié)點(diǎn)是紅色，叔叔節(jié)點(diǎn)是黑色，且當(dāng)前節(jié)點(diǎn)位于父節(jié)點(diǎn)的左側(cè)。

修復(fù)步驟：

(a)右旋父節(jié)點(diǎn)

-以父節(jié)點(diǎn)為軸，進(jìn)行右旋操作。

(b)進(jìn)入右右情況

-旋轉(zhuǎn)后，當(dāng)前節(jié)點(diǎn)與父節(jié)點(diǎn)的關(guān)系變?yōu)橛矣仪闆r，可應(yīng)用RR情況的修復(fù)步驟。

(c)左旋祖父節(jié)點(diǎn)

-以祖父節(jié)點(diǎn)為軸，進(jìn)行左旋操作。

(d)重新著色

-將父節(jié)點(diǎn)設(shè)置為黑色。

-將祖父節(jié)點(diǎn)設(shè)置為紅色。

示例：假設(shè)插入節(jié)點(diǎn)15，樹結(jié)構(gòu)如下：

10(B)

/\

5(B)20(R)

/\

17(R)25(B)

插入15后，路徑為10→20→17，若20和17均為紅色，則需修復(fù)：

-20和17為紅色，10為黑色，叔叔節(jié)點(diǎn)為17（黑色），屬于左右情況（LR）。

-先左旋20，再右旋10，最后重新著色。

（三）插入后的最終狀態(tài)

修復(fù)完成后，紅黑樹的性質(zhì)應(yīng)完全恢復(fù)：

1.所有節(jié)點(diǎn)為紅色或黑色。

2.根節(jié)點(diǎn)為黑色。

3.葉子節(jié)點(diǎn)為黑色。

4.紅色節(jié)點(diǎn)的子節(jié)點(diǎn)為黑色。

5.從任一節(jié)點(diǎn)到葉子的所有路徑包含相同數(shù)目的黑色節(jié)點(diǎn)。

三、紅黑樹的刪除操作（續(xù)）

（一）刪除步驟（詳細(xì)情況）

紅黑樹的刪除操作分為三種情況，需根據(jù)目標(biāo)節(jié)點(diǎn)的子節(jié)點(diǎn)數(shù)量進(jìn)行處理。

1.刪除葉子節(jié)點(diǎn)

若刪除的節(jié)點(diǎn)為葉子節(jié)點(diǎn)（無子節(jié)點(diǎn)），直接將其替換為NIL節(jié)點(diǎn)（黑色），可能引發(fā)黑高度問題，需后續(xù)修復(fù)。

2.刪除一個子節(jié)點(diǎn)的節(jié)點(diǎn)

若刪除的節(jié)點(diǎn)有一個子節(jié)點(diǎn)，用其子節(jié)點(diǎn)替換該節(jié)點(diǎn)，并刪除原子節(jié)點(diǎn)。此操作可能破壞性質(zhì)5（黑高度），需修復(fù)。

3.刪除兩個子節(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)，可轉(zhuǎn)化為前兩種情況處理。

（二）修復(fù)操作（詳細(xì)步驟）

刪除操作可能導(dǎo)致兩種主要問題：黑高度不匹配和紅節(jié)點(diǎn)相鄰。

1.黑高度不匹配（修復(fù)方法：紅黑樹剪切）

當(dāng)刪除黑色節(jié)點(diǎn)后，部分路徑的黑高度減少，需通過以下步驟修復(fù)：

(1)引入“紅色鏈接”

-在黑高度減少的路徑上，將NIL節(jié)點(diǎn)臨時設(shè)為紅色，形成“紅色鏈接”。

-紅色鏈接相當(dāng)于將黑高度“借出”，使路徑黑高度恢復(fù)一致