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 つ減らすことができる
  - さもなければ、無駄に二重黒を減らすことになり、どこでパス上の黒ノードの数を 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 文を使用してコード量を削減している；関数封装を使用すればより標準的であるべき
[結果の例]

削除調整#

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