紅黑樹查找與插入操作分析一、紅黑樹概述

紅黑樹是一種自平衡二叉搜索樹，通過維護紅黑屬性來保證樹的高度平衡，從而實現(xiàn)高效的查找、插入和刪除操作。其核心特性包括：

-每個節(jié)點為紅色或黑色

-根節(jié)點為黑色

-紅色節(jié)點的兩個子節(jié)點均為黑色（從任何節(jié)點到其所有后代的外部路徑上黑色節(jié)點數(shù)量相同）

-不允許出現(xiàn)連續(xù)的紅色節(jié)點

-可通過旋轉(zhuǎn)和重新著色操作保持平衡

二、紅黑樹查找操作分析

紅黑樹的查找過程與普通二叉搜索樹的查找類似，但需考慮其平衡特性對查找路徑的影響。

（一）查找步驟

1.從根節(jié)點開始，比較目標鍵值與當前節(jié)點值：

-若相等，查找成功，返回節(jié)點

-若目標鍵值小于當前節(jié)點值，轉(zhuǎn)向左子樹

-若目標鍵值大于當前節(jié)點值，轉(zhuǎn)向右子樹

2.重復上述步驟，直至找到目標節(jié)點或到達葉節(jié)點（查找失?。?/p>

（二）查找性能分析

-時間復雜度：O(logn)，其中n為樹中節(jié)點數(shù)量

-空間復雜度：O(logn)，用于遞歸調(diào)用棧或迭代過程中的臨時變量

-平衡特性保證最壞情況下查找路徑不會過長

三、紅黑樹插入操作分析

插入操作需在二叉搜索樹插入完成后，通過旋轉(zhuǎn)和著色調(diào)整樹的高度和顏色屬性，以維持紅黑特性。

（一）插入步驟

1.標準BST插入：按二叉搜索樹規(guī)則將節(jié)點插入合適位置

2.更新顏色：新插入節(jié)點默認為紅色，以避免立即引入沖突

3.修復紅黑屬性：通過以下操作調(diào)整樹：

-若父節(jié)點為黑色，無需額外操作

-若父節(jié)點為紅色且叔節(jié)點存在且為紅色：

(1)著色父節(jié)點和叔節(jié)點為黑色，祖父節(jié)點為紅色

(2)將當前節(jié)點移動至祖父節(jié)點，重新從步驟3開始

-若父節(jié)點為紅色且叔節(jié)點為黑色或不存在：

(1)若當前節(jié)點為父節(jié)點的右子節(jié)點：

-左旋父節(jié)點，將當前節(jié)點變?yōu)楦腹?jié)點的左子節(jié)點

-進入(2)

(2)右旋祖父節(jié)點，將父節(jié)點變?yōu)楹谏?，祖父?jié)點變?yōu)榧t色

（二）插入性能分析

-時間復雜度：O(logn)

-空間復雜度：O(logn)

-操作過程需維護紅黑屬性，可能涉及最多三次旋轉(zhuǎn)和著色調(diào)整

四、插入示例

假設插入鍵值序列[10,20,30,40,50]：

1.插入10：樹為單節(jié)點，顏色為黑色，操作完成

2.插入20：樹變?yōu)樽笞訕浼t色，右子樹黑色，無需調(diào)整

3.插入30：父節(jié)點20為紅色，叔節(jié)點10為黑色：

-著色10和20為黑色，根節(jié)點（原根）變?yōu)榧t色

-樹重新平衡

4.后續(xù)插入40、50類似，可能涉及左旋、右旋組合調(diào)整

五、總結(jié)

紅黑樹的查找和插入操作通過嚴格的屬性維護實現(xiàn)高效性，其復雜度為O(logn)，適用于需要動態(tài)維護有序數(shù)據(jù)集的場景。插入操作需分步驟修復紅黑屬性，確保樹的高度平衡。

一、紅黑樹概述

紅黑樹是一種自平衡二叉搜索樹，通過維護紅黑屬性來保證樹的高度平衡，從而實現(xiàn)高效的查找、插入和刪除操作。其核心特性包括：

