2 赤黒木 - Bo2SS

工学実装において非常に広く応用されている

コース内容#

<5 つのバランス条件>#

ノードは黒か赤のいずれかである
根ノードは黒である [髪の毛]
葉ノード (NIL) は黒である [足を洗わない]
1. 通常は描画しないし、NIL ノードを考慮する必要もなく、デフォルトで黒である
赤ノードの 2 つの子ノードはすべて黒である⭐
1. 赤ノードは赤ノードを持つことができない
根ノードからすべての葉ノードへのパス上で、黒ノードの数は同じである⭐

バランス条件の理解#

4 番目と 5 番目の条件 👉 赤黒木において、最長の辺のノードの数：最短の辺のノードの数 = 2 : 1
- 本質的に、赤黒木も木の高さでバランスを制御している
赤黒木は AVL 木よりも木の高さの制御条件が緩やかである
- したがって、赤黒木にノードを挿入または削除した後、調整が発生する確率は低く、調整の損失が減少する
トップ 3 条件は基本的に無意味で、好きな色に染めて、色を変えたいときは変え、NIL はデフォルトで黒である
- ❓ もし 3 番目の条件がなければ、赤黒木は強力ではなくなるのか？でもデフォルトで黒ではないのか？

調整戦略#

挿入調整と削除調整は分かれている [AVL 木とは異なる]

<重要なポイント>#

①【挿入調整は祖父ノードの視点で見る】

下に 2 層を見る
- あるノードとその子ノードが衝突した場合、あるノードは管理できない
- “隔世の親”：祖父は息子と孫のことを管理し、息子が孫を叩くことは許されない
挿入されるノードは必ず赤であり、5 番目の条件に基づく
- ❌黒を挿入する —— 必ず調整が発生する [必ずあるパス上の黒ノードの数が変わる]
- ✅赤を挿入する —— 調整が発生する可能性がある
[挿入調整の目的] 二重赤の状況を解決する

②【削除調整は親ノードの視点で見る】

下に 1 層を見る
発生の前提
- 黒を削除する [二分探索木の削除を参照]
  - 度数 0⭐：特例 [NIL が機能する]
    - 二重黒の NIL ノードが発生する
    - 削除調整を引き起こす
  - 度数 1
    - 唯一の子供は必ず赤である。さもなければ、そのノードは必ず別のサブツリーを持ち、左右の黒ノードの数を等しく保つ必要があり、度数 1 と矛盾する
    - 削除調整は発生しない
  - 度数 2：度数 0 または 1 の状況に変換できる
- 赤を削除する：バランス状態に影響しない
[削除調整の目的] 二重黒の状況を解決する

--> 合計5 つの状況：挿入 2 つ + 削除 3 つ

⭐重要なポイント⭐ —— 一般的な調整戦略
- 各状況を、大きな赤黒木の局所的なサブツリーとして想像する
  - 根ノードには「先祖ノード」があり、他のノードにはサブツリーがある可能性がある
- 全体に影響を与えないために、局所的なサブツリーの黒ノードの数は調整前後で等しい
- [以下の各状況は木の一部のみを示している]
[PS] 根ノードが黒でない場合、色を染めるだけで済む [重要ではない]

挿入調整#

[目標] 二重赤の状況を解決する

2 つの大きなカテゴリ：4 + 4 の小状況

状況一#

【特徴】叔父ノードが赤である
【戦略】
- 三元組 <15 [1, 20]> の小さな帽子を変更する
  - 黒赤赤👉赤黒黒：祖父が父たちの赤い帽子を奪う
  - 各パスの黒ノードの数を変えないことを保証する
【図示】赤が上昇する
[PS]
- [図中] 根ノードの色は必ず黒である。さもなければ、挿入前に根ノードと子ノードが衝突し、不均衡になる
- 4 つの小状況を含む：挿入ノードxは 4 つの位置を持つことができるが、処理方法は一貫している

状況二#

例：LL

【特徴】叔父ノードが黒で、LL で衝突が発生する [2 つの赤ノードが L と LL にある]
【戦略】
- まず AVL 木の回転調整戦略を使用する：LL [例]、LR、RL、RR
- 次に三元組の色を変更する：赤が上昇する [赤黒黒] または赤が下降する [黒赤赤]
【分析】図中 <LL 型の不均衡>、どのノードが確定している [存在 + 色] のか？どれが特例か？
- 確定 [青い枠で囲まれた]
  - LL 型 → 10、15
  - 状況二 → 25
  - 15 は赤である → 20
  - 各パスの黒ノードの数は同じである [2 つ] && 10、15 は赤である → 5、13、19
  - [PS] 4 つの黒ノードはすべて NIL でも良い
