平衡木（赤黒木） - Afro-Blueランダム化BSTとスプレイ木はどちらも特殊な探索が線形時間となる可能性がある。そのため、根から外部節点への距離がすべて等しくなるような木構造を考える。 2分探索木のノードに赤か黒の色をつけ、以下の条件を満たすものを赤黒木と呼ぶ ノードは赤か黒 根は黒 全ての葉は黒 赤いノードの子は黒 全ての葉から根までのパスには同じ個数の黒いノードがある 上記条件より、最短パスは黒ノードだけを含み、最長パスには赤黒が交互に含まれることになる。最短パスと最長パスが2倍を超えないようにバランスをとる。 全てのノードに赤を示す1bitを加える。 挿入するノードの親の親が黒でその子（親）が二つとも赤と赤の場合、親の親の色を赤に変更し、親二つのノードを黒にする。また親の親と親のノードが共に赤の場合、回転を使用し親の親を親の子ノードに移動、親を黒にすればよい。 詳細の説明は以下サイトが分かりやすい。 http://w