-節(jié)點顏色：每個節(jié)點為紅色或黑色。

-根節(jié)點顏色：根節(jié)點必須為黑色。

-紅色節(jié)點的子節(jié)點：紅色節(jié)點的兩個子節(jié)點必須均為黑色（即不存在連續(xù)的紅色節(jié)點）。

-黑色高度：從任何節(jié)點到其所有后代的外部路徑上，黑色節(jié)點的數(shù)量（稱為黑色高度）必須相同。

-平衡維護：通過左旋、右旋和重新著色操作來維護上述屬性。

紅黑樹的平衡性使其查找、插入和刪除操作的時間復雜度均為O(logn)，適用于需要動態(tài)維護有序數(shù)據(jù)集的場景。

二、紅黑樹查找操作分析

紅黑樹的查找過程與普通二叉搜索樹的查找類似，但需考慮其平衡特性對查找路徑的影響。

（一）查找步驟

1.初始化：從根節(jié)點開始，目標鍵值為`target`，當前節(jié)點為`current`，當前節(jié)點的高度為`currentHeight`。

2.比較鍵值：

-若`current`為空，查找失敗，返回`null`。

-若`current.value==target`，查找成功，返回`current`節(jié)點。

-若`target<current.value`，轉(zhuǎn)向左子節(jié)點，更新`current=current.left`。

-若`target>current.value`，轉(zhuǎn)向右子節(jié)點，更新`current=current.right`。

3.重復步驟2，直至找到目標節(jié)點或到達葉節(jié)點（查找失?。?/p>

4.路徑記錄（可選）：記錄從根節(jié)點到當前節(jié)點的路徑，用于后續(xù)操作（如插入時的修復）。

（二）查找性能分析

-時間復雜度：O(logn)，其中n為樹中節(jié)點數(shù)量。由于紅黑樹的高度為2log(n+1)，查找操作的高度為O(logn)。

-空間復雜度：O(logn)，用于遞歸調(diào)用棧或迭代過程中的臨時變量。若使用遞歸，棧深度為樹的高度；若使用迭代，需維護當前節(jié)點和父節(jié)點指針。

-平衡特性：紅黑樹的平衡特性保證最壞情況下查找路徑不會過長，即使樹的部分節(jié)點被刪除導致局部傾斜。

三、紅黑樹插入操作分析

插入操作需在二叉搜索樹插入完成后，通過旋轉(zhuǎn)和著色調(diào)整樹的高度和顏色屬性，以維持紅黑特性。

（一）插入步驟

1.標準BST插入：

-按照二叉搜索樹的規(guī)則將節(jié)點插入合適位置。即，若目標鍵值小于當前節(jié)點值，則插入左子樹；否則插入右子樹。遞歸執(zhí)行，直至找到空位置插入新節(jié)點。

-新插入的節(jié)點默認為紅色，以避免立即引入沖突。

2.更新祖先節(jié)點：

-從插入節(jié)點向上遍歷，記錄路徑上的所有祖先節(jié)點（包括插入節(jié)點的父節(jié)點和更上層的節(jié)點）。這些節(jié)點可能需要調(diào)整顏色或進行旋轉(zhuǎn)操作。

3.修復紅黑屬性：

-通過以下操作調(diào)整樹，確保滿足紅黑特性：

(1)父節(jié)點為黑色：

-若插入節(jié)點是唯一的子節(jié)點（即父節(jié)點的另一子節(jié)點為空），無需額外操作，樹保持平衡。

(2)父節(jié)點為紅色：

-此時必存在祖父節(jié)點（父節(jié)點的父節(jié)點）。進一步分為以下情況：

a.叔叔節(jié)點存在且為紅色：

-著色操作：將父節(jié)點和叔叔節(jié)點著色為黑色，祖父節(jié)點著色為紅色。

-遞歸修復：將當前節(jié)點移動至祖父節(jié)點，重新從步驟3開始。

