紅黑樹的旋轉(zhuǎn)操作示例演示一、紅黑樹旋轉(zhuǎn)操作概述

紅黑樹是一種自平衡二叉查找樹，其通過旋轉(zhuǎn)和重新著色操作來維護(hù)平衡。旋轉(zhuǎn)操作主要分為左旋和右旋兩種，用于調(diào)整樹的結(jié)構(gòu)，確保紅黑樹的性質(zhì)得以保持。本演示將通過具體步驟展示紅黑樹的旋轉(zhuǎn)操作過程，包括左旋和右旋的應(yīng)用場景及實(shí)現(xiàn)方法。

二、左旋操作

左旋操作用于將紅黑樹中某個(gè)節(jié)點(diǎn)的右子節(jié)點(diǎn)提升為父節(jié)點(diǎn)，同時(shí)調(diào)整相關(guān)節(jié)點(diǎn)的位置和顏色，以維持紅黑樹的性質(zhì)。

（一）左旋操作適用場景

1.紅黑樹中存在“右右”情況（即父節(jié)點(diǎn)為紅色，其右子節(jié)點(diǎn)也為紅色，且右子節(jié)點(diǎn)的右子節(jié)點(diǎn)為黑色）。

2.通過左旋可以修復(fù)紅黑樹的平衡，避免連續(xù)紅色節(jié)點(diǎn)的出現(xiàn)。

（二）左旋操作步驟（以節(jié)點(diǎn)X為根節(jié)點(diǎn)進(jìn)行操作）

1.將X的右子節(jié)點(diǎn)Y設(shè)為新的根節(jié)點(diǎn)。

2.將X作為Y的左子節(jié)點(diǎn)。

3.如果Y有左子節(jié)點(diǎn)Z，將Z設(shè)為X的右子節(jié)點(diǎn)。

4.調(diào)整節(jié)點(diǎn)的顏色：

-若X原本為紅色，Y設(shè)為黑色，且X的右子節(jié)點(diǎn)（若存在）設(shè)為黑色。

-若X原本為黑色，則不改變顏色。

（三）左旋操作示例

假設(shè)樹結(jié)構(gòu)如下：

X(紅)

/\

T1Y(紅)

/\

T2Z(黑)

左旋后結(jié)構(gòu)變?yōu)椋?/p>

Y(黑)

/\

X(紅)T2

/\

T1Z(黑)

三、右旋操作

右旋操作與左旋操作相反，用于將紅黑樹中某個(gè)節(jié)點(diǎn)的左子節(jié)點(diǎn)提升為父節(jié)點(diǎn)，同時(shí)調(diào)整相關(guān)節(jié)點(diǎn)的位置和顏色。

（一）右旋操作適用場景

1.紅黑樹中存在“左左”情況（即父節(jié)點(diǎn)為紅色，其左子節(jié)點(diǎn)也為紅色，且左子節(jié)點(diǎn)的左子節(jié)點(diǎn)為黑色）。

2.通過右旋可以修復(fù)紅黑樹的平衡，避免連續(xù)紅色節(jié)點(diǎn)的出現(xiàn)。

（二）右旋操作步驟（以節(jié)點(diǎn)X為根節(jié)點(diǎn)進(jìn)行操作）

1.將X的左子節(jié)點(diǎn)Y設(shè)為新的根節(jié)點(diǎn)。

2.將X作為Y的右子節(jié)點(diǎn)。

3.如果Y有右子節(jié)點(diǎn)Z，將Z設(shè)為X的左子節(jié)點(diǎn)。

4.調(diào)整節(jié)點(diǎn)的顏色：

-若X原本為紅色，Y設(shè)為黑色，且X的左子節(jié)點(diǎn)（若存在）設(shè)為黑色。

-若X原本為黑色，則不改變顏色。

（三）右旋操作示例

假設(shè)樹結(jié)構(gòu)如下：

X(紅)

/\

Y(紅)T2

/\

T1Z(黑)

右旋后結(jié)構(gòu)變?yōu)椋?/p>