- 特例
  - 17
    - 赤である可能性がある
    - 無くても良い、黒でも良い [ただし、図に含めることはできない。さもなければ 5 番目の条件を満たさない]
【図示】大きな右回転 + 赤が上昇 / 下降する
- LL 型が大きな右回転後、黒ノードの数の変化により不均衡が発生👉[赤が上昇 / 下降する] 調整を使用
[PS]
- 2 つの赤ノードの回転に対して、各パス上の黒ノードの数には影響を与えない
  - 小さな左回転、小さな右回転に対して
  - 例：[元の図を仮定] 15 号ノードを持って小さな右回転を行う
  - したがって、小さな回転はバランスに影響を与えない
- ❗ 挿入ノードxの位置は回溯調整の中間結果であり、直接挿入後の姿ではない
- 4 つの小状況を含む：LL、LR、RL、RR

削除調整#

[目標] 二重黒の状況を解決する

2 つの大きなカテゴリ：兄弟ノードが黒である [2 + 2 + 2 の小状況]、兄弟ノードが赤である [特例]

状況一#

例：右側に二重黒の子ノード

【特徴】二重黒ノード x の兄弟ノードは黒であり、兄弟ノードの 2 つの子ノードも黒である
【戦略】親ノードに 1 重の黒を追加し、二重黒ノードと兄弟ノードの 1 重の黒を減少させる
[PS] 95 は回溯から来たものである [問題を見る視点を広く持つべき]

状況二#

例：RL

[二重黒ノード x の位置を注意深く観察し、38 が根ノードの子ツリーであることに注目]
【特徴】兄弟ノードは右側にあり + 兄弟ノードの左子ノードは赤で、右子ノードは必ず黒である [さもなければ RR 型と見なされ、後で説明]
【戦略】小さな右回転、元の兄弟ノードを赤に変更し、新しい兄弟ノードを黒に変更し、RR 型に変換する [状況三を参照]
【分析】どのノードの色が確定しているのか？[小さな右回転部分]
- [元の図を参照し、青い枠で囲まれた部分が確定した色]
- RL 型 → 72、51、85
- 根が 38 の子ツリーの各パスの黒ノードの数は同じである [2 つ] && 51 は赤である → 48、64

状況三#

例：RR

[二重黒ノード x の位置を注意深く観察し、38 が根ノードの子ツリーであることに注目]
【特徴】兄弟ノードは右側にあり + その右子ノードは赤である [左子ノードには要求なし]
【戦略】大きな左回転を行い、新しい根ノードは元の根ノード [二重黒ノードの親ノード] の色とし、2 つの新しい子ノードを黒に変更し、二重黒ノードの 1 重の黒を減少させる [この順序には特に意味はない]
【分析】どのノードの色が確定しているのか？
- [元の図を参照し、青い枠で囲まれた部分が確定した色]
- RR 型 → 28、 51、72
- 各パスの黒ノードの数は同じである [≈2 つ、38 は不確定] && 72 は赤である → 64、85
- [PS] 38、48 は不確定
【考察 1】色変更戦略
- まず48が赤である可能性があるため、衝突を避けるために❗、38 を黒に変更する必要がある
- 次に、局所的なサブツリーの黒ノードの数が調整前後で等しくなることを保証する
- ① [2 つ] もし 38 が元々赤であれば → 51 を赤に変更し、72 を黒に変更する
- ② [3 つ] もし 38 が元々黒であれば → 72 を黒に変更する
- 【一般的な方法】新しい根ノードは元の根の色とし、新しい子ノードはすべて黒に変更する
  - 黒赤赤👉赤黒黒
  - (または)
  - 黒黒赤👉黒黒黒
【考察 2】なぜ左回転で二重黒を解決するのか？
- 大きな左回転後、二重黒が存在するパス上に黒ノードが 1 つ増える [51 の追加] ため、二重黒を 1 つ減らすことができる
  - さもなければ、無駄に二重黒を減らすことになり、どこでパス上の黒ノードの数を増やすことができるのか

状況二、三の小結

