修復次數：0
節點數：0
紅色／深灰填色 = 節點本身的顏色（紅黑樹的核心資訊，恆常可見不受高亮遮蔽）；
藍色外框（current）= 當前正在檢查的節點 z；黃色外框（frontier）= 本步涉及的父／叔／祖父節點；
節點上方文字為「紅」/「黑」文字備援（與填色同步）。
本幀修復類型（caseOf）
—
普通二元搜尋樹有個毛病：照順序插入時會退化成一條鏈，查一筆要走 n 步、跟沒建樹一樣慢。紅黑樹和 B 樹 都是為了「不管你怎麼插，樹都不會長歪」而生，查詢永遠只要約 log n 步。差別在手段：紅黑樹像給每個節點 貼「紅／黑」標籤，靠幾條著色規則自動把樹壓平，適合擺在記憶體裡；B 樹則讓一個節點裝好幾個鍵、長得又寬又矮， 每個寬節點剛好對應一次硬碟讀取——所以資料庫和檔案系統的索引幾乎都用它。下面你會看到紅黑樹插入後怎麼靠 重新染色 + 旋轉修復，以及 B 樹在節點塞滿時怎麼分裂。
兩者都保證 O(log n)，但換取平衡的手段完全不同：紅黑樹靠「節點顏色 + 五性質（尤其黑高相等）」在二元樹上 維持近似平衡，插入後可能觸發重染色或旋轉修復；B 樹（本頁 t=2，即 2-3-4 樹）則放棄二元限制，讓每個節點 容納多個鍵（1~3 鍵），插入時預防性地把已滿節點分裂、中鍵提升，換取「樹更寬、更矮」——寬節點正好對應 一次磁碟頁讀取，是資料庫索引/檔案系統偏好 B 樹而非紅黑樹的原因。
insert(value) 先做標準 BST 插入，新節點一律先染紅（不影響黑高）；若父節點也是紅色，違反「性質4：不可連續紅」， 需呼叫 insertFixUp 向上修復：case1（叔叔是紅色）→ 父/叔重染黑、祖父重染紅，把檢查點上移至祖父繼續； case2→case3（叔叔是黑色，且 z 為內側子）→ 先旋轉一次把 z 轉為外側子，再走 case3；case3（叔叔是黑色， z 本為外側子）→ 父變黑、祖父變紅，對祖父做反向旋轉。迴圈結束後根節點強制設黑（性質2）。
insert(key) 下探前先檢查根節點是否已滿（3 鍵）：若滿，建立新根、把舊根當第一個子節點，先分裂舊根（樹高 +1）。 insertNonFull(node, key) 下探時，內部節點先比較 keys[] 找出應進入的子節點索引；若該子節點已滿（3 鍵）， 先呼叫 splitChild 預防性分裂：中間鍵提升到父節點、右半部搬到新建節點，原節點只保留左半部；分裂後再依 key 與提升鍵比較決定實際遞迴方向。到達葉節點且未滿時，直接在正確位置插入（鍵值右移騰出空間）。 t=2 時每節點鍵數上限為 2t-1=3，下限（非根）為 t-1=1。