b.叔叔節(jié)點為黑色或不存在：

-此時必存在祖父節(jié)點。進一步分為以下子情況：

i.當前節(jié)點是父節(jié)點的左子節(jié)點（左左情況）：

-右旋祖父節(jié)點：將祖父節(jié)點變?yōu)楹谏?，父?jié)點變?yōu)榧t色。

-重新著色：將父節(jié)點和其右子節(jié)點（若存在）著色為黑色，祖父節(jié)點著色為紅色。

-結(jié)束修復：當前節(jié)點移動至父節(jié)點，父節(jié)點移動至祖父節(jié)點，重新從步驟3開始。

ii.當前節(jié)點是父節(jié)點的右子節(jié)點（右右情況）：

-左旋父節(jié)點：將父節(jié)點變?yōu)楹谏娓腹?jié)點變?yōu)榧t色。

-重新著色：將父節(jié)點和其左子節(jié)點（若存在）著色為黑色，祖父節(jié)點著色為紅色。

-結(jié)束修復：當前節(jié)點移動至父節(jié)點，父節(jié)點移動至祖父節(jié)點，重新從步驟3開始。

4.最終調(diào)整：

-若祖父節(jié)點變?yōu)榧t色，可能需要進一步遞歸修復，直至根節(jié)點。

-最終，根節(jié)點必須為黑色，且樹滿足所有紅黑特性。

（二）插入性能分析

-時間復雜度：O(logn)，其中n為樹中節(jié)點數(shù)量。插入操作可能涉及路徑上的多個節(jié)點調(diào)整，但樹的高度保證為O(logn)，因此操作復雜度與高度成正比。

-空間復雜度：O(logn)，用于遞歸調(diào)用?；虻^程中的臨時變量。若使用遞歸，棧深度為樹的高度；若使用迭代，需維護當前節(jié)點、父節(jié)點和祖父節(jié)點指針。

-操作過程：可能涉及最多三次旋轉(zhuǎn)和著色調(diào)整（如右右情況），但整體復雜度仍為O(logn)。

（三）插入示例

假設插入鍵值序列[10,20,30,40,50]：

1.插入10：樹為單節(jié)點，顏色為黑色，操作完成。

2.插入20：樹變?yōu)樽笞訕浼t色，右子樹黑色，無需調(diào)整。

3.插入30：父節(jié)點20為紅色，叔節(jié)點10為黑色：

-著色10和20為黑色，根節(jié)點（原根）變?yōu)榧t色。

-樹重新平衡。

4.插入40：父節(jié)點30為紅色，叔節(jié)點20為黑色：

-叔叔節(jié)點為黑色，當前節(jié)點為右子節(jié)點（右右情況）：

-左旋父節(jié)點30，將父節(jié)點變?yōu)楹谏?，祖父?jié)點（原根）變?yōu)榧t色。

-重新著色父節(jié)點30和其左子節(jié)點（若存在）為黑色，祖父節(jié)點變?yōu)榧t色。

-結(jié)束修復。

5.插入50：若為右右情況，類似插入40；若為左右情況，需先左旋當前節(jié)點，再右旋父節(jié)點。

四、紅黑樹刪除操作分析

刪除操作比插入更復雜，需通過旋轉(zhuǎn)和著色調(diào)整樹的高度和顏色屬性。此處僅概述刪除步驟，具體細節(jié)需結(jié)合刪除后的樹形和節(jié)點關系進行調(diào)整。

（一）刪除步驟

1.標準BST刪除：

-若刪除節(jié)點為葉節(jié)點或僅有一個子節(jié)點，直接刪除并替換為子節(jié)點或`null`。

-若刪除節(jié)點有兩個子節(jié)點，找到其中序后繼（右子樹的最小節(jié)點）或中序前驅(qū)（左子樹的最大節(jié)點），替換其值，然后刪除原后繼或前驅(qū)節(jié)點。

2.修復紅黑屬性：

-刪除操作可能破壞紅黑特性，需通過以下操作調(diào)整：

(1)定義替換節(jié)點：