Y(黑)

/\

T1X(紅)

/\

ZT2

四、旋轉(zhuǎn)操作的應(yīng)用

旋轉(zhuǎn)操作是紅黑樹維護(hù)平衡的核心機(jī)制，實(shí)際應(yīng)用中通常結(jié)合左右旋和著色操作共同使用。以下是一個(gè)綜合示例：

（一）初始樹結(jié)構(gòu)（存在“右右”情況）

15(紅)

/\

10(黑)17(紅)

/\

13(黑)20(紅)

/\

1214

（二）第一步：對(duì)節(jié)點(diǎn)17進(jìn)行左旋

15(紅)

/\

10(黑)13(紅)

/\

1217(黑)

/\

1420(紅)

（三）第二步：對(duì)節(jié)點(diǎn)13進(jìn)行右旋

15(紅)

/\

10(黑)17(紅)

/\

1213(黑)

/\

1420(紅)

（四）調(diào)整顏色并驗(yàn)證平衡

-將節(jié)點(diǎn)15設(shè)為黑色，節(jié)點(diǎn)13設(shè)為紅色，節(jié)點(diǎn)17設(shè)為黑色。

-最終樹結(jié)構(gòu)滿足紅黑樹性質(zhì)，無連續(xù)紅色節(jié)點(diǎn)。

四、旋轉(zhuǎn)操作的應(yīng)用（續(xù)）

（一）綜合旋轉(zhuǎn)與著色示例詳解

在實(shí)際的紅黑樹插入或刪除操作中，很少僅通過一次旋轉(zhuǎn)就能完成平衡調(diào)整。通常需要結(jié)合多次旋轉(zhuǎn)（左旋、右旋）以及重新著色來修復(fù)因插入或刪除節(jié)點(diǎn)而破壞的紅黑樹性質(zhì)。以下通過一個(gè)更詳細(xì)的插入場景，演示旋轉(zhuǎn)與著色的綜合應(yīng)用。

場景：向紅黑樹中插入節(jié)點(diǎn)值為9的節(jié)點(diǎn)。假設(shè)初始部分樹結(jié)構(gòu)如下（為簡化，忽略部分黑色高度指示，假設(shè)根節(jié)點(diǎn)為黑色）：

10(黑)

/\

5(黑)15(黑)

\/\

71217

/\\

3620

插入節(jié)點(diǎn)9后，在節(jié)點(diǎn)5的右子樹中插入，導(dǎo)致節(jié)點(diǎn)10和15之間出現(xiàn)連續(xù)紅色節(jié)點(diǎn)（10紅色，15紅色，其父節(jié)點(diǎn)5為黑色），違反了紅黑樹的性質(zhì)4（沒有兩個(gè)相鄰的紅色節(jié)點(diǎn)）。此時(shí)需要通過旋轉(zhuǎn)和著色進(jìn)行修復(fù)。

步驟1：首次旋轉(zhuǎn)與著色

1.問題識(shí)別：節(jié)點(diǎn)15是節(jié)點(diǎn)10的右子節(jié)點(diǎn)，且節(jié)點(diǎn)10和15都為紅色，其父節(jié)點(diǎn)5為黑色。這是一個(gè)典型的“右右”情況（相對(duì)于節(jié)點(diǎn)10）。

2.執(zhí)行左旋：對(duì)節(jié)點(diǎn)10執(zhí)行左旋。左旋以節(jié)點(diǎn)10為中心。

節(jié)點(diǎn)15成為新的父節(jié)點(diǎn)，節(jié)點(diǎn)10成為節(jié)點(diǎn)15的左子節(jié)點(diǎn)。

原節(jié)點(diǎn)10的右子節(jié)點(diǎn)（即節(jié)點(diǎn)17）成為節(jié)點(diǎn)15的右子節(jié)點(diǎn)。

原樹結(jié)構(gòu)：

```

10(紅)

/\

5(黑)15(紅)

\/\

71217

/\\

3620

```

左旋后結(jié)構(gòu)：

