超圖解！一次搞懂演算法｜平衡樹系列

❶ 二元堆積樹的定位與平衡

• 二元堆積樹與二元搜尋樹高度相似，最適合做作為切入平衡樹系列的開頭，同 BST 有著分支數為 2 的樹狀結構。
• 二元堆積樹由於不需維持「左小右大」的規則，轉換去維持「上小下大」的關係，因此讓我們能利用此點、持續保持樹的平衡。

❶ Heap Sort 排序法

• 由「二元堆積樹」衍伸出來，透過多次的「刪除」操作，我們將能把一個數列精確排序，並有著極佳的排序效能。

❶ ＡＶＬ樹 定位與架構

• 立基於 BST，AVL樹同樣有著分支數為 2 的特性，同時加上「旋轉」的概念，讓我們能永久維持樹的平衡，保障搜尋效能。

❶ AVL 四種核心操作介紹

• Left-Left 旋轉：透過旋轉，將一側的深度轉移到另一側。
• Left-Right 旋轉：先進行小規模旋轉，調整好之後，再將一側的深度轉移到另一側。
• Right-Right 旋轉：透過旋轉，將一側的深度轉移到另一側。
• Right-left 旋轉：先進行小規模旋轉，調整好之後，再將一側的深度轉移到另一側。

❶ 2-3 樹定位與平衡：

• 2-3 樹為 B-Tree 其中一個類別，隨著我們學習平衡樹越來越深，我們樹的分支數也將隨著提高，此處每個節點開始能有 3 個分支。
• 2-3 樹將確保所有 leaf 都在同一層，藉此維持樹的平衡並保障效能。

❶ 2-3 樹 新增 ：

• 新增：2-3 樹的新增，不同於之前的樹狀結構，將會以一種「由底而上」的概念進行，並進行適當的「拆解」與「向上融合」。

❶ 2-3 樹 搜尋：

• 搜尋：2-3 樹的搜尋，由於一個節點可能有 2 個 key 值，因此搜尋時需同時進行多值判定。

❶ 2-3 樹 刪除：

• 刪除：2-3 樹的刪除，相對複雜許多，有許多細部分類，需要特別耐心的逐一理解，吸收後將能對平衡樹有更深一層認識。

❶ 2-3-4 樹 定位與平衡：

• 2-3-4 樹同為 B-Tree 其中一個類別，由 2-3 樹繼續延伸，讓每個節點開始能有 4 個分支。
• 2-3-4 將作為我們紅黑樹的前哨戰，了解 2-3-4 樹將幫助我們更順暢地進入紅黑樹單元。
• 2-3-4 樹同樣確保所有 leaf 都在同一層，藉此維持樹的平衡並保障效能。

❶ 2-3-4 樹 新增：

• 新增：2-3-4 樹的新增，同於 2-3 樹，以一種「由底而上」的概念進行，並進行適當的「拆解」與「向上融合」。

❶ 2-3-4 樹 搜尋：

• 搜尋：2-3-4 樹的搜尋，由於一個節點可能有 3 個 key 值，因此搜尋時需同時進行多值判定。

❶ 2-3-4 樹 刪除：

• 刪除：2-3-4 樹的刪除，複雜度增加，有更多細部分類，同樣需要特別耐心的一個個理解，吸收後將能對平衡樹有更深一層認識。

【壹】什麼是紅黑樹？架構與定位：

• 紅黑樹同BST，每個節點有著 2 個分支。不僅如此，紅黑樹將利用「顏色」來判斷進行平衡的時機點，掌握紅色節點對於紅黑樹的意義，是學習紅黑樹的第一步。

【貳】2-3-4 樹 & 紅黑樹 架構轉換：

• 2-3-4樹 做為學習紅黑樹的前哨戰，意義中他們是同一種架構，然而 2-3-4樹 難以用程式實作，所以我們利用紅黑樹的「顏色」概念，讓程式實作更加順暢。也是因為此原因，讓紅黑樹成為最常用的平衡樹之一。

【參】紅黑樹「新增四大規則」觀念解說：

• 新增：紅黑樹的新增，涵蓋「選轉」與「顏色」兩樣操作，同時包含四種處理狀況，彼此互相交互連結。透過詳細圖解步驟，將能有效學習紅黑樹新增概念。

【肆】紅黑樹「新增 從０到１」完整流程示範：

【捌】紅黑樹「新增 Live」實作演練：

• 我們將從全空的樹，一步步透過我們之前所學的「新增四大規則」，建立起一顆符合所有規則的紅黑樹！

【伍】紅黑樹 搜尋 觀念解說：

【玖】紅黑樹 搜尋 Live 實作演練：

• 搜尋：紅黑樹搜尋與 BST 非常相似，持續透過二分法找尋，最終獲得極佳的搜尋效能。更由於樹的永遠平衡，二元搜尋法的效能將持續保障著。

【陸】紅黑樹 「刪除八大規則」 觀念解說：

• 刪除：紅黑樹刪除有八種不同情境，需要仔細透過圖解步驟，才有辦法確切掌握。此外，不同 Case 間也會相互連結，是學習紅黑樹一個關鍵的坎，既困難也重要。

【柒】紅黑樹 「刪除 從０到１」完整流程示範：

【拾】紅黑樹「刪除 Live」實作演練：

• 我們將從一顆完整的紅黑樹，一步步透過我們之前所學的「刪除 八大規則」，將我們的樹不斷削減、直到歸為成土。

「用圖片高效學程式」臉書專頁：專頁連結

「用圖片高效學程式」YT頻道：頻道連結

「Cloud Taiwan - AWS x GCP x Azure」版主：社團連結