赤黒木
赤黒木の構造の視覚化をしてくれるツール。
Red/Black Tree Visualization
赤黒木にもバリエーションがあるらしいけど、プログラミングの基礎の赤黒木と同じアルゴリズムを使った赤黒木の説明。 Red-Black Trees in a Functional Setting
木構造とハッシュ―平衡二分探索木「赤黒木」で知る豊かなデータ型（山本さんのやつ）
浅井本の赤黒木
それ以外の赤黒木の説明。
Red-Black Trees
Red-black tree / Wikipedia
Open Data Structures
「みんなのデータ構造」のオープンソース版
数としての赤黒木
挿入の手順
(1) 空のツリーへ「1」を挿入
黒の1が挿入される
https://gyazo.com/8aad1a9d55a95c26e2edfc8744c47a7f
(2) 上のツリーに「2」を挿入
赤の2が挿入される
https://gyazo.com/342e6af927f9dfaa43044e4eb4c8c609
(3) 上のツリーに「3」を挿入
赤の3が挿入されて...
https://gyazo.com/e3adf955602edf802d6b56d0867d8b4f
リバランスされて以下の形になる
https://gyazo.com/f7ffb627d2e65f114183f8c9634c5068
(4) 上のツリーに「4」を挿入
赤の4が挿入されて...
https://gyazo.com/6e9012169a994c7a1096904144bc20a6
Uncleノードが赤いのでCase 2bのリカラリングとなり、祖父ノードから黒を下ろしてくる
https://gyazo.com/bc69dcfc103e3d03b5125bead4601b08
ルートが赤いので黒にする
https://gyazo.com/2b6fda1482f9a1c6f6121094ebf8360e
（省略）
(8) ツリーに8を挿入
https://gyazo.com/195f684b11f8699d84db866f33ba5646
Uncleノードが赤いのでリカラリング、祖父ノードから黒を下ろしてくる
https://gyazo.com/32593a27d26c8489310429019f30caca
4と6とで赤ノードが続いているので、シングルローテーションでリバランスする
https://gyazo.com/c0f4c691fd72b013617b06c3d1a7406d
謎の力が働いて以下のようになった...
https://gyazo.com/1970c5e10087ecd1b533da831f3d94d2