```

15(黑)

/\

10(紅)17

/\

5(黑)12

\/\

7620

/\

39

```

（注意：節(jié)點(diǎn)9是新插入的，暫時(shí)未在圖中顯式表示其位置，假設(shè)它在節(jié)點(diǎn)7的右子樹中，即7->9）。

3.執(zhí)行著色：對(duì)新樹結(jié)構(gòu)執(zhí)行著色。

將節(jié)點(diǎn)15（左旋后的根）設(shè)為黑色。

將節(jié)點(diǎn)10（左旋后成為節(jié)點(diǎn)15的左子節(jié)點(diǎn)）設(shè)為紅色。

這樣，節(jié)點(diǎn)15（黑）-節(jié)點(diǎn)10（紅）這一對(duì)父子節(jié)點(diǎn)不再違反性質(zhì)4。

4.結(jié)果檢查：檢查節(jié)點(diǎn)10（紅）的父節(jié)點(diǎn)（節(jié)點(diǎn)5）是否為黑色。如果是，則僅此步驟完成。如果不是，則需要進(jìn)入下一步。

步驟2：處理父節(jié)點(diǎn)為紅色的情況

1.問題識(shí)別（假設(shè)）：在左旋和著色后，發(fā)現(xiàn)節(jié)點(diǎn)10（紅）的父節(jié)點(diǎn)5（黑）也是紅色。此時(shí)，節(jié)點(diǎn)5、節(jié)點(diǎn)10和節(jié)點(diǎn)15（其父節(jié)點(diǎn)是更高層的節(jié)點(diǎn)，假設(shè)為20，且為黑色）構(gòu)成了一個(gè)“右紅-左紅”模式（沿從節(jié)點(diǎn)10到節(jié)點(diǎn)20的路徑看，先是節(jié)點(diǎn)10紅色，然后是節(jié)點(diǎn)5黑色，再然后是節(jié)點(diǎn)20黑色，但節(jié)點(diǎn)10和節(jié)點(diǎn)5相鄰）。這同樣違反了性質(zhì)4。

2.執(zhí)行右旋：對(duì)節(jié)點(diǎn)5的父節(jié)點(diǎn)（假設(shè)為節(jié)點(diǎn)20）執(zhí)行右旋。右旋以節(jié)點(diǎn)20為中心。

節(jié)點(diǎn)5成為新的父節(jié)點(diǎn)，節(jié)點(diǎn)20成為節(jié)點(diǎn)5的右子節(jié)點(diǎn)。

原節(jié)點(diǎn)20的右子節(jié)點(diǎn)（假設(shè)為節(jié)點(diǎn)25，如果不存在則為nil）成為節(jié)點(diǎn)5的右子節(jié)點(diǎn)。

原樹結(jié)構(gòu)（簡化表示）：

```

20(黑)

/\

15(黑)25

/\

10(紅)17

/\

5(紅)12

/\

79

```

右旋后結(jié)構(gòu)：

```

20(黑)

/\

5(紅)15(黑)

\/\

101217

/\

79

```

（節(jié)點(diǎn)20的其他子節(jié)點(diǎn)如25保持不變或移除）。節(jié)點(diǎn)10、15、20之間的相對(duì)位置和顏色關(guān)系得到調(diào)整。

3.執(zhí)行著色：對(duì)新樹結(jié)構(gòu)執(zhí)行著色。

將節(jié)點(diǎn)20（右旋后的根）設(shè)為黑色。

將節(jié)點(diǎn)5（右旋后成為節(jié)點(diǎn)20的左子節(jié)點(diǎn)）設(shè)為黑色。

將節(jié)點(diǎn)15（原為黑色，現(xiàn)在成為節(jié)點(diǎn)5的右子節(jié)點(diǎn)）設(shè)為紅色。

這樣，節(jié)點(diǎn)20（黑）-節(jié)點(diǎn)5（黑）-節(jié)點(diǎn)10（紅）這一路徑不再相鄰紅色節(jié)點(diǎn)。

