紅黑樹插入與調整詳解

一、紅黑樹的五大性質

紅黑樹是一種自平衡的二叉搜索樹（BST），其核心特性如下：

1. 顏色屬性：每個節點非紅即黑
2. 根屬性：根節點必須為黑色
3. 葉子屬性：所有的 NIL 葉子節點都是黑色
4. 紅節點約束：紅色節點的子節點必須為黑色（即無連續紅節點）
5. 黑高平衡：從任一節點到其所有后代葉子節點的路徑中，黑色節點數量相等

---

二、插入操作流程

階段 1：標準 BST 插入

• 從根節點開始查找插入位置
• 新節點總是紅色
• 按照 BST 規則插入

階段 2：平衡修復（重點）

當插入后新節點的父節點是紅色時，需要進行結構調整。核心考量因素：

• 父節點是祖父的左孩子還是右孩子
• 叔叔節點的顏色
• 新節點的插入方向（左/右）

---

三、調整情況詳解

情況分類表

父節點位置	叔叔顏色	插入方向	操作類型	案例編號
左子樹	紅	-	重新著色	Case 1
左子樹	黑	右孩子	左旋	Case 2
左子樹	黑	左孩子	右旋 + 變色	Case 3
右子樹	紅	-	重新著色	Case 1’
右子樹	黑	左孩子	右旋	Case 2’
右子樹	黑	右孩子	左旋 + 變色	Case 3’

---

詳細調整步驟（以父節點為左孩子為例）

Case 1：叔叔為紅色

• 父節點、叔叔設為黑色
• 祖父節點設為紅色
• 將祖父節點作為新節點，遞歸向上調整

Case 2：叔叔為黑且新節點是右孩子

• 以父節點為支點進行左旋
• 轉換為 Case 3 處理

Case 3：叔叔為黑且新節點是左孩子

• 父節點設為黑色
• 祖父節點設為紅色
• 以祖父節點為支點進行右旋

父節點為右孩子的情況完全對稱。

---

四、記憶技巧與口訣

三步判斷法

1. 看顏色：父節點為紅色才需要調整
2. 查叔叔：查看叔叔節點顏色
3. 辨方向：判斷新節點是左插還是右插

核心口訣

紅叔變色向上傳，
黑叔旋轉看方向；
先左后右調平衡，
黑高不變記心上。

顏色標記法

• 紅色節點：可能引發沖突
• 黑色節點：安全、穩定
• 新插入節點：總是紅色

---

五、代碼實現框架

def insert_fixup(tree, z):while z.parent.color == RED:if z.parent == z.parent.parent.left:uncle = z.parent.parent.rightif uncle.color == RED:  # Case 1z.parent.color = BLACKuncle.color = BLACKz.parent.parent.color = REDz = z.parent.parentelse:if z == z.parent.right:  # Case 2z = z.parentleft_rotate(tree, z)# Case 3z.parent.color = BLACKz.parent.parent.color = REDright_rotate(tree, z.parent.parent)else:# 對稱處理：父節點為右孩子uncle = z.parent.parent.leftif uncle.color == RED:  # Case 1'z.parent.color = BLACKuncle.color = BLACKz.parent.parent.color = REDz = z.parent.parentelse:if z == z.parent.left:  # Case 2'z = z.parentright_rotate(tree, z)# Case 3'z.parent.color = BLACKz.parent.parent.color = REDleft_rotate(tree, z.parent.parent)tree.root.color = BLACK