C# 資料結構 - 紅黑樹刪除操作完整解析 (上)(6)

3.2.3 黑兄紅侄 - 四種旋轉情形

若兩個侄子皆為紅：情形 1/2 優先 LL 旋轉，情形 3/4 優先 RR 旋轉。

紅黑樹程式碼實作心得

SortedDictionary 底層使用紅黑樹，但 TreeSet 採用預先旋轉/著色的新演算法 (預平衡)，插入/刪除前預先調整避免回溯。作者質疑此法在「未命中目標」 (插入重複鍵、刪除不存在鍵) 時產生無用功，決定自行實作傳統回溯式紅黑樹，使用固定長度 64 陣列記錄路徑。重寫過程中遺失刪除代碼但快速重寫並改進，最終完成。