紅黑樹的插入規(guī)程一、紅黑樹的概述

紅黑樹是一種自平衡的二叉查找樹，每個節(jié)點都包含一個顏色屬性，可以是紅色或黑色。其核心特性包括：

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

2.根節(jié)點必須是黑色。

3.所有葉子節(jié)點（NIL節(jié)點）均為黑色。

4.如果一個節(jié)點是紅色的，則其兩個子節(jié)點必須都是黑色（從任何節(jié)點到其所有后代葉子的簡單路徑上不能有相鄰的紅色節(jié)點）。

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

二、紅黑樹的插入操作

紅黑樹的插入過程與普通二叉查找樹的插入類似，但在插入后需要通過一系列旋轉(zhuǎn)和重新著色操作來維護紅黑樹的性質(zhì)。具體步驟如下：

（一）基本插入步驟

1.創(chuàng)建節(jié)點：在二叉查找樹中找到合適的插入位置，創(chuàng)建一個紅色的節(jié)點，并將其插入。

2.初始平衡檢查：由于新節(jié)點是紅色的，可能破壞紅黑樹的某些性質(zhì)（如相鄰紅色節(jié)點），因此需要后續(xù)調(diào)整。

（二）插入后的調(diào)整操作

如果插入節(jié)點后紅黑樹的性質(zhì)被破壞，需要進(jìn)行以下調(diào)整：

1.情況一：新節(jié)點的父節(jié)點是黑色

-此時樹仍然滿足紅黑樹的性質(zhì)，無需額外操作。

2.情況二：新節(jié)點的父節(jié)點是紅色

-這可能引發(fā)以下子情況，需要分別處理：

(1)叔叔節(jié)點是紅色

-操作步驟：

1)將父節(jié)點和叔叔節(jié)點都變?yōu)楹谏?/p>

2)將祖父節(jié)點變?yōu)榧t色。

3)將當(dāng)前節(jié)點移動到祖父節(jié)點位置。

4)重新從新的當(dāng)前節(jié)點開始檢查。

(2)叔叔節(jié)點是黑色

-根據(jù)當(dāng)前節(jié)點與父節(jié)點的相對位置，分為兩種情況：

a)當(dāng)前節(jié)點是右孩子

-操作步驟：

1)將父節(jié)點變?yōu)楹谏?/p>

2)將祖父節(jié)點變?yōu)榧t色。

3)對父節(jié)點進(jìn)行左旋。

4)將當(dāng)前節(jié)點移動到祖父節(jié)點位置，重新檢查。

b)當(dāng)前節(jié)點是左孩子

-操作步驟：

1)將父節(jié)點變?yōu)楹谏?/p>

2)將祖父節(jié)點變?yōu)榧t色。

3)對祖父節(jié)點進(jìn)行右旋。

4)將當(dāng)前節(jié)點移動到父節(jié)點位置，重新檢查。

（三）終止條件

調(diào)整過程持續(xù)進(jìn)行，直到滿足以下條件之一：

1.當(dāng)前節(jié)點到達(dá)樹根，且所有性質(zhì)均恢復(fù)。

2.遇到黑色節(jié)點且無法繼續(xù)調(diào)整。

三、示例插入過程

假設(shè)插入節(jié)點值為15，樹初始狀態(tài)如下（節(jié)點值表示節(jié)點，B表示黑色，R表示紅色）：

10(B)

/\

5(B)13(R)

/\

11(B)15(R)

插入節(jié)點15后，父節(jié)點13為紅色，叔叔節(jié)點為空（視為黑色），屬于情況二(2)b)：

1.父節(jié)點13變?yōu)楹谏?/p>

2.祖父節(jié)點10變?yōu)榧t色。

3.對祖父節(jié)點10進(jìn)行右旋：

13(R)

/\

10(B)15(R)

/

5(B)

4.重新檢查當(dāng)前節(jié)點15（現(xiàn)為右孩子），發(fā)現(xiàn)樹已平衡，插入完成。

四、插入操作的時間復(fù)雜度

紅黑樹的插入操作包括查找插入位置和后續(xù)的調(diào)整過程。

-查找操作的時間復(fù)雜度為O(h)，其中h為樹的高度，平攤情況下為O(logn)。

-調(diào)整操作最壞情況下需要O(logn)次旋轉(zhuǎn)和重新著色。

因此，總時間復(fù)雜度為O(logn)。

一、紅黑樹的概述

紅黑樹是一種自平衡的二叉查找樹，每個節(jié)點都包含一個顏色屬性，可以是紅色或黑色。其核心特性對于理解插入和調(diào)整至關(guān)重要，具體包括：

1.節(jié)點顏色：每個節(jié)點要么是紅色，要么是黑色。這構(gòu)成了樹的基本著色規(guī)則。

2.根節(jié)點顏色：紅黑樹的根節(jié)點必須是黑色。這是確保樹從頂部開始的平衡性的關(guān)鍵。

3.葉子節(jié)點顏色：所有的葉子節(jié)點（在標(biāo)準(zhǔn)定義中通常指NIL節(jié)點或空指針，它們在插入時被添加，但在刪除時可能被移除）必須是黑色。這些虛擬節(jié)點不影響路徑計數(shù)，但維護了樹的完整性。