4.結(jié)果檢查：再次檢查紅黑樹性質(zhì)。此時(shí)，節(jié)點(diǎn)5（黑）的子節(jié)點(diǎn)是節(jié)點(diǎn)10（紅）和節(jié)點(diǎn)15（黑），滿足性質(zhì)4。節(jié)點(diǎn)20（黑）的子節(jié)點(diǎn)是節(jié)點(diǎn)5（黑），也滿足性質(zhì)4。如果此時(shí)樹中不存在其他違反性質(zhì)4的路徑，則平衡修復(fù)完成。

步驟3：處理節(jié)點(diǎn)9的插入位置

1.插入節(jié)點(diǎn)9：將新插入的節(jié)點(diǎn)9最終放置在樹中的正確位置。根據(jù)紅黑樹的插入規(guī)則，節(jié)點(diǎn)總是被插入為葉節(jié)點(diǎn)，并初始著色為紅色。假設(shè)最終插入位置在節(jié)點(diǎn)7的右子樹。

2.最終樹結(jié)構(gòu)（示例）：

```

20(黑)

/\

5(黑)15(黑)

\/\

101217

/\

79

/\

36

```

3.驗(yàn)證性質(zhì)：檢查樹是否滿足所有紅黑樹性質(zhì)：

性質(zhì)1：每個(gè)節(jié)點(diǎn)要么是紅色，要么是黑色。（滿足，根節(jié)點(diǎn)20為黑色，葉節(jié)點(diǎn)為黑色，內(nèi)部節(jié)點(diǎn)交替著色）。

性質(zhì)2：根節(jié)點(diǎn)是黑色。（滿足）。

性質(zhì)3：每個(gè)葉子節(jié)點(diǎn)（NIL節(jié)點(diǎn)）是黑色。（NIL節(jié)點(diǎn)視為黑色，滿足）。

性質(zhì)4：如果節(jié)點(diǎn)是紅色的，則它的兩個(gè)子節(jié)點(diǎn)都是黑色的。（檢查所有紅色節(jié)點(diǎn)：節(jié)點(diǎn)10是紅色，其子節(jié)點(diǎn)7和9均為黑色；節(jié)點(diǎn)15是紅色，其子節(jié)點(diǎn)12和17均為黑色。滿足）。

性質(zhì)5：對(duì)于任意節(jié)點(diǎn)，從該節(jié)點(diǎn)到其所有后代葉節(jié)點(diǎn)的簡單路徑上，均包含相同數(shù)目的黑色節(jié)點(diǎn)。（可以驗(yàn)證從任何葉節(jié)點(diǎn)到根的路徑，黑色節(jié)點(diǎn)數(shù)量均為2，滿足）。

總結(jié)：通過上述步驟，我們演示了在紅黑樹插入新節(jié)點(diǎn)后，如何通過一系列的左旋、右旋和著色操作，逐步修復(fù)因插入而破壞的紅黑樹平衡性質(zhì)，最終確保樹保持平衡狀態(tài)。這個(gè)過程可能涉及多級(jí)節(jié)點(diǎn)，需要根據(jù)具體情況進(jìn)行判斷和操作。

五、旋轉(zhuǎn)操作的注意事項(xiàng)

（一）旋轉(zhuǎn)不改變鍵值的相對(duì)順序

旋轉(zhuǎn)操作僅改變樹的結(jié)構(gòu)，調(diào)整節(jié)點(diǎn)的父子關(guān)系和指向，并不改變節(jié)點(diǎn)所存儲(chǔ)的鍵值或整個(gè)樹中鍵值的相對(duì)排序。因此，旋轉(zhuǎn)后的樹仍然滿足二叉查找樹的關(guān)鍵字性質(zhì)。

（二）旋轉(zhuǎn)影響節(jié)點(diǎn)的高度和黑色高度

旋轉(zhuǎn)會(huì)改變相關(guān)節(jié)點(diǎn)的深度（高度）和黑色高度（從節(jié)點(diǎn)到葉子的路徑上黑色節(jié)點(diǎn)的數(shù)量）。在進(jìn)行旋轉(zhuǎn)和著色操作后，必須重新檢查并確保所有節(jié)點(diǎn)的黑色高度滿足紅黑樹的性質(zhì)5。

