赤黒木
アカウントの画像が赤いから連想するんだと思う
データ構造を保存する空間がサイコーに効率が良い
平均 & 最悪: $ \mathcal O(n)
探索・挿入・削除がめちゃ速い
探索
平均 & 最悪: $ \mathcal O(\log{n})
挿入・削除
償却: $ \mathcal O(1)
最悪: $ \mathcal O(\log n)
同様の特長を持つデータ構造に AVL木 があるが、 AVL木よりも制約条件がゆるいので、
制約条件を満たすために修正するコストが少ないのが強み
動的に変化させることが多い (挿入削除が多い) 場合は赤黒木
静的に構築する場合はAVL木がよい
https://scrapbox.io/files/65c816328c917e0025f7d66b.svg
code:rb-tree.tikz(tex)
\begin{document}
\begin{tikzpicture}
\tikzset{
level/.style={sibling distance=60mm/#1},
every node/.style={draw,circle,font=\Large},
% blackやwhiteにしてしまうと、color scheme切り替え設定に上書きされてしまうので、似ている色に変えた
b/.style={fill=black!90,text=black!10},
r/.style={fill=red,text=black!10},
nil/.style={rectangle,font=\small}
}
}
}
}
}
}
}
}
}
};
\end{tikzpicture}
\end{document}
重なりをなくしたいtakker.icon
制約条件
0. 二分探索木である
1. 各ノードは赤か黒の色をもつ
2. 根は黒
この条件はしばし省かれる。
根は赤から黒に変えることはできるので、解析にはほとんど影響しない
3. 葉 (NIL) はすべて黒
葉はすべて根と同じ色
4. 赤のノードは黒ノードを2つ子に持つ
したがって、赤のノードの親ノードは黒
これを満たさない場合は赤違反、満たす場合は赤遵守と呼ぶことにする 5. 任意のノードについて、
そのノードから子孫の葉までの道に含まれる黒いノードの数は、選んだ葉によらず一定
この条件は、「根から葉までの道に含まれる黒いノードの数は、葉によらず一定」と言い換えることができる
$ \implies 根から葉まで道で最長のものの長さは、根から葉までの道で最短のものの長さの二倍を超えない
ちなみにこの制約条件をよく読むと、
全部のノードが黒であっても条件を満たすことが分かる
これはAVL木である、と思うSummer498.icon
なので、赤黒木はAVL木の条件をゆるくしたものと言える
計算量の証明
検索は二分探索木の計算量になる
この際に赤黒木の制約から導かれる性質を利用して最悪計算量が$ \mathcal O(\log n)で済むことを示す
挿入削除の際に赤黒木特有の操作が$ \mathcal O(\log n)で済むことを示す
木の回転
計算量が$ \mathcal O(\log n)であること
木の回転が挿入・削除で 3 回以内になること
色の変更: 定数 (しかも非常に速い)
操作
つまり、$ \mathcal O(\log n)で検索ができる
また、挿入削除するべきノードを検索で特定できる
ここでは、挿入や削除の直後に制約条件を満たすために修正する (平衡化) 過程に着目する
カレントノード「自身」は各反復の開始時に赤黒木.赤.icon(赤)である
要件4「赤のノードは黒ノードを2つ子に持つ」は
親も赤の場合 (自身と親との間で赤違反) の (自身, 親) をのぞき、全ての組 (node, parent) で満たされる (赤遵守) 他のすべての性質は木全体で満たされる
挿入時に起こり得る6ケース
table:挿入時のケースと、処理後の結果一覧
前 の 状 態 後 の 状 態
ー ー ー ー ケース 回転 割当 ー ー ー ー → Δh
親 祖 叔 X → 父 祖 叔 X 次
父 父 親 父 父
ー I3 →
赤黒木.黒.icon I1 →
赤黒木.赤.icon ー I4 赤黒木.黒.icon →
赤黒木.赤.icon 赤黒木.黒.icon 赤黒木.赤.icon I2 自:=祖 ？ ？ 2
赤黒木.赤.icon 赤黒木.黒.icon 赤黒木.黒.icon i I5 親↶自 自:=親 赤黒木.赤.icon 赤黒木.黒.icon 赤黒木.黒.icon o I6 0
赤黒木.赤.icon 赤黒木.黒.icon 赤黒木.黒.icon o I6 親↷祖 赤黒木.黒.icon 赤黒木.赤.icon 赤黒木.黒.icon →
なお、この表で祖父、叔父という表現を用いているのは、単に原文で uncle (叔父) が使われていたことに合わせているだけである
親は祖父の左右どちら側にも存在しうる
自身(自)はカレントノード
挿入ノードはカレントノードだが、操作を進めると他のノードがカレントノードになる可能性もある
表で、
前の状態の列グループはケースを定義し、記号をケース列で割り振る
空欄セルの値は無視 (don't care)
例: I4 の場合、叔父ノードの色は自由(両方の可能性をカバーする)
x 列は子の向きの変化を表す
o (outer) は親と自身が共に左または共に右の子であることを意味し
i (inner) は祖父から親の方向が親から自身への方向と違うことを意味する
回転の列は、回転が平衡化に寄与しているかどうかを表す
割当の列は、後続ステップに入る前に自身への割当 (ポインタの繋ぎ変え) が行われることを示す
他のノード親、祖父、叔父にも同様に再割り当てが行われる可能性がある
後の状態の列グループは、ノードに変更があった場合の変更後の状態を示す
次の列の矢印は、このステップで平衡化が完了したことを意味する
$ \Delta hは操作後に(再割当後の)自身が元の自身と比べてどこの高さに要るのかを示す
計算量解析に用いる
些細なケースの説明
挿入ケース1
ループ不変条件により他の要件 (特に要件5) も成立
よって、何もせずに終了できる
挿入ケース2
両方を黒に塗り替え、祖父を赤にすることで、
親や叔父を通るルートは必ず祖父も通るので、
これらの経路上の黒ノード数が変わらない
自身に祖父を割り当てて次のループへ
挿入ケース3
自身が根である場合、
親が居ないため赤遵守、ループ不変条件により他の要件も成立 よって何もせずに終了できる
挿入ケース4
親は根なので勝手に塗り替えてよい
また、この際に木の黒高さが1増える
込み入ったケースの説明
挿入ケース5
親が赤、祖父が黒、叔父が黒の場合
木の形が悪い(inner)ので、I6 に向けて変形する
自身が親の右子であれば、親を根とする部分木を左回転する
―――――左子であれば、――――――――――右回転する
と、祖父から見た時の子の向きが outer になる
また、自身と親の親子関係が入れ替わっただけなので赤違反のままである 自身に親だったものを割当、親に自身だったものを割当て I6 へ
挿入ケース6
親が赤、祖父が黒、叔父が黒の場合
木の形が良い(outer)ので、そのまま回転して整理できる
親が祖父の右子であれば、祖父を根とする部分木を左回転する
―――――左子であれば、―――――――――――右回転する
叔父(今は祖父の子になっている)が黒なので、親ー祖父ー叔父の間で赤遵守 ゴシップ話
このデータ構造は1972年のルドルフ・ベイヤー (en:Rudolf Bayer) の発明である"symmetric binary B-trees"が元となっており、
赤黒木という名前自体は 1978年にレオニダス・ギッバス (en:Leonidas J. Guibas) とロバート・セジウィック (en:Robert Sedgewick) によって発表された論文による。
赤黒木は英語では red-black tree だが、 略すと発明者のイニシャルと同じ RB木になる
これ好きSummer498.icon
ランダウのO記法のOは$ \cal Oではなく$ \Omicronらしい要出典takker.icon それ思った。しかしなんでたまに$ \mathcal Oで書く人がいるのだろう？Summer498.icon
なお、私が$ \mathcal Oを使ってるのは参照元 Wikipedia が使ってるから
$ \cal Oのほうがかっこいい気がするtakker.icon
フーリエ変換$ \mathcal Fのように、関数を受け取って関数を返す高階関数(変換)だから$ \mathcal O を使うという説明付けを思いついたSummer498.icon
あとちゃんと\Omicronにしてて偉いえらい！.iconSummer498.icon
上界が$ \Omegaで下界が$ \Omicronなのではnishio.icon
と思ったがもっと複雑だった