4.紅色節(jié)點的子節(jié)點顏色：如果一個節(jié)點是紅色的，那么它的兩個子節(jié)點必須都是黑色。這個規(guī)則直接防止了兩個紅色節(jié)點相鄰，從而避免了從根到葉子的路徑上出現(xiàn)兩條連續(xù)的紅色路徑，保證了樹的基本平衡。

5.黑色高度（BlackHeight）：從任何節(jié)點到其所有葉子的簡單路徑上必須包含相同數(shù)目的黑色節(jié)點。這個屬性被稱為樹的“黑色高度”，是紅黑樹平衡性的核心度量。任何從根到葉子的路徑，其黑色節(jié)點的數(shù)量是固定的。這個常數(shù)被稱為樹的黑高，通常用`B(H)`表示，其中`H`是樹的高度。這一特性確保了樹的最小高度，從而提供了良好的查找性能。

二、紅黑樹的插入操作

紅黑樹的插入過程首先遵循標(biāo)準(zhǔn)二叉查找樹的插入方法，即找到合適的插入位置，然后將新節(jié)點插入。然而，由于紅黑樹的自平衡特性，插入新節(jié)點后必須進(jìn)行一系列的檢查和調(diào)整，以確保所有紅黑性質(zhì)仍然得到滿足。這些調(diào)整是通過旋轉(zhuǎn)和重新著色來完成的。具體步驟如下：

（一）基本插入步驟

1.查找插入位置：

-從根節(jié)點開始，按照二叉查找樹的規(guī)則（若當(dāng)前節(jié)點值小于目標(biāo)值，則向左子樹查找；否則向右子樹查找）向下遍歷。

-當(dāng)找到一個空子節(jié)點（即NULL或NIL節(jié)點）時，新的節(jié)點將插入到該位置。

2.創(chuàng)建并插入節(jié)點：

-創(chuàng)建一個新節(jié)點，其值為待插入的值，初始顏色設(shè)為紅色。

-將該節(jié)點作為上述步驟中找到的空子節(jié)點。

3.初始性質(zhì)檢查：

-插入操作完成后，首先檢查紅黑樹的根節(jié)點是否為黑色。由于根節(jié)點初始可能為紅色（尤其是在樹為空時插入第一個節(jié)點的情況，此時需要特殊處理，將根節(jié)點設(shè)為黑色），但通常在更通用的插入流程中，我們會假設(shè)根節(jié)點已經(jīng)是黑色（或通過后續(xù)調(diào)整來處理根節(jié)點顏色）。

-檢查是否存在相鄰的紅色節(jié)點。由于新插入的節(jié)點是紅色的，其父節(jié)點也必須是黑色。如果父節(jié)點是紅色，則根據(jù)叔叔節(jié)點的顏色進(jìn)入不同的調(diào)整流程。如果父節(jié)點是黑色，則樹仍然滿足紅黑樹的性質(zhì)，無需額外操作，插入過程結(jié)束。

（二）插入后的調(diào)整操作

如果插入節(jié)點后紅黑樹的性質(zhì)被破壞（主要是性質(zhì)4和性質(zhì)5），需要進(jìn)行以下調(diào)整。調(diào)整過程的核心是通過局部旋轉(zhuǎn)和顏色變換來修復(fù)被破壞的性質(zhì)。主要涉及以下幾種情況：

1.情況一：新節(jié)點的父節(jié)點是黑色

-分析：如果新插入的紅色節(jié)點的父節(jié)點已經(jīng)是黑色，那么插入操作不會直接違反任何紅黑性質(zhì)。這是因為：

-性質(zhì)4（紅色節(jié)點的子節(jié)點必須是黑色）不會被違反，因為新節(jié)點是紅色的，其子節(jié)點（如果存在）在插入時默認(rèn)為NIL節(jié)點（黑色）。

-性質(zhì)5（從任一節(jié)點到其每個葉子的所有簡單路徑上包含相同數(shù)目的黑色節(jié)點）也不會被違反，因為新增了一條紅色路徑，而另一條未經(jīng)過新節(jié)點的路徑的黑色節(jié)點數(shù)量不變。

-結(jié)論：此時樹仍然滿足紅黑樹的性質(zhì)，無需額外操作。插入完成。

2.情況二：新節(jié)點的父節(jié)點是紅色

-分析：這種情況會直接違反紅黑樹的性質(zhì)4（因為一個紅色節(jié)點有了另一個紅色節(jié)點作為其子節(jié)點）。此時需要進(jìn)一步檢查叔叔節(jié)點的顏色，以決定具體的調(diào)整策略。

-子情況(1)：叔叔節(jié)點是紅色

-場景描述：假設(shè)當(dāng)前節(jié)點（記為`x`）是紅色，其父節(jié)點（記為`p`）是紅色，且`p`是祖父節(jié)點（記為`g`）的左孩子。如果`x`是`p`的右孩子，可以通過左旋將`x`和`p`的位置交換，然后轉(zhuǎn)換到`p`是`g`的左孩子的情況。如果`x`是`p`的左孩子，則直接進(jìn)行以下操作。

-操作步驟：

a)顏色變換：將當(dāng)前節(jié)點`x`的父節(jié)點`p`和叔叔節(jié)點`u`（`u`是`g`的另一個子節(jié)點）都變?yōu)楹谏?。同時，將祖父節(jié)點`g`變?yōu)榧t色。