-若刪除節(jié)點為紅色，其替換節(jié)點（或其子節(jié)點）可以安全替換其位置，無需額外調(diào)整。

-若刪除節(jié)點為黑色，其替換節(jié)點必須為紅色（因為BST中刪除黑色節(jié)點會導致其子節(jié)點路徑黑色高度減1）。

(2)定義兄弟節(jié)點：

-若替換節(jié)點為右節(jié)點，其兄弟節(jié)點為左節(jié)點；反之亦然。

(3)修復循環(huán)：

-從替換節(jié)點開始，向上遍歷，記錄路徑上的所有祖先節(jié)點，通過旋轉(zhuǎn)和著色調(diào)整樹：

a.兄弟節(jié)點為紅色：

-左旋父節(jié)點：將兄弟節(jié)點變?yōu)楹谏腹?jié)點變?yōu)榧t色。

-重新著色：將父節(jié)點和其兄弟節(jié)點著色為黑色。

-右旋父節(jié)點：將父節(jié)點變?yōu)楹谏?，祖父?jié)點變?yōu)榧t色。

b.兄弟節(jié)點為黑色：

-進一步分為以下子情況：

i.兄弟節(jié)點左子節(jié)點為紅色，右子節(jié)點為黑色（左右情況）：

-右旋兄弟節(jié)點：將兄弟節(jié)點變?yōu)榧t色，其左子節(jié)點變?yōu)楹谏?/p>

-進入下一種情況。

ii.兄弟節(jié)點左子節(jié)點為黑色，右子節(jié)點為黑色（左右情況）：

-著色兄弟節(jié)點為紅色。

-著色父節(jié)點為黑色。

-將當前節(jié)點移動至祖父節(jié)點，重新從步驟3開始。

iii.兄弟節(jié)點右子節(jié)點為紅色（右右情況）：

-左旋兄弟節(jié)點：將兄弟節(jié)點變?yōu)楹谏溆易庸?jié)點變?yōu)楹谏?/p>

-重新著色父節(jié)點為黑色。

-結(jié)束修復。

3.最終調(diào)整：

-若父節(jié)點變?yōu)榧t色，可能需要進一步遞歸修復，直至根節(jié)點。

-最終，根節(jié)點必須為黑色，且樹滿足所有紅黑特性。

（二）刪除性能分析

-時間復雜度：O(logn)，其中n為樹中節(jié)點數(shù)量。刪除操作可能涉及路徑上的多個節(jié)點調(diào)整，但樹的高度保證為O(logn)，因此操作復雜度與高度成正比。

-空間復雜度：O(logn)，用于遞歸調(diào)用?；虻^程中的臨時變量。若使用遞歸，棧深度為樹的高度；若使用迭代，需維護當前節(jié)點、父節(jié)點和兄弟節(jié)點指針。

五、總結(jié)

紅黑樹的查找、插入和刪除操作通過嚴格的屬性維護實現(xiàn)高效性，其復雜度為O(logn)，適用于需要動態(tài)維護有序數(shù)據(jù)集的場景。插入和刪除操作需分步驟修復紅黑屬性，確保樹的高度平衡。具體操作涉及旋轉(zhuǎn)和著色組合，需根據(jù)樹形和節(jié)點關系靈活調(diào)整。

六、注意事項

-插入和刪除操作需謹慎處理節(jié)點顏色和樹形，避免破壞紅黑特性。

-操作過程中可能涉及多次旋轉(zhuǎn)和著色，需逐步驟驗證樹是否滿足紅黑屬性。

-實際應用中可使用遞歸或迭代方式實現(xiàn)旋轉(zhuǎn)和著色操作，遞歸方式更直觀但可能導致棧溢出，迭代方式更高效。

一、紅黑樹概述

紅黑樹是一種自平衡二叉搜索樹，通過維護紅黑屬性來保證樹的高度平衡，從而實現(xiàn)高效的查找、插入和刪除操作。其核心特性包括：

-每個節(jié)點為紅色或黑色

