前言

今天要進入的章節是紅黑樹，簡單來說就是 2-3-4 Tree 對應的 Binary Search Tree (BST)，而前兩章節說過 2-3-4 Tree 是平衡的樹，因此紅黑樹可以被看作 Balanced BST

定義

1. 每個 node 不是黑就是紅
2. Root 一律都是黑色
3. Nil 也視為黑色
4. 對紅色節點來說，兩子點必為黑（即任何 Path 上不可出現連續紅色 Nodes）
5. Root 到不同 Leaf 路徑上具有相同數目之黑色 Nodes（即為 Balanced）

Insert X in R-B Tree (Top-Down)

1. Search for x 找出適當位置
2. Search 過程中若發現某一節點兩個子點為紅色，進行 Color Change 若 C.C 完後發現有連續紅色則進行 Rotation
3. 之後插入 x 且此節點必為紅色
4. 檢查有無連續紅色 Nodes，若有則 Rotation
5. Root 一律改黑色 (if needs)
   

Rotation in R-B Tree 調整

分成 4 種：LL、LR、RL、RR 和昨天所介紹的 AVL Tree 調整法則相同，這邊就不贅述了，麻煩大家往前看囉！
此外，要將中往上拉設為黑點，大小子點為紅點