-目的：這一步消除了直接相鄰的兩個紅色節(jié)點（`p`和`u`），但引入了一個新的紅色節(jié)點（`g`），可能需要進(jìn)一步調(diào)整。

b)節(jié)點移動：將當(dāng)前節(jié)點`x`向上移動到祖父節(jié)點`g`的位置。即，`x`現(xiàn)在指向`g`原來的位置。

-目的：因為`g`現(xiàn)在變成了紅色，且`x`仍然在`g`的子樹中，所以`x`和`g`形成了一個新的“父紅子紅”對，需要再次檢查。

c)重新檢查：從新的當(dāng)前節(jié)點`x`（即原來的`g`）開始，返回到情況二或情況三進(jìn)行檢查。如果`x`到達(dá)了根節(jié)點，則將根節(jié)點設(shè)為黑色（這是唯一可能需要改變根節(jié)點顏色的場景），調(diào)整結(jié)束。

-子情況(2)：叔叔節(jié)點是黑色

-場景描述：假設(shè)當(dāng)前節(jié)點`x`是紅色，其父節(jié)點`p`是紅色，且叔叔節(jié)點`u`是黑色。這需要根據(jù)當(dāng)前節(jié)點`x`與父節(jié)點`p`的相對位置（左孩子或右孩子）進(jìn)行不同的旋轉(zhuǎn)操作。

-子情況2a：當(dāng)前節(jié)點`x`是左孩子（LeftChild）

-場景分析：這種情況稱為“左左情況”（Left-LeftCase）。此時樹的結(jié)構(gòu)類似于一個向右傾斜的紅鏈接。

-操作步驟：

a)父節(jié)點顏色變換：將父節(jié)點`p`變?yōu)楹谏?/p>

-目的：修復(fù)`p`和`x`之間的紅鏈接。

b)祖父節(jié)點顏色變換：將祖父節(jié)點`g`變?yōu)榧t色。

-目的：平衡由于`p`變?yōu)楹谏赡芤氲牟黄胶狻?/p>

c)右旋操作：對祖父節(jié)點`g`執(zhí)行右旋（RightRotation）。

-執(zhí)行細(xì)節(jié)：旋轉(zhuǎn)的中心是`g`。`g`的左子樹（即父節(jié)點`p`所在的子樹）會“順時針”移動到`g`的右子樹位置。`p`成為新的子樹的根，`x`成為`p`的右孩子。

-目的：這一系列操作（著色變換+右旋）將原來的“左左”不平衡模式轉(zhuǎn)換為一個可能需要進(jìn)一步處理的“右右”模式，或者直接修復(fù)了不平衡。

d)重新檢查：右旋后，檢查新的當(dāng)前節(jié)點`x`（原來是`g`）是否到達(dá)了根節(jié)點，或者是否形成了新的“父紅子紅”對。如果需要，從新的當(dāng)前節(jié)點開始繼續(xù)檢查。

-子情況2b：當(dāng)前節(jié)點`x`是右孩子（RightChild）

-場景分析：這種情況稱為“右右情況”（Right-RightCase）。此時樹的結(jié)構(gòu)類似于一個向左傾斜的紅鏈接。

-操作步驟：

a)父節(jié)點顏色變換：將父節(jié)點`p`變?yōu)楹谏?/p>

-目的：修復(fù)`p`和`x`之間的紅鏈接。

b)祖父節(jié)點顏色變換：將祖父節(jié)點`g`變?yōu)榧t色。

-目的：平衡由于`p`變?yōu)楹谏赡芤氲牟黄胶狻?/p>

c)左旋操作：對祖父節(jié)點`g`執(zhí)行左旋（LeftRotation）。

-執(zhí)行細(xì)節(jié)：旋轉(zhuǎn)的中心是`g`。`g`的右子樹（即父節(jié)點`p`所在的子樹）會“逆時針”移動到`g`的左子樹位置。`p`成為新的子樹的根，`x`成為`p`的左孩子。

-目的：這一系列操作（著色變換+左旋）將原來的“右右”不平衡模式轉(zhuǎn)換為一個可能需要進(jìn)一步處理的“左左”模式，或者直接修復(fù)了不平衡。

d)重新檢查：左旋后，檢查新的當(dāng)前節(jié)點`x`（原來是`g`）是否到達(dá)了根節(jié)點，或者是否形成了新的“父紅子紅”對。如果需要，從新的當(dāng)前節(jié)點開始繼續(xù)檢查。

（三）終止條件

調(diào)整過程持續(xù)進(jìn)行，直到滿足以下條件之一：

1.到達(dá)根節(jié)點并完成調(diào)整：如果當(dāng)前節(jié)點在調(diào)整過程中移動到了根節(jié)點位置，并且在該過程中所有性質(zhì)都被修復(fù)，則將根節(jié)點設(shè)為黑色（這是唯一可能需要改變根節(jié)點顏色的場景），調(diào)整結(jié)束。

2.無法繼續(xù)調(diào)整：如果在調(diào)整過程中，當(dāng)前節(jié)點不再滿足進(jìn)入調(diào)整條件（如到達(dá)了葉子節(jié)點或叔叔節(jié)點不是紅色且當(dāng)前節(jié)點是右孩子等），且沒有違反的性質(zhì)，則調(diào)整結(jié)束。

