一、紅黑樹插入節點
1、時間複雜度：向一顆含有n個節點的紅黑樹中插入一個新節點的操作可在O（lgn）時間内完成。
2、步驟
1）、将節點z插入樹T内，就好像T是一顆普通的二叉查找樹一樣，然後将z着為紅色。
2）、為保證紅黑性質可以得到保持，調用一個輔助程式RB-INSERT-FIXUP
3、RB-Insert僞代碼
1 RB-INSERT(T, z)
2 y ← nil[T] // 建立節點“y”，将y設為空節點。
3 x ← root[T] // 設“紅黑樹T”的根節點為“x”
4 while x ≠ nil[T] // 找出要插入的節點“z”在二叉樹T中的位置“y”
5 do y ← x
6 if key[z] < key[x]
7 then x ← left[x]
8 else x ← right[x]
9 p[z] ← y // 設定 “z的父親” 為 “y”
10 if y = nil[T]
11 then root[T] ← z // 情況1：若y是空節點，則将z設為根
12 else if key[z] < key[y]
13 then left[y] ← z // 情況2：若“z所包含的值” < “y所包含的值”，則将z設為“y的左孩子”
14 else right[y] ← z // 情況3：(“z所包含的值” >= “y所包含的值”)将z設為“y的右孩子”
15 left[z] ← nil[T] // z的左孩子設為空
16 right[z] ← nil[T] // z的右孩子設為空。至此，已經完成将“節點z插入到二叉樹”中了。
17 color[z] ← RED // 将z着色為“紅色”
18 RB-INSERT-FIXUP(T, z) // 通過RB-INSERT-FIXUP對紅黑樹的節點進行顔色修改以及旋轉，讓樹T仍然是一顆紅黑樹 4、RB-INSERT-FIXUP
1 RB-INSERT-FIXUP(T, z)
2 while color[p[z]] = RED // 若“目前節點(z)的父節點是紅色”，則進行以下處理。
3 do if p[z] = left[p[p[z]]] // 若“z的父節點”是“z的祖父節點的左孩子”，則進行以下處理。
4 then y ← right[p[p[z]]] // 将y設定為“z的叔叔節點(z的祖父節點的右孩子)”
5 if color[y] = RED // Case 1條件：叔叔是紅色
6 then color[p[z]] ← BLACK ▹ Case 1 // (01) 将“父節點”設為黑色。
7 color[y] ← BLACK ▹ Case 1 // (02) 将“叔叔節點”設為黑色。
8 color[p[p[z]]] ← RED ▹ Case 1 // (03) 将“祖父節點”設為“紅色”。
9 z ← p[p[z]] ▹ Case 1 // (04) 将“祖父節點”設為“目前節點”(紅色節點)
10 else if z = right[p[z]] // Case 2條件：叔叔是黑色，且目前節點是右孩子
11 then z ← p[z] ▹ Case 2 // (01) 将“父節點”作為“新的目前節點”。
12 LEFT-ROTATE(T, z) ▹ Case 2 // (02) 以“新的目前節點”為支點進行左旋。
13 color[p[z]] ← BLACK ▹ Case 3 // Case 3條件：叔叔是黑色，且目前節點是左孩子。(01) 将“父節點”設為“黑色”。
14 color[p[p[z]]] ← RED ▹ Case 3 // (02) 将“祖父節點”設為“紅色”。
15 RIGHT-ROTATE(T, p[p[z]]) ▹ Case 3 // (03) 以“祖父節點”為支點進行右旋。
16 else (same as then clause with "right" and "left" exchanged) // 若“z的父節點”是“z的祖父節點的右孩子”，将上面的操作中“right”和“left”交換位置，然後依次執行。
17 color[root[T]] ← BLACK 根據被插入節點的父節點的情況，可以将"當節點z被着色為紅色節點，并插入二叉樹"劃分為三種情況來處理。
1）被插入的節點是根節點。我們隻需要直接把此節點塗為黑色。
2）被插入的節點的父節點是黑色。什麼也不需要做。節點被插入後，仍然是紅黑樹。
3）被插入的節點的父節點是紅色。 那麼，該情況與紅黑樹的“特性(5)”相沖突。這種情況下，被插入節點是一定存在非空祖父節點的；進一步的講，被插入節點也一定存在叔叔節點(即使叔叔節點為空，我們也視之為存在，空節點本身就是黑色節點)。了解這點之後，我們依據"叔叔節點的情況"，将這種情況進一步劃分為3種情況(Case)。
| 現象說明 | 處理政策 | |
| Case 1 | 目前節點的父節點是紅色，且目前節點的祖父節點的另一個子節點（叔叔節點）也是紅色。 | (01) 将“父節點”設為黑色。 (02) 将“叔叔節點”設為黑色。 (03) 将“祖父節點”設為“紅色”。 (04) 将“祖父節點”設為“目前節點”(紅色節點)；即，之後繼續對“目前節點”進行操作。 |
| Case 2 | 目前節點的父節點是紅色，叔叔節點是黑色，且目前節點是其父節點的右孩子 | (01) 将“父節點”作為“新的目前節點”。 (02) 以“新的目前節點”為支點進行左旋。 |
| Case 3 | 目前節點的父節點是紅色，叔叔節點是黑色，且目前節點是其父節點的左孩子 | (01) 将“父節點”設為“黑色”。 (02) 将“祖父節點”設為“紅色”。 (03) 以“祖父節點”為支點進行右旋。 |
上面三種情況(Case)處理問題的核心思路都是：将紅色的節點移到根節點；然後，将根節點設為黑色。下面對它們詳細進行介紹。
1. (Case 1)叔叔是紅色
1.1 現象說明
目前節點(即，被插入節點)的父節點是紅色，且目前節點的祖父節點的另一個子節點（叔叔節點）也是紅色。
1.2 處理政策
(01) 将“父節點”設為黑色。
(02) 将“叔叔節點”設為黑色。
(03) 将“祖父節點”設為“紅色”。
(04) 将“祖父節點”設為“目前節點”(紅色節點)；即，之後繼續對“目前節點”進行操作。
下面談談為什麼要這樣處理。(建議了解的時候，通過下面的圖進行對比)
“目前節點”和“父節點”都是紅色，違背“特性(4)”。是以，将“父節點”設定“黑色”以解決這個問題。
但是，将“父節點”由“紅色”變成“黑色”之後，違背了“特性(5)”：因為，包含“父節點”的分支的黑色節點的總數增加了1。 解決這個問題的辦法是：将“祖父節點”由“黑色”變成紅色，同時，将“叔叔節點”由“紅色”變成“黑色”。關于這裡，說明幾點：第一，為什麼“祖父節點”之前是黑色？這個應該很容易想明白，因為在變換操作之前，該樹是紅黑樹，“父節點”是紅色，那麼“祖父節點”一定是黑色。 第二，為什麼将“祖父節點”由“黑色”變成紅色，同時，将“叔叔節點”由“紅色”變成“黑色”；能解決“包含‘父節點’的分支的黑色節點的總數增加了1”的問題。這個道理也很簡單。“包含‘父節點’的分支的黑色節點的總數增加了1” 同時也意味着 “包含‘祖父節點’的分支的黑色節點的總數增加了1”，既然這樣，我們通過将“祖父節點”由“黑色”變成“紅色”以解決“包含‘祖父節點’的分支的黑色節點的總數增加了1”的問題； 但是，這樣處理之後又會引起另一個問題“包含‘叔叔’節點的分支的黑色節點的總數減少了1”，現在我們已知“叔叔節點”是“紅色”，将“叔叔節點”設為“黑色”就能解決這個問題。 是以，将“祖父節點”由“黑色”變成紅色，同時，将“叔叔節點”由“紅色”變成“黑色”；就解決了該問題。
按照上面的步驟處理之後：目前節點、父節點、叔叔節點之間都不會違背紅黑樹特性，但祖父節點卻不一定。若此時，祖父節點是根節點，直接将祖父節點設為“黑色”，那就完全解決這個問題了；若祖父節點不是根節點，那我們需要将“祖父節點”設為“新的目前節點”，接着對“新的目前節點”進行分析。
1.3 示意圖
2. (Case 2)叔叔是黑色，且目前節點是右孩子
2.1 現象說明
目前節點(即，被插入節點)的父節點是紅色，叔叔節點是黑色，且目前節點是其父節點的右孩子
2.2 處理政策
(01) 将“父節點”作為“新的目前節點”。
(02) 以“新的目前節點”為支點進行左旋。
下面談談為什麼要這樣處理。(建議了解的時候，通過下面的圖進行對比)
首先，将“父節點”作為“新的目前節點”；接着，以“新的目前節點”為支點進行左旋。 為了便于了解，我們先說明第(02)步，再說明第(01)步；為了便于說明，我們設定“父節點”的代号為F(Father)，“目前節點”的代号為S(Son)。
為什麼要“以F為支點進行左旋”呢？根據已知條件可知：S是F的右孩子。而之前我們說過，我們處理紅黑樹的核心思想：将紅色的節點移到根節點；然後，将根節點設為黑色。既然是“将紅色的節點移到根節點”，那就是說要不斷的将破壞紅黑樹特性的紅色節點上移(即向根方向移動)。 而S又是一個右孩子，是以，我們可以通過“左旋”來将S上移！
按照上面的步驟(以F為支點進行左旋)處理之後：若S變成了根節點，那麼直接将其設為“黑色”，就完全解決問題了；若S不是根節點，那我們需要執行步驟(01)，即“将F設為‘新的目前節點’”。那為什麼不繼續以S為新的目前節點繼續處理，而需要以F為新的目前節點來進行處理呢？這是因為“左旋”之後，F變成了S的“子節點”，即S變成了F的父節點；而我們處理問題的時候，需要從下至上(由葉到根)方向進行處理；也就是說，必須先解決“孩子”的問題，再解決“父親”的問題；是以，我們執行步驟(01)：将“父節點”作為“新的目前節點”。
2.2 示意圖
3. (Case 3)叔叔是黑色，且目前節點是左孩子
3.1 現象說明
目前節點(即，被插入節點)的父節點是紅色，叔叔節點是黑色，且目前節點是其父節點的左孩子
3.2 處理政策
(01) 将“父節點”設為“黑色”。
(02) 将“祖父節點”設為“紅色”。
(03) 以“祖父節點”為支點進行右旋。
下面談談為什麼要這樣處理。(建議了解的時候，通過下面的圖進行對比)
為了便于說明，我們設定“目前節點”為S(Original Son)，“兄弟節點”為B(Brother)，“叔叔節點”為U(Uncle)，“父節點”為F(Father)，祖父節點為G(Grand-Father)。
S和F都是紅色，違背了紅黑樹的“特性(4)”，我們可以将F由“紅色”變為“黑色”，就解決了“違背‘特性(4)’”的問題；但卻引起了其它問題：違背特性(5)，因為将F由紅色改為黑色之後，所有經過F的分支的黑色節點的個數增加了1。那我們如何解決“所有經過F的分支的黑色節點的個數增加了1”的問題呢？ 我們可以通過“将G由黑色變成紅色”，同時“以G為支點進行右旋”來解決。
2.3 示意圖
提示：上面的進行Case 3處理之後，再将節點"120"當作目前節點，就變成了Case 2的情況。