（三）旋轉(zhuǎn)與著色的配合是關(guān)鍵

單純的旋轉(zhuǎn)只能局部調(diào)整樹的結(jié)構(gòu)，無法直接修復(fù)連續(xù)紅色節(jié)點(diǎn)的全局問題。必須將旋轉(zhuǎn)與著色操作結(jié)合起來，才能有效維護(hù)紅黑樹的所有性質(zhì)。通常，先通過旋轉(zhuǎn)調(diào)整節(jié)點(diǎn)關(guān)系，再通過著色改變節(jié)點(diǎn)顏色，或者反過來。

（四）旋轉(zhuǎn)操作的遞歸實(shí)現(xiàn)

旋轉(zhuǎn)操作本身相對(duì)簡單，但在紅黑樹的插入和刪除算法中，旋轉(zhuǎn)點(diǎn)可能位于樹的較高層級(jí)。因此，通常采用遞歸方式來實(shí)現(xiàn)旋轉(zhuǎn)操作，簡化代碼邏輯。遞歸旋轉(zhuǎn)時(shí)，需要正確傳遞父節(jié)點(diǎn)指針，以便進(jìn)行著色和進(jìn)一步可能需要的旋轉(zhuǎn)。

六、旋轉(zhuǎn)操作的效率分析

紅黑樹的旋轉(zhuǎn)操作非常高效。每次旋轉(zhuǎn)操作的時(shí)間復(fù)雜度為O(1)，即常數(shù)時(shí)間復(fù)雜度，因?yàn)樗簧婕肮潭〝?shù)量的指針修改和顏色變更。由于紅黑樹的平衡性質(zhì)保證了樹的高度大致為2log(N)，其中N是節(jié)點(diǎn)數(shù)量，因此即使需要進(jìn)行多次旋轉(zhuǎn)操作，總的時(shí)間復(fù)雜度也仍然是O(log(N))。這使得紅黑樹在執(zhí)行插入和刪除操作時(shí)，能夠保持較高的效率。

一、紅黑樹旋轉(zhuǎn)操作概述

紅黑樹是一種自平衡二叉查找樹，其通過旋轉(zhuǎn)和重新著色操作來維護(hù)平衡。旋轉(zhuǎn)操作主要分為左旋和右旋兩種，用于調(diào)整樹的結(jié)構(gòu)，確保紅黑樹的性質(zhì)得以保持。本演示將通過具體步驟展示紅黑樹的旋轉(zhuǎn)操作過程，包括左旋和右旋的應(yīng)用場景及實(shí)現(xiàn)方法。

二、左旋操作

左旋操作用于將紅黑樹中某個(gè)節(jié)點(diǎn)的右子節(jié)點(diǎn)提升為父節(jié)點(diǎn)，同時(shí)調(diào)整相關(guān)節(jié)點(diǎn)的位置和顏色，以維持紅黑樹的性質(zhì)。

（一）左旋操作適用場景

1.紅黑樹中存在“右右”情況（即父節(jié)點(diǎn)為紅色，其右子節(jié)點(diǎn)也為紅色，且右子節(jié)點(diǎn)的右子節(jié)點(diǎn)為黑色）。

2.通過左旋可以修復(fù)紅黑樹的平衡，避免連續(xù)紅色節(jié)點(diǎn)的出現(xiàn)。

（二）左旋操作步驟（以節(jié)點(diǎn)X為根節(jié)點(diǎn)進(jìn)行操作）

1.將X的右子節(jié)點(diǎn)Y設(shè)為新的根節(jié)點(diǎn)。

2.將X作為Y的左子節(jié)點(diǎn)。

3.如果Y有左子節(jié)點(diǎn)Z，將Z設(shè)為X的右子節(jié)點(diǎn)。

4.調(diào)整節(jié)點(diǎn)的顏色：