3.所有性質(zhì)恢復(fù)：調(diào)整過程中的每一步都旨在逐步修復(fù)被破壞的性質(zhì)。當(dāng)所有性質(zhì)（特別是性質(zhì)4和性質(zhì)5）都恢復(fù)到定義狀態(tài)時，調(diào)整結(jié)束。

三、示例插入過程（詳細(xì)展開）

假設(shè)我們要向一個初始為空的紅黑樹中插入節(jié)點值為15。我們逐步插入節(jié)點，并展示每次插入后的樹狀圖和必要的調(diào)整。

初始狀態(tài)（空樹）：

[]

插入節(jié)點10：

1.樹為空，創(chuàng)建根節(jié)點10，顏色為黑色。

2.樹滿足所有紅黑性質(zhì)。

10(B)

插入節(jié)點5：

1.10是黑色，5插入為10的左孩子。

2.5是紅色，10是黑色，性質(zhì)4和5均滿足。

10(B)

/

5(R)

插入節(jié)點20：

1.10是黑色，20插入為10的右孩子。

2.20是紅色，10是黑色，性質(zhì)4和5均滿足。

10(B)

/\

5(R)20(R)

插入節(jié)點15：

1.查找插入位置：從根開始，10<15，向右子樹，20<15，向20的右子樹，無子節(jié)點，插入15為20的右孩子。

2.15是紅色，其父節(jié)點20是紅色，違反性質(zhì)4。

3.檢查叔叔節(jié)點：15的父節(jié)點是20，祖父節(jié)點是10。20是10的右孩子，查找10的左孩子（即5），5是黑色，所以叔叔節(jié)點5是黑色。

4.屬于情況二(2)。

5.檢查當(dāng)前節(jié)點15與父節(jié)點20的相對位置：15是20的左孩子。

6.屬于子情況2a（左左情況）。

7.執(zhí)行子情況2a的操作：

a)將父節(jié)點20變?yōu)楹谏?/p>

b)將祖父節(jié)點10變?yōu)榧t色。

c)對祖父節(jié)點10執(zhí)行右旋。

8.右旋操作細(xì)節(jié)：

-旋轉(zhuǎn)中心是10。

-10的左子樹（5）現(xiàn)在成為10的右子樹。

-20成為5的右子樹。

-15成為20的左子樹。

9.調(diào)整后的樹：

10(R)

/

5(B)

\

20(B)

/

15(R)

10.重新檢查：

-當(dāng)前節(jié)點是15，其父節(jié)點是20，顏色為黑色。

-叔叔節(jié)點是5，顏色為黑色。

-15是20的右孩子。

-屬于情況二(2)。

-檢查當(dāng)前節(jié)點15與父節(jié)點20的相對位置：15是20的右孩子。

-屬于子情況2b（右右情況）。

-執(zhí)行子情況2b的操作：

a)將父節(jié)點20變?yōu)楹谏?/p>

b)將祖父節(jié)點10變?yōu)榧t色。

c)對祖父節(jié)點10執(zhí)行左旋。

d.左旋操作細(xì)節(jié)：

-旋轉(zhuǎn)中心是10。

-10的右子樹（20為根的子樹）現(xiàn)在成為10的左子樹。

-5成為20的父節(jié)點，且成為10的右子樹。

-15成為5的右子樹。

e.調(diào)整后的樹：

20(B)

/\

10(R)5(B)

\

15(R)

f.重新檢查：

-當(dāng)前節(jié)點是15，其父節(jié)點是10，顏色為紅色。

-叔叔節(jié)點是5，顏色為黑色。

-15是10的右孩子。

-屬于情況二(2)。

-檢查當(dāng)前節(jié)點15與父節(jié)點10的相對位置：15是10的右孩子。

-屬于子情況2b（右右情況）。

-執(zhí)行子情況2b的操作：

a)將父節(jié)點10變?yōu)楹谏?/p>

b)將祖父節(jié)點20變?yōu)榧t色。

c)對祖父節(jié)點20執(zhí)行左旋。

d.左旋操作細(xì)節(jié)：

-旋轉(zhuǎn)中心是20。

-20的右子樹（5為根的子樹）現(xiàn)在成為20的左子樹。

-10成為5的父節(jié)點，且成為20的右子樹。

-15成為10的右子樹。

e.調(diào)整后的樹：

10(B)

/\

20(R)5(B)

\

15(R)

f.重新檢查：

-當(dāng)前節(jié)點是15，其父節(jié)點是10，顏色為黑色。

-叔叔節(jié)點是5，顏色為黑色。

-15是10的右孩子。

-屬于情況二(2)。

-檢查當(dāng)前節(jié)點15與父節(jié)點10的相對位置：15是10的右孩子。

-屬于子情況2b（右右情況）。

-執(zhí)行子情況2b的操作：

a)將父節(jié)點10變?yōu)楹谏＃ㄒ淹瓿桑?/p>

b)將祖父節(jié)點20變?yōu)榧t色。（已完成）

c)對祖父節(jié)點20執(zhí)行左旋。（已完成）

g.終止條件：15到達(dá)了非根節(jié)點（10）的父節(jié)點位置，且叔叔節(jié)點為黑色，且當(dāng)前節(jié)點是右孩子，且已完成所有2b步驟。樹重新滿足所有紅黑性質(zhì)。調(diào)整結(jié)束。