-根節(jié)點為黑色

-紅色節(jié)點的兩個子節(jié)點均為黑色（從任何節(jié)點到其所有后代的外部路徑上黑色節(jié)點數(shù)量相同）

-不允許出現(xiàn)連續(xù)的紅色節(jié)點

-可通過旋轉(zhuǎn)和重新著色操作保持平衡

二、紅黑樹查找操作分析

紅黑樹的查找過程與普通二叉搜索樹的查找類似，但需考慮其平衡特性對查找路徑的影響。

（一）查找步驟

1.從根節(jié)點開始，比較目標鍵值與當前節(jié)點值：

-若相等，查找成功，返回節(jié)點

-若目標鍵值小于當前節(jié)點值，轉(zhuǎn)向左子樹

-若目標鍵值大于當前節(jié)點值，轉(zhuǎn)向右子樹

2.重復上述步驟，直至找到目標節(jié)點或到達葉節(jié)點（查找失?。?/p>

（二）查找性能分析

-時間復雜度：O(logn)，其中n為樹中節(jié)點數(shù)量

-空間復雜度：O(logn)，用于遞歸調(diào)用棧或迭代過程中的臨時變量

-平衡特性保證最壞情況下查找路徑不會過長

三、紅黑樹插入操作分析

插入操作需在二叉搜索樹插入完成后，通過旋轉(zhuǎn)和著色調(diào)整樹的高度和顏色屬性，以維持紅黑特性。

（一）插入步驟

1.標準BST插入：按二叉搜索樹規(guī)則將節(jié)點插入合適位置

2.更新顏色：新插入節(jié)點默認為紅色，以避免立即引入沖突

3.修復紅黑屬性：通過以下操作調(diào)整樹：

-若父節(jié)點為黑色，無需額外操作

-若父節(jié)點為紅色且叔節(jié)點存在且為紅色：

(1)著色父節(jié)點和叔節(jié)點為黑色，祖父節(jié)點為紅色

(2)將當前節(jié)點移動至祖父節(jié)點，重新從步驟3開始

-若父節(jié)點為紅色且叔節(jié)點為黑色或不存在：

(1)若當前節(jié)點為父節(jié)點的右子節(jié)點：

-左旋父節(jié)點，將當前節(jié)點變?yōu)楦腹?jié)點的左子節(jié)點

-進入(2)

(2)右旋祖父節(jié)點，將父節(jié)點變?yōu)楹谏?，祖父?jié)點變?yōu)榧t色

（二）插入性能分析

-時間復雜度：O(logn)

-空間復雜度：O(logn)

-操作過程需維護紅黑屬性，可能涉及最多三次旋轉(zhuǎn)和著色調(diào)整

四、插入示例

假設插入鍵值序列[10,20,30,40,50]：

1.插入10：樹為單節(jié)點，顏色為黑色，操作完成

2.插入20：樹變?yōu)樽笞訕浼t色，右子樹黑色，無需調(diào)整

3.插入30：父節(jié)點20為紅色，叔節(jié)點10為黑色：

-著色10和20為黑色，根節(jié)點（原根）變?yōu)榧t色

-樹重新平衡

4.后續(xù)插入40、50類似，可能涉及左旋、右旋組合調(diào)整

五、總結(jié)

紅黑樹的查找和插入操作通過嚴格的屬性維護實現(xiàn)高效性，其復雜度為O(logn)，適用于需要動態(tài)維護有序數(shù)據(jù)集的場景。插入操作需分步驟修復紅黑屬性，確保樹的高度平衡。

一、紅黑樹概述

紅黑樹是一種自平衡二叉搜索樹，通過維護紅黑屬性來保證樹的高度平衡，從而實現(xiàn)高效的查找、插入和刪除操作。其核心特性包括：

-節(jié)點顏色：每個節(jié)點為紅色或黑色。

-根節(jié)點顏色：根節(jié)點必須為黑色。