-若X原本為紅色，Y設(shè)為黑色，且X的右子節(jié)點(diǎn)（若存在）設(shè)為黑色。

-若X原本為黑色，則不改變顏色。

（三）左旋操作示例

假設(shè)樹結(jié)構(gòu)如下：

X(紅)

/\

T1Y(紅)

/\

T2Z(黑)

左旋后結(jié)構(gòu)變?yōu)椋?/p>

Y(黑)

/\

X(紅)T2

/\

T1Z(黑)

三、右旋操作

右旋操作與左旋操作相反，用于將紅黑樹中某個(gè)節(jié)點(diǎn)的左子節(jié)點(diǎn)提升為父節(jié)點(diǎn)，同時(shí)調(diào)整相關(guān)節(jié)點(diǎn)的位置和顏色。

（一）右旋操作適用場景

1.紅黑樹中存在“左左”情況（即父節(jié)點(diǎn)為紅色，其左子節(jié)點(diǎn)也為紅色，且左子節(jié)點(diǎn)的左子節(jié)點(diǎn)為黑色）。

2.通過右旋可以修復(fù)紅黑樹的平衡，避免連續(xù)紅色節(jié)點(diǎn)的出現(xiàn)。

（二）右旋操作步驟（以節(jié)點(diǎn)X為根節(jié)點(diǎn)進(jìn)行操作）

1.將X的左子節(jié)點(diǎn)Y設(shè)為新的根節(jié)點(diǎn)。

2.將X作為Y的右子節(jié)點(diǎn)。

3.如果Y有右子節(jié)點(diǎn)Z，將Z設(shè)為X的左子節(jié)點(diǎn)。

4.調(diào)整節(jié)點(diǎn)的顏色：

-若X原本為紅色，Y設(shè)為黑色，且X的左子節(jié)點(diǎn)（若存在）設(shè)為黑色。

-若X原本為黑色，則不改變顏色。

（三）右旋操作示例

假設(shè)樹結(jié)構(gòu)如下：

X(紅)

/\

Y(紅)T2

/\

T1Z(黑)

右旋后結(jié)構(gòu)變?yōu)椋?/p>

Y(黑)

/\

T1X(紅)

/\

ZT2

四、旋轉(zhuǎn)操作的應(yīng)用

旋轉(zhuǎn)操作是紅黑樹維護(hù)平衡的核心機(jī)制，實(shí)際應(yīng)用中通常結(jié)合左右旋和著色操作共同使用。以下是一個(gè)綜合示例：

（一）初始樹結(jié)構(gòu)（存在“右右”情況）

15(紅)

/\

10(黑)17(紅)

/\

13(黑)20(紅)

/\

1214

（二）第一步：對(duì)節(jié)點(diǎn)17進(jìn)行左旋

15(紅)

/\

10(黑)13(紅)

/\

1217(黑)

/\

1420(紅)

（三）第二步：對(duì)節(jié)點(diǎn)13進(jìn)行右旋

15(紅)

/\

10(黑)17(紅)

/\

1213(黑)

/\

1420(紅)

（四）調(diào)整顏色并驗(yàn)證平衡

-將節(jié)點(diǎn)15設(shè)為黑色，節(jié)點(diǎn)13設(shè)為紅色，節(jié)點(diǎn)17設(shè)為黑色。

-最終樹結(jié)構(gòu)滿足紅黑樹性質(zhì)，無連續(xù)紅色節(jié)點(diǎn)。

四、旋轉(zhuǎn)操作的應(yīng)用（續(xù)）

（一）綜合旋轉(zhuǎn)與著色示例詳解

在實(shí)際的紅黑樹插入或刪除操作中，很少僅通過一次旋轉(zhuǎn)就能完成平衡調(diào)整。通常需要結(jié)合多次旋轉(zhuǎn)（左旋、右旋）以及重新著色來修復(fù)因插入或刪除節(jié)點(diǎn)而破壞的紅黑樹性質(zhì)。以下通過一個(gè)更詳細(xì)的插入場景，演示旋轉(zhuǎn)與著色的綜合應(yīng)用。