最終樹狀圖：

10(B)

/\

20(R)5(B)

\

15(R)

驗證黑高：計算從根到葉子的黑色節(jié)點數(shù)量。

-路徑10->20->15:10(B),20(R),15(R)->黑高=1

-路徑10->5:10(B),5(B)->黑高=2

兩條路徑的黑高均為2，滿足性質(zhì)5。

插入操作的時間復(fù)雜度

紅黑樹的插入操作包括查找插入位置和后續(xù)的調(diào)整過程。

-查找操作：在標(biāo)準(zhǔn)二叉查找樹中，查找操作的時間復(fù)雜度為O(h)，其中h是樹的高度。紅黑樹的高度在最壞情況下為O(logn)，因此查找操作的時間復(fù)雜度為O(logn)。平攤情況下也是如此。

-插入節(jié)點本身：創(chuàng)建節(jié)點并執(zhí)行插入操作是常數(shù)時間O(1)的操作。

-調(diào)整操作：調(diào)整過程可能涉及多次檢查和旋轉(zhuǎn)/重新著色。每次檢查都需要確定當(dāng)前節(jié)點、父節(jié)點和叔叔節(jié)點的位置和顏色，這可以通過O(1)的操作完成。每次旋轉(zhuǎn)也是常數(shù)時間的操作。最壞情況下，調(diào)整過程可能需要O(logn)次檢查和O(logn)次旋轉(zhuǎn)（每次調(diào)整最多進(jìn)行兩次旋轉(zhuǎn)），因此調(diào)整操作的時間復(fù)雜度為O(logn)。

-總時間復(fù)雜度：將查找操作和調(diào)整操作的時間復(fù)雜度相加，紅黑樹插入操作的總時間復(fù)雜度為O(logn)。

總結(jié)：紅黑樹的插入操作首先按照二叉查找樹的規(guī)則進(jìn)行插入，然后通過一系列基于當(dāng)前節(jié)點、父節(jié)點和叔叔節(jié)點顏色的檢查和調(diào)整（旋轉(zhuǎn)和重新著色）來維護樹的平衡和紅黑性質(zhì)。這些調(diào)整確保了插入操作的時間復(fù)雜度為O(logn)，并且保持了樹的近似平衡狀態(tài)。

一、紅黑樹的概述

紅黑樹是一種自平衡的二叉查找樹，每個節(jié)點都包含一個顏色屬性，可以是紅色或黑色。其核心特性包括：

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

2.根節(jié)點必須是黑色。

3.所有葉子節(jié)點（NIL節(jié)點）均為黑色。

4.如果一個節(jié)點是紅色的，則其兩個子節(jié)點必須都是黑色（從任何節(jié)點到其所有后代葉子的簡單路徑上不能有相鄰的紅色節(jié)點）。

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

二、紅黑樹的插入操作

紅黑樹的插入過程與普通二叉查找樹的插入類似，但在插入后需要通過一系列旋轉(zhuǎn)和重新著色操作來維護紅黑樹的性質(zhì)。具體步驟如下：

（一）基本插入步驟

1.創(chuàng)建節(jié)點：在二叉查找樹中找到合適的插入位置，創(chuàng)建一個紅色的節(jié)點，并將其插入。

2.初始平衡檢查：由于新節(jié)點是紅色的，可能破壞紅黑樹的某些性質(zhì)（如相鄰紅色節(jié)點），因此需要后續(xù)調(diào)整。

（二）插入后的調(diào)整操作

如果插入節(jié)點后紅黑樹的性質(zhì)被破壞，需要進(jìn)行以下調(diào)整：

1.情況一：新節(jié)點的父節(jié)點是黑色

-此時樹仍然滿足紅黑樹的性質(zhì)，無需額外操作。

2.情況二：新節(jié)點的父節(jié)點是紅色

-這可能引發(fā)以下子情況，需要分別處理：

(1)叔叔節(jié)點是紅色

-操作步驟：

1)將父節(jié)點和叔叔節(jié)點都變?yōu)楹谏?/p>

2)將祖父節(jié)點變?yōu)榧t色。

3)將當(dāng)前節(jié)點移動到祖父節(jié)點位置。

4)重新從新的當(dāng)前節(jié)點開始檢查。

(2)叔叔節(jié)點是黑色

-根據(jù)當(dāng)前節(jié)點與父節(jié)點的相對位置，分為兩種情況：

a)當(dāng)前節(jié)點是右孩子

-操作步驟：

1)將父節(jié)點變?yōu)楹谏?/p>

2)將祖父節(jié)點變?yōu)榧t色。

3)對父節(jié)點進(jìn)行左旋。

4)將當(dāng)前節(jié)點移動到祖父節(jié)點位置，重新檢查。

b)當(dāng)前節(jié)點是左孩子

-操作步驟：

1)將父節(jié)點變?yōu)楹谏?/p>

2)將祖父節(jié)點變?yōu)榧t色。

3)對祖父節(jié)點進(jìn)行右旋。

4)將當(dāng)前節(jié)點移動到父節(jié)點位置，重新檢查。

（三）終止條件

調(diào)整過程持續(xù)進(jìn)行，直到滿足以下條件之一：

1.當(dāng)前節(jié)點到達(dá)樹根，且所有性質(zhì)均恢復(fù)。