-紅色節(jié)點的子節(jié)點：紅色節(jié)點的兩個子節(jié)點必須均為黑色（即不存在連續(xù)的紅色節(jié)點）。

-黑色高度：從任何節(jié)點到其所有后代的外部路徑上，黑色節(jié)點的數(shù)量（稱為黑色高度）必須相同。

-平衡維護：通過左旋、右旋和重新著色操作來維護上述屬性。

紅黑樹的平衡性使其查找、插入和刪除操作的時間復雜度均為O(logn)，適用于需要動態(tài)維護有序數(shù)據(jù)集的場景。

二、紅黑樹查找操作分析

紅黑樹的查找過程與普通二叉搜索樹的查找類似，但需考慮其平衡特性對查找路徑的影響。

（一）查找步驟

1.初始化：從根節(jié)點開始，目標鍵值為`target`，當前節(jié)點為`current`，當前節(jié)點的高度為`currentHeight`。

2.比較鍵值：

-若`current`為空，查找失敗，返回`null`。

-若`current.value==target`，查找成功，返回`current`節(jié)點。

-若`target<current.value`，轉(zhuǎn)向左子節(jié)點，更新`current=current.left`。

-若`target>current.value`，轉(zhuǎn)向右子節(jié)點，更新`current=current.right`。

3.重復步驟2，直至找到目標節(jié)點或到達葉節(jié)點（查找失敗）。

4.路徑記錄（可選）：記錄從根節(jié)點到當前節(jié)點的路徑，用于后續(xù)操作（如插入時的修復）。

（二）查找性能分析

-時間復雜度：O(logn)，其中n為樹中節(jié)點數(shù)量。由于紅黑樹的高度為2log(n+1)，查找操作的高度為O(logn)。

-空間復雜度：O(logn)，用于遞歸調(diào)用棧或迭代過程中的臨時變量。若使用遞歸，棧深度為樹的高度；若使用迭代，需維護當前節(jié)點和父節(jié)點指針。

-平衡特性：紅黑樹的平衡特性保證最壞情況下查找路徑不會過長，即使樹的部分節(jié)點被刪除導致局部傾斜。

三、紅黑樹插入操作分析

插入操作需在二叉搜索樹插入完成后，通過旋轉(zhuǎn)和著色調(diào)整樹的高度和顏色屬性，以維持紅黑特性。

（一）插入步驟

1.標準BST插入：

-按照二叉搜索樹的規(guī)則將節(jié)點插入合適位置。即，若目標鍵值小于當前節(jié)點值，則插入左子樹；否則插入右子樹。遞歸執(zhí)行，直至找到空位置插入新節(jié)點。

-新插入的節(jié)點默認為紅色，以避免立即引入沖突。

2.更新祖先節(jié)點：

-從插入節(jié)點向上遍歷，記錄路徑上的所有祖先節(jié)點（包括插入節(jié)點的父節(jié)點和更上層的節(jié)點）。這些節(jié)點可能需要調(diào)整顏色或進行旋轉(zhuǎn)操作。

3.修復紅黑屬性：

-通過以下操作調(diào)整樹，確保滿足紅黑特性：

(1)父節(jié)點為黑色：

-若插入節(jié)點是唯一的子節(jié)點（即父節(jié)點的另一子節(jié)點為空），無需額外操作，樹保持平衡。

(2)父節(jié)點為紅色：

-此時必存在祖父節(jié)點（父節(jié)點的父節(jié)點）。進一步分為以下情況：

a.叔叔節(jié)點存在且為紅色：

-著色操作：將父節(jié)點和叔叔節(jié)點著色為黑色，祖父節(jié)點著色為紅色。

-遞歸修復：將當前節(jié)點移動至祖父節(jié)點，重新從步驟3開始。

b.叔叔節(jié)點為黑色或不存在：

-此時必存在祖父節(jié)點。進一步分為以下子情況：

i.當前節(jié)點是父節(jié)點的左子節(jié)點（左左情況）：

-右旋祖父節(jié)點：將祖父節(jié)點變?yōu)楹谏?，父?jié)點變?yōu)榧t色。