場景：向紅黑樹中插入節(jié)點(diǎn)值為9的節(jié)點(diǎn)。假設(shè)初始部分樹結(jié)構(gòu)如下（為簡化，忽略部分黑色高度指示，假設(shè)根節(jié)點(diǎn)為黑色）：

10(黑)

/\

5(黑)15(黑)

\/\

71217

/\\

3620

插入節(jié)點(diǎn)9后，在節(jié)點(diǎn)5的右子樹中插入，導(dǎo)致節(jié)點(diǎn)10和15之間出現(xiàn)連續(xù)紅色節(jié)點(diǎn)（10紅色，15紅色，其父節(jié)點(diǎn)5為黑色），違反了紅黑樹的性質(zhì)4（沒有兩個(gè)相鄰的紅色節(jié)點(diǎn)）。此時(shí)需要通過旋轉(zhuǎn)和著色進(jìn)行修復(fù)。

步驟1：首次旋轉(zhuǎn)與著色

1.問題識(shí)別：節(jié)點(diǎn)15是節(jié)點(diǎn)10的右子節(jié)點(diǎn)，且節(jié)點(diǎn)10和15都為紅色，其父節(jié)點(diǎn)5為黑色。這是一個(gè)典型的“右右”情況（相對(duì)于節(jié)點(diǎn)10）。

2.執(zhí)行左旋：對(duì)節(jié)點(diǎn)10執(zhí)行左旋。左旋以節(jié)點(diǎn)10為中心。

節(jié)點(diǎn)15成為新的父節(jié)點(diǎn)，節(jié)點(diǎn)10成為節(jié)點(diǎn)15的左子節(jié)點(diǎn)。

原節(jié)點(diǎn)10的右子節(jié)點(diǎn)（即節(jié)點(diǎn)17）成為節(jié)點(diǎn)15的右子節(jié)點(diǎn)。

原樹結(jié)構(gòu)：

```

10(紅)

/\

5(黑)15(紅)

\/\

71217

/\\

3620

```

左旋后結(jié)構(gòu)：

```

15(黑)

/\

10(紅)17

/\

5(黑)12

\/\

7620

/\

39

```

（注意：節(jié)點(diǎn)9是新插入的，暫時(shí)未在圖中顯式表示其位置，假設(shè)它在節(jié)點(diǎn)7的右子樹中，即7->9）。

3.執(zhí)行著色：對(duì)新樹結(jié)構(gòu)執(zhí)行著色。

將節(jié)點(diǎn)15（左旋后的根）設(shè)為黑色。

將節(jié)點(diǎn)10（左旋后成為節(jié)點(diǎn)15的左子節(jié)點(diǎn)）設(shè)為紅色。

這樣，節(jié)點(diǎn)15（黑）-節(jié)點(diǎn)10（紅）這一對(duì)父子節(jié)點(diǎn)不再違反性質(zhì)4。

4.結(jié)果檢查：檢查節(jié)點(diǎn)10（紅）的父節(jié)點(diǎn)（節(jié)點(diǎn)5）是否為黑色。如果是，則僅此步驟完成。如果不是，則需要進(jìn)入下一步。

步驟2：處理父節(jié)點(diǎn)為紅色的情況

1.問題識(shí)別（假設(shè)）：在左旋和著色后，發(fā)現(xiàn)節(jié)點(diǎn)10（紅）的父節(jié)點(diǎn)5（黑）也是紅色。此時(shí)，節(jié)點(diǎn)5、節(jié)點(diǎn)10和節(jié)點(diǎn)15（其父節(jié)點(diǎn)是更高層的節(jié)點(diǎn)，假設(shè)為20，且為黑色）構(gòu)成了一個(gè)“右紅-左紅”模式（沿從節(jié)點(diǎn)10到節(jié)點(diǎn)20的路徑看，先是節(jié)點(diǎn)10紅色，然后是節(jié)點(diǎn)5黑色，再然后是節(jié)點(diǎn)20黑色，但節(jié)點(diǎn)10和節(jié)點(diǎn)5相鄰）。這同樣違反了性質(zhì)4。