2.遇到黑色節(jié)點且無法繼續(xù)調(diào)整。

三、示例插入過程

假設(shè)插入節(jié)點值為15，樹初始狀態(tài)如下（節(jié)點值表示節(jié)點，B表示黑色，R表示紅色）：

10(B)

/\

5(B)13(R)

/\

11(B)15(R)

插入節(jié)點15后，父節(jié)點13為紅色，叔叔節(jié)點為空（視為黑色），屬于情況二(2)b)：

1.父節(jié)點13變?yōu)楹谏?/p>

2.祖父節(jié)點10變?yōu)榧t色。

3.對祖父節(jié)點10進(jìn)行右旋：

13(R)

/\

10(B)15(R)

/

5(B)

4.重新檢查當(dāng)前節(jié)點15（現(xiàn)為右孩子），發(fā)現(xiàn)樹已平衡，插入完成。

四、插入操作的時間復(fù)雜度

紅黑樹的插入操作包括查找插入位置和后續(xù)的調(diào)整過程。

-查找操作的時間復(fù)雜度為O(h)，其中h為樹的高度，平攤情況下為O(logn)。

-調(diào)整操作最壞情況下需要O(logn)次旋轉(zhuǎn)和重新著色。

因此，總時間復(fù)雜度為O(logn)。

一、紅黑樹的概述

紅黑樹是一種自平衡的二叉查找樹，每個節(jié)點都包含一個顏色屬性，可以是紅色或黑色。其核心特性對于理解插入和調(diào)整至關(guān)重要，具體包括：

1.節(jié)點顏色：每個節(jié)點要么是紅色，要么是黑色。這構(gòu)成了樹的基本著色規(guī)則。

2.根節(jié)點顏色：紅黑樹的根節(jié)點必須是黑色。這是確保樹從頂部開始的平衡性的關(guān)鍵。

3.葉子節(jié)點顏色：所有的葉子節(jié)點（在標(biāo)準(zhǔn)定義中通常指NIL節(jié)點或空指針，它們在插入時被添加，但在刪除時可能被移除）必須是黑色。這些虛擬節(jié)點不影響路徑計數(shù)，但維護了樹的完整性。

4.紅色節(jié)點的子節(jié)點顏色：如果一個節(jié)點是紅色的，那么它的兩個子節(jié)點必須都是黑色。這個規(guī)則直接防止了兩個紅色節(jié)點相鄰，從而避免了從根到葉子的路徑上出現(xiàn)兩條連續(xù)的紅色路徑，保證了樹的基本平衡。

5.黑色高度（BlackHeight）：從任何節(jié)點到其所有葉子的簡單路徑上必須包含相同數(shù)目的黑色節(jié)點。這個屬性被稱為樹的“黑色高度”，是紅黑樹平衡性的核心度量。任何從根到葉子的路徑，其黑色節(jié)點的數(shù)量是固定的。這個常數(shù)被稱為樹的黑高，通常用`B(H)`表示，其中`H`是樹的高度。這一特性確保了樹的最小高度，從而提供了良好的查找性能。

二、紅黑樹的插入操作

紅黑樹的插入過程首先遵循標(biāo)準(zhǔn)二叉查找樹的插入方法，即找到合適的插入位置，然后將新節(jié)點插入。然而，由于紅黑樹的自平衡特性，插入新節(jié)點后必須進(jìn)行一系列的檢查和調(diào)整，以確保所有紅黑性質(zhì)仍然得到滿足。這些調(diào)整是通過旋轉(zhuǎn)和重新著色來完成的。具體步驟如下：

（一）基本插入步驟

1.查找插入位置：

-從根節(jié)點開始，按照二叉查找樹的規(guī)則（若當(dāng)前節(jié)點值小于目標(biāo)值，則向左子樹查找；否則向右子樹查找）向下遍歷。

-當(dāng)找到一個空子節(jié)點（即NULL或NIL節(jié)點）時，新的節(jié)點將插入到該位置。

2.創(chuàng)建并插入節(jié)點：

-創(chuàng)建一個新節(jié)點，其值為待插入的值，初始顏色設(shè)為紅色。

-將該節(jié)點作為上述步驟中找到的空子節(jié)點。

3.初始性質(zhì)檢查：

-插入操作完成后，首先檢查紅黑樹的根節(jié)點是否為黑色。由于根節(jié)點初始可能為紅色（尤其是在樹為空時插入第一個節(jié)點的情況，此時需要特殊處理，將根節(jié)點設(shè)為黑色），但通常在更通用的插入流程中，我們會假設(shè)根節(jié)點已經(jīng)是黑色（或通過后續(xù)調(diào)整來處理根節(jié)點顏色）。

-檢查是否存在相鄰的紅色節(jié)點。由于新插入的節(jié)點是紅色的，其父節(jié)點也必須是黑色。如果父節(jié)點是紅色，則根據(jù)叔叔節(jié)點的顏色進(jìn)入不同的調(diào)整流程。如果父節(jié)點是黑色，則樹仍然滿足紅黑樹的性質(zhì)，無需額外操作，插入過程結(jié)束。

（二）插入后的調(diào)整操作

如果插入節(jié)點后紅黑樹的性質(zhì)被破壞（主要是性質(zhì)4和性質(zhì)5），需要進(jìn)行以下調(diào)整。調(diào)整過程的核心是通過局部旋轉(zhuǎn)和顏色變換來修復(fù)被破壞的性質(zhì)。主要涉及以下幾種情況：