-重新著色：將父節(jié)點和其右子節(jié)點（若存在）著色為黑色，祖父節(jié)點著色為紅色。

-結(jié)束修復：當前節(jié)點移動至父節(jié)點，父節(jié)點移動至祖父節(jié)點，重新從步驟3開始。

ii.當前節(jié)點是父節(jié)點的右子節(jié)點（右右情況）：

-左旋父節(jié)點：將父節(jié)點變?yōu)楹谏?，祖父?jié)點變?yōu)榧t色。

-重新著色：將父節(jié)點和其左子節(jié)點（若存在）著色為黑色，祖父節(jié)點著色為紅色。

-結(jié)束修復：當前節(jié)點移動至父節(jié)點，父節(jié)點移動至祖父節(jié)點，重新從步驟3開始。

4.最終調(diào)整：

-若祖父節(jié)點變?yōu)榧t色，可能需要進一步遞歸修復，直至根節(jié)點。

-最終，根節(jié)點必須為黑色，且樹滿足所有紅黑特性。

（二）插入性能分析

-時間復雜度：O(logn)，其中n為樹中節(jié)點數(shù)量。插入操作可能涉及路徑上的多個節(jié)點調(diào)整，但樹的高度保證為O(logn)，因此操作復雜度與高度成正比。

-空間復雜度：O(logn)，用于遞歸調(diào)用棧或迭代過程中的臨時變量。若使用遞歸，棧深度為樹的高度；若使用迭代，需維護當前節(jié)點、父節(jié)點和祖父節(jié)點指針。

-操作過程：可能涉及最多三次旋轉(zhuǎn)和著色調(diào)整（如右右情況），但整體復雜度仍為O(logn)。

（三）插入示例

假設插入鍵值序列[10,20,30,40,50]：

1.插入10：樹為單節(jié)點，顏色為黑色，操作完成。

2.插入20：樹變?yōu)樽笞訕浼t色，右子樹黑色，無需調(diào)整。

3.插入30：父節(jié)點20為紅色，叔節(jié)點10為黑色：

-著色10和20為黑色，根節(jié)點（原根）變?yōu)榧t色。

-樹重新平衡。

4.插入40：父節(jié)點30為紅色，叔節(jié)點20為黑色：

-叔叔節(jié)點為黑色，當前節(jié)點為右子節(jié)點（右右情況）：

-左旋父節(jié)點30，將父節(jié)點變?yōu)楹谏?，祖父?jié)點（原根）變?yōu)榧t色。

-重新著色父節(jié)點30和其左子節(jié)點（若存在）為黑色，祖父節(jié)點變?yōu)榧t色。

-結(jié)束修復。

5.插入50：若為右右情況，類似插入40；若為左右情況，需先左旋當前節(jié)點，再右旋父節(jié)點。

四、紅黑樹刪除操作分析

刪除操作比插入更復雜，需通過旋轉(zhuǎn)和著色調(diào)整樹的高度和顏色屬性。此處僅概述刪除步驟，具體細節(jié)需結(jié)合刪除后的樹形和節(jié)點關系進行調(diào)整。

（一）刪除步驟

1.標準BST刪除：

-若刪除節(jié)點為葉節(jié)點或僅有一個子節(jié)點，直接刪除并替換為子節(jié)點或`null`。

-若刪除節(jié)點有兩個子節(jié)點，找到其中序后繼（右子樹的最小節(jié)點）或中序前驅(qū)（左子樹的最大節(jié)點），替換其值，然后刪除原后繼或前驅(qū)節(jié)點。

2.修復紅黑屬性：

-刪除操作可能破壞紅黑特性，需通過以下操作調(diào)整：

(1)定義替換節(jié)點：

-若刪除節(jié)點為紅色，其替換節(jié)點（或其子節(jié)點）可以安全替換其位置，無需額外調(diào)整。

-若刪除節(jié)點為黑色，其替換節(jié)點必須為紅色（因為BST中刪除黑色節(jié)點會導致其