赤黒木は、それぞれのノードが赤もしくは黒であり、根からそれぞれの葉までのパスが同じ数の黒ノードを持ち、1つの列に赤ノードが2つ連続しないような二分木として定義されます。明確に、赤黒木の最も長いパスの長さはその木の最も短かいパスの長さの2倍が限界です。したがって、赤黒木は平衡木の一種です。[rbtree]//木の色は、その木が空であれば根ノードの色は黒になります。要素を持つような赤黒木を表わします。はじめに赤ノードの連続を許すような色の違反を含む中間生成の木をコンストラクトする必要がしばしばあります。それからそのような違反を修正するために木を回転させるのです。色が違反するようなどんな中間生成した木にも型を割り当てられないのです。0)//1つの列における2つの赤ノードの発生を1つの色違反として数えましょう。回の色違反を含む木を表わします。色違反のない有効な赤黒木です。なくてはいけないことが分かります。[insfix_r]これで赤黒木への挿入を実装する準備が整いました。与えられた赤黒木に要素を挿入した木は常に有効な赤黒木であることを保証するような、挿入の実装できます。呼び出して得られる木が常に黒であることも示しています。割り当てれらた型が、赤黒木にへの挿入方法について形式的な説明を事実上与えていることに注意してください。このアルゴリズムの内部構造についてほとんど理解していない疑似コードとして書かれたアルゴリズムを単に頼って、多くのプログラマは赤黒木を実装します。その関数が常に与えられた赤黒木の黒高さを管理できているか、判断できるプログラマはほとんどいないでしょう。木の値が赤になった場合、色違反のある木を作ってしまうかもしれません。この不変条件は赤黒木の挿入アルゴリズムとしてよく知られたものと本質的に同じです。与えられた赤黒木に要素が含まれていたら、上記で実装した挿入操作はその要素を挿入しません。そのような場合、呼び出し元に知らせた方が望ましいかもしれません。この目的のために例外を発生させることもできます。引数を与えて、挿入しようとした要素が実際に挿入されたのか示すフラグを返す方法があります。それがどのようにサポートされているのか解説します。2分探索木の要素の削除を実装するのは挿入よりもきわめて難しいことがあります。これは赤黒木において特に顕著です。ライブラリをおすすめします。