1.情況一：新節(jié)點的父節(jié)點是黑色

-分析：如果新插入的紅色節(jié)點的父節(jié)點已經(jīng)是黑色，那么插入操作不會直接違反任何紅黑性質(zhì)。這是因為：

-性質(zhì)4（紅色節(jié)點的子節(jié)點必須是黑色）不會被違反，因為新節(jié)點是紅色的，其子節(jié)點（如果存在）在插入時默認(rèn)為NIL節(jié)點（黑色）。

-性質(zhì)5（從任一節(jié)點到其每個葉子的所有簡單路徑上包含相同數(shù)目的黑色節(jié)點）也不會被違反，因為新增了一條紅色路徑，而另一條未經(jīng)過新節(jié)點的路徑的黑色節(jié)點數(shù)量不變。

-結(jié)論：此時樹仍然滿足紅黑樹的性質(zhì)，無需額外操作。插入完成。

2.情況二：新節(jié)點的父節(jié)點是紅色

-分析：這種情況會直接違反紅黑樹的性質(zhì)4（因為一個紅色節(jié)點有了另一個紅色節(jié)點作為其子節(jié)點）。此時需要進(jìn)一步檢查叔叔節(jié)點的顏色，以決定具體的調(diào)整策略。

-子情況(1)：叔叔節(jié)點是紅色

-場景描述：假設(shè)當(dāng)前節(jié)點（記為`x`）是紅色，其父節(jié)點（記為`p`）是紅色，且`p`是祖父節(jié)點（記為`g`）的左孩子。如果`x`是`p`的右孩子，可以通過左旋將`x`和`p`的位置交換，然后轉(zhuǎn)換到`p`是`g`的左孩子的情況。如果`x`是`p`的左孩子，則直接進(jìn)行以下操作。

-操作步驟：

a)顏色變換：將當(dāng)前節(jié)點`x`的父節(jié)點`p`和叔叔節(jié)點`u`（`u`是`g`的另一個子節(jié)點）都變?yōu)楹谏?。同時，將祖父節(jié)點`g`變?yōu)榧t色。

-目的：這一步消除了直接相鄰的兩個紅色節(jié)點（`p`和`u`），但引入了一個新的紅色節(jié)點（`g`），可能需要進(jìn)一步調(diào)整。

b)節(jié)點移動：將當(dāng)前節(jié)點`x`向上移動到祖父節(jié)點`g`的位置。即，`x`現(xiàn)在指向`g`原來的位置。

-目的：因為`g`現(xiàn)在變成了紅色，且`x`仍然在`g`的子樹中，所以`x`和`g`形成了一個新的“父紅子紅”對，需要再次檢查。

c)重新檢查：從新的當(dāng)前節(jié)點`x`（即原來的`g`）開始，返回到情況二或情況三進(jìn)行檢查。如果`x`到達(dá)了根節(jié)點，則將根節(jié)點設(shè)為黑色（這是唯一可能需要改變根節(jié)點顏色的場景），調(diào)整結(jié)束。

-子情況(2)：叔叔節(jié)點是黑色

-場景描述：假設(shè)當(dāng)前節(jié)點`x`是紅色，其父節(jié)點`p`是紅色，且叔叔節(jié)點`u`是黑色。這需要根據(jù)當(dāng)前節(jié)點`x`與父節(jié)點`p`的相對位置（左孩子或右孩子）進(jìn)行不同的旋轉(zhuǎn)操作。

-子情況2a：當(dāng)前節(jié)點`x`是左孩子（LeftChild）

-場景分析：這種情況稱為“左左情況”（Left-LeftCase）。此時樹的結(jié)構(gòu)類似于一個向右傾斜的紅鏈接。

-操作步驟：

a)父節(jié)點顏色變換：將父節(jié)點`p`變?yōu)楹谏?/p>

-目的：修復(fù)`p`和`x`之間的紅鏈接。

b)祖父節(jié)點顏色變換：將祖父節(jié)點`g`變?yōu)榧t色。

-目的：平衡由于`p`變?yōu)楹谏赡芤氲牟黄胶狻?/p>

c)右旋操作：對祖父節(jié)點`g`執(zhí)行右旋（RightRotation）。

-執(zhí)行細(xì)節(jié)：旋轉(zhuǎn)的中心是`g`。`g`的左子樹（即父節(jié)點`p`所在的子樹）會“順時針”移動到`g`的右子樹位置。`p`成為新的子樹的根，`x`成為`p`的右孩子。

-目的：這一系列操作（著色變換+右旋）將原來的“左左”不平衡模式轉(zhuǎn)換為一個可能需要進(jìn)一步處理的“右右”模式，或者直接修復(fù)了不平衡。

d)重新檢查：右旋后，檢查新的當(dāng)前節(jié)點`x`（原來是`g`）是否到達(dá)了根節(jié)點，或者是否形成了新的“父紅子紅”對。如果需要，從新的當(dāng)前節(jié)點開始繼續(xù)檢查。

-子情況2b：當(dāng)前節(jié)點`x`是右孩子（RightChild）

-場景分析：這種情況稱為“右右情況”（Right-RightCase）。此時樹的結(jié)構(gòu)類似于一個向左傾斜的紅鏈接。

