C# 資料結構 - 紅黑樹插入操作與旋轉類型 (上)(2)

紅黑樹旋轉操作

同 AVL：LL、RR、LR、RL 四種。差別在旋轉後調整節點顏色而非平衡因子。動畫參考 AVL 文章。

插入操作核心概念

• 新節點初始顏色為紅色 (插入黑會增加黑高度破壞平衡)
• 若父節點為紅，違反「不得有相鄰紅節點」，需調整

術語定義

• 「新」：新插入節點
• 「父」：新節點父節點
• 「叔」：父節點兄弟節點
• 「祖」：父節點父節點
• 藍色箭頭指向「判定點」 (每次不平衡判斷起點)

插入分類

1. 黑父

父為黑，插入紅不影響平衡，直接結束。

紅黑樹優勢：黑父情況常見，旋轉機率低於 AVL。

2. 紅父

父為紅，祖必為黑。依叔父顏色分兩種：

2.1 紅叔

無需旋轉：父/叔染黑、祖染紅。若祖父為紅，以祖為新判定點向上繼續平衡。操作與「父」在「叔」左/右、「新」為左/右孩子無關。