状況二：RL、LR；状況三：RR、LL
二重黒ノードの兄弟ノードは黒であり、兄弟ノードの中に赤い子ノードがある
- RR[兄弟ノードは右側にあり ➕ その右子ノードは赤である]
  - 大きな左回転を行い、新しい根を元の根の色に変更し、新しい根の 2 つの子ノードを黒に変更する
- RL[兄弟ノードは右側にあり ➕ その左子ノードは赤で、右子ノードは必ず黒である]
  - 小さな右回転を行い、元の兄弟ノードを赤に変更し、新しい兄弟ノードを黒に変更し、次に RR 戦略を行う
- LL、LR：RR、RL と同様
優先順位：RR > RL、LL > LR

特殊な状況#

【特徴】二重黒ノードの兄弟ノードは赤である
【戦略】二重黒ノードの親ノードを持って、二重黒ノードに回転し、元の根ノードを赤に変更し、新しい根ノードを黒に変更する
【図示】大きな左回転 + 元 / 新根ノードの色を変更する
- 青い枠は確定した色のノードであり、どのように確定したのか？
  - 特殊な状況 → 二重黒ノード、兄弟ノード
  - 4 番目の条件 && 兄弟ノードは赤である → 親ノード
  - 5 番目の条件 && 兄弟ノードは赤である → 兄弟ノードの子ノード [それ以降の黒ノードの位置は必ずしも連続している必要はない]
【変換後】元の根ノードから下を見て、削除調整を行う
- この時、二重ノードの兄弟ノードは必ず黒であり、状況一、二、三に移行できる

コードデモ#

挿入調整#

根ノードの手動での黒染め
- 2 番目の条件を保証する：根ノードは黒である
- どのような場合に根ノードが赤になるか
  - 挿入された最初のノード [挿入されたノードは赤である]
  - 状況一の赤が上昇する
  - 状況二の赤が上昇する [赤が下降する場合は影響しない]
- ❗ 手動での黒染め操作のみが、パス上の黒ノードの数を増加させる
  - 根ノードで大きな回転操作が発生する場合、根ノードは赤ノードに変わり、この時手動での黒染めが有効になる
- コードを通じて処理を封装する：insert = __insert + 黒染め
❓ 状況一の手抜き操作が回溯時の調整に影響を与えるか？
- 下のパスに衝突を引き起こさない
- パスの黒ノードの数に影響を与えない
- 上位ノードに衝突を引き起こす可能性がある
  - しかし、元々はランダムな操作であり、赤黒木が一定の規模に達すると、損失は無視できる
❓ 赤が下降することと赤が上昇することの違い：それぞれに利点があり、衝突の可能性がある
- 赤が下降する：新しく挿入されたノードと衝突しやすい
- 赤が上昇する：親ノードと衝突しやすい
  - [PS] 赤黒木が非常に大きい場合、赤ノードが上昇するのは難しい
❓ AVL 木と赤黒木
- AVL 木は赤黒木よりもバランスが取れている
- 赤黒木の調整のコストは AVL 木よりも低い
  - 赤黒木の約半分の調整は染色で解決できる [状況一]
- 動的な挿入と削除ノードに適しているが、検索は AVL よりもやや劣る可能性がある
[PS]
- 挿入調整は、再帰の回溯段階で発生する
- 挿入調整のコードでは、goto 文を使用してコード量を減らしている；関数を封装する方が標準的であるべき
[結果の例]

削除調整#

挿入調整コードの基礎の上に追加する
削除調整の状況は【二重黒の子ノードがない】+【二重黒の子ノードがある [特例 + 兄弟ノードに赤い子ノードがない / ある <LR、LL、RL、RR>]】に分かれる
状況二、三では、二重黒の問題を解決することを忘れず、順序には特に意味はない
LR / RL タイプの判断を行う際、LL サブツリーが黒であるかどうかを直接判断してはいけない
- 黒である可能性もあれば、二重黒である可能性もある
- [二重黒] LL が NIL ノードである可能性があり、NIL ノードはメモリで共有されているため、その色は二重黒である可能性がある
- 【判断の変化】LL サブツリーが黒であるかどうかを判断する 👉赤でない
main 関数に削除操作を追加する
[結果の例]
- 3 つの状況を示し、結果はリストに示される
- NIL はメモリで共有されているため、すべて二重黒である可能性がある