-操作步驟：

a)父節(jié)點顏色變換：將父節(jié)點`p`變?yōu)楹谏?/p>

-目的：修復(fù)`p`和`x`之間的紅鏈接。

b)祖父節(jié)點顏色變換：將祖父節(jié)點`g`變?yōu)榧t色。

-目的：平衡由于`p`變?yōu)楹谏赡芤氲牟黄胶狻?/p>

c)左旋操作：對祖父節(jié)點`g`執(zhí)行左旋（LeftRotation）。

-執(zhí)行細(xì)節(jié)：旋轉(zhuǎn)的中心是`g`。`g`的右子樹（即父節(jié)點`p`所在的子樹）會“逆時針”移動到`g`的左子樹位置。`p`成為新的子樹的根，`x`成為`p`的左孩子。

-目的：這一系列操作（著色變換+左旋）將原來的“右右”不平衡模式轉(zhuǎn)換為一個可能需要進(jìn)一步處理的“左左”模式，或者直接修復(fù)了不平衡。

d)重新檢查：左旋后，檢查新的當(dāng)前節(jié)點`x`（原來是`g`）是否到達(dá)了根節(jié)點，或者是否形成了新的“父紅子紅”對。如果需要，從新的當(dāng)前節(jié)點開始繼續(xù)檢查。

（三）終止條件

調(diào)整過程持續(xù)進(jìn)行，直到滿足以下條件之一：

1.到達(dá)根節(jié)點并完成調(diào)整：如果當(dāng)前節(jié)點在調(diào)整過程中移動到了根節(jié)點位置，并且在該過程中所有性質(zhì)都被修復(fù)，則將根節(jié)點設(shè)為黑色（這是唯一可能需要改變根節(jié)點顏色的場景），調(diào)整結(jié)束。

2.無法繼續(xù)調(diào)整：如果在調(diào)整過程中，當(dāng)前節(jié)點不再滿足進(jìn)入調(diào)整條件（如到達(dá)了葉子節(jié)點或叔叔節(jié)點不是紅色且當(dāng)前節(jié)點是右孩子等），且沒有違反的性質(zhì)，則調(diào)整結(jié)束。

3.所有性質(zhì)恢復(fù)：調(diào)整過程中的每一步都旨在逐步修復(fù)被破壞的性質(zhì)。當(dāng)所有性質(zhì)（特別是性質(zhì)4和性質(zhì)5）都恢復(fù)到定義狀態(tài)時，調(diào)整結(jié)束。

三、示例插入過程（詳細(xì)展開）

假設(shè)我們要向一個初始為空的紅黑樹中插入節(jié)點值為15。我們逐步插入節(jié)點，并展示每次插入后的樹狀圖和必要的調(diào)整。

初始狀態(tài)（空樹）：

[]

插入節(jié)點10：

1.樹為空，創(chuàng)建根節(jié)點10，顏色為黑色。

2.樹滿足所有紅黑性質(zhì)。

10(B)

插入節(jié)點5：

1.10是黑色，5插入為10的左孩子。

2.5是紅色，10是黑色，性質(zhì)4和5均滿足。

10(B)

/

5(R)

插入節(jié)點20：

1.10是黑色，20插入為10的右孩子。

2.20是紅色，10是黑色，性質(zhì)4和5均滿足。

10(B)

/\

5(R)20(R)

插入節(jié)點15：

1.查找插入位置：從根開始，10<15，向右子樹，20<15，向20的右子樹，無子節(jié)點，插入15為20的右孩子。

2.15是紅色，其父節(jié)點20是紅色，違反性質(zhì)4。

3.檢查叔叔節(jié)點：15的父節(jié)點是20，祖父節(jié)點是10。20是10的右孩子，查找10的左孩子（即5），5是黑色，所以叔叔節(jié)點5是黑色。

4.屬于情況二(2)。

5.檢查當(dāng)前節(jié)點15與父節(jié)點20的相對位置：15是20的左孩子。

6.屬于子情況2a（左左情況）。

7.執(zhí)行子情況2a的操作：

a)將父節(jié)點20變?yōu)楹谏?/p>

b)將祖父節(jié)點10變?yōu)榧t色。

c)對祖父節(jié)點10執(zhí)行右旋。

8.右旋操作細(xì)節(jié)：

-旋轉(zhuǎn)中心是10。

-10的左子樹（5）現(xiàn)在成為10的右子樹。

-20成為5的右子樹。

-15成為20的左子樹。

9.調(diào)整后的樹：

10(R)

/

5(B)

\

20(B)

/

15(R)

10.重新檢查：

-當(dāng)前節(jié)點是15，其父節(jié)點是20，顏色為黑色。

-叔叔節(jié)點是5，顏色為黑色。

-15是20的右孩子。

-屬于情況二(2)。

-檢查當(dāng)前節(jié)點15與父節(jié)點20的相對位置：15是20的右孩子。

-屬于子情況2b（右右情況）。

-執(zhí)行子情況2b的操作：

a)將父節(jié)點20變?yōu)楹谏?/p>

b)將祖父節(jié)點10變?yōu)榧t色。

c)對祖父節(jié)點10執(zhí)行左旋。

d.左旋操作細(xì)節(jié)：

-旋轉(zhuǎn)中心是10。

-10