以下の動画がとても分かりやすいです。
Red Black Treeと同じ平衡2分探索木にAVL木があります。
AVL木では、「左右部分木の高さの差は１以下」というルールを設けて、木の高さの調節を行いました。
Red Black Tree は、2分探索木のデータ構造に、赤、黒という「色」を加えたデータ構造で、この色を使うことで、木の高さを自動的に小さく維持しようとします。
以下を参照しています。
Red Black Trees (with implementation in C++, Java, and Python)
Lec 10 | MIT 6.046J / 18.410J Introduction to Algorithms (SMA 5503), Fall 2005
また、以下にはpythonの実装コードがあります。
http://wwwa.pikara.ne.jp/okojisan/rb-tree/python.html
Red Black Tree
Red Black Tree は、 2分探索木のルール以外に、以下のルールを持ちます。
- 各ノードは赤か黒の色をもつ。
- 根は黒である。
- 葉 (NIL) はすべて黒である。
- 赤のノードは黒ノードを 2つ子に持つ。（したがって、赤のノードの親ノードは黒である）。
- 任意のノードについて、そのノードから子孫の葉までの道に含まれる黒いノードの数は、選んだ葉によらず一定である（黒いノードの含まれる個数をBlack Height と考えると、Black Heihgtは一定になる）。
以下の2分探索木は、Red Black Tree になります。
Red Black Treeの高さ
要素数\( n \)のRed Black Treeの高さは \( O(\log n) \) になります。
以下で簡単に証明します。
Red Black Tree は、赤いノードをその親の黒いノードと結合することで、2-3-4木に変形することができます。
例えば、上で図示した Red Black Tree は、以下のように変形することができます。
このように変形すると、全てのノードは、2つから4つの子を持ちます。また、全てのノードの子要素は同じ高さ、Red Black Treeの規則5より、Black Height を高さとして持ちます。
葉の数は \( n + 1\) として表すことができます。
また、 2-3-4木では、高さを\( h ^ {\prime} \)とすると、葉の数は以下のように表すことができます。
$$ 2 ^ {h ^ {\prime}} \leq 葉の数 \leq 4 ^ {h ^ {\prime}} $$
よって、以下のようになります。
$$ 2 ^ {h ^ {\prime}} \leq n + 1 $$
$$ \log{_2} 2 ^ {h ^ {\prime}} \leq \log{_2} n + 1 $$
$$ h ^ {\prime} \leq \log n + 1 $$
ここで、\( h \leq 2 h ^ {\prime} \)となるので、以下のように変形できます。
$$ h \leq 2 \log n + 1 $$
Red Black Tree の高さは \( h \leq 2 \log n + 1 = O ( \log n ) \) となるので、木の構造を変えない操作（値の探索、最大値、最小値…）は、 \( O(\log n) \) で行うことができます。
Red Black Treeの操作
Red Black Treeで木の構造が変わる操作、つまり挿入と削除があった際に、木の平衡を保つための操作が必要になります。
この平衡を保つ操作は、回転と色の変更を組み合わせることで行われます。
回転
ＡＶＬ木でもあった操作です。
木を回転させることで、回転方向の部分木の高さが増え、反対方向の部分木の高さが減ので、木の平衡をとることができるようになります。
木の回転（きのかいてん、英: tree rotation）は、2分探索木の操作の一種で、要素の順序を崩さずに構造を変更するものである。木の回転は木の中の1つのノードを上にし、別のノードを下にする。木の形状を変化させるのに使い、特に大きい部分木を持ち上げて小さい部分木を下げることで全体の木の高さを低くするのに使う。それによって各種操作の性能を向上させる。
出典: フリー百科事典『ウィキペディア（Wikipedia）』
色の変更
赤と黒の色に関するルールを守るため、ノードの色の変更を行います。
赤なら黒、黒なら赤に変更します。
以下に続きます。