2.執(zhí)行右旋：對(duì)節(jié)點(diǎn)5的父節(jié)點(diǎn)（假設(shè)為節(jié)點(diǎn)20）執(zhí)行右旋。右旋以節(jié)點(diǎn)20為中心。

節(jié)點(diǎn)5成為新的父節(jié)點(diǎn)，節(jié)點(diǎn)20成為節(jié)點(diǎn)5的右子節(jié)點(diǎn)。

原節(jié)點(diǎn)20的右子節(jié)點(diǎn)（假設(shè)為節(jié)點(diǎn)25，如果不存在則為nil）成為節(jié)點(diǎn)5的右子節(jié)點(diǎn)。

原樹結(jié)構(gòu)（簡化表示）：

```

20(黑)

/\

15(黑)25

/\

10(紅)17

/\

5(紅)12

/\

79

```

右旋后結(jié)構(gòu)：

```

20(黑)

/\

5(紅)15(黑)

\/\

101217

/\

79

```

（節(jié)點(diǎn)20的其他子節(jié)點(diǎn)如25保持不變或移除）。節(jié)點(diǎn)10、15、20之間的相對(duì)位置和顏色關(guān)系得到調(diào)整。

3.執(zhí)行著色：對(duì)新樹結(jié)構(gòu)執(zhí)行著色。

將節(jié)點(diǎn)20（右旋后的根）設(shè)為黑色。

將節(jié)點(diǎn)5（右旋后成為節(jié)點(diǎn)20的左子節(jié)點(diǎn)）設(shè)為黑色。

將節(jié)點(diǎn)15（原為黑色，現(xiàn)在成為節(jié)點(diǎn)5的右子節(jié)點(diǎn)）設(shè)為紅色。

這樣，節(jié)點(diǎn)20（黑）-節(jié)點(diǎn)5（黑）-節(jié)點(diǎn)10（紅）這一路徑不再相鄰紅色節(jié)點(diǎn)。

4.結(jié)果檢查：再次檢查紅黑樹性質(zhì)。此時(shí)，節(jié)點(diǎn)5（黑）的子節(jié)點(diǎn)是節(jié)點(diǎn)10（紅）和節(jié)點(diǎn)15（黑），滿足性質(zhì)4。節(jié)點(diǎn)20（黑）的子節(jié)點(diǎn)是節(jié)點(diǎn)5（黑），也滿足性質(zhì)4。如果此時(shí)樹中不存在其他違反性質(zhì)4的路徑，則平衡修復(fù)完成。

步驟3：處理節(jié)點(diǎn)9的插入位置

1.插入節(jié)點(diǎn)9：將新插入的節(jié)點(diǎn)9最終放置在樹中的正確位置。根據(jù)紅黑樹的插入規(guī)則，節(jié)點(diǎn)總是被插入為葉節(jié)點(diǎn)，并初始著色為紅色。假設(shè)最終插入位置在節(jié)點(diǎn)7的右子樹。

2.最終樹結(jié)構(gòu)（示例）：

```

20(黑)

/\

5(黑)15(黑)

\/\

101217

/\

79

/\

36

```

3.驗(yàn)證性質(zhì)：檢查樹是否滿足所有紅黑樹性質(zhì)：

性質(zhì)1：每個(gè)節(jié)點(diǎn)要么是紅色，要么是黑色。（滿足，根節(jié)點(diǎn)20為黑色，葉節(jié)點(diǎn)為黑色，內(nèi)部節(jié)點(diǎn)交替著色）。

性質(zhì)2：根節(jié)點(diǎn)是黑色。（滿足）。

性質(zhì)3：每個(gè)葉子節(jié)點(diǎn)（NIL節(jié)點(diǎn)）是黑色。（NIL節(jié)點(diǎn)視為黑色，滿足）。

性質(zhì)4：如果節(jié)點(diǎn)是紅色的，則它的兩個(gè)子節(jié)點(diǎn)都是黑色的。（檢