赤黒木
ノード間の順序関係は、NとR間の順序(Nを除去することによって直ちに解決する問題)を除いて保存され、Nは最大1つの非NILの子を持つ。
もし、Nがちょうど1つだけ非NILの子を持つなら、Nの子は赤でなければならない。もしNの子が黒なら、要件5によって2つ目の黒の非NILの子が強制されるからである。
もし、Nが赤のノードである場合、非NILの子を持つことはできない。なぜなら要件4によりNの子は黒でなければならないからであり、さらに、先ほどの議論と同様に、黒い子を1つだけ持つことはできない。その結果、赤のノードNは子を持たず、単に削除されるだけである。
もし、Nが黒ノードであれば、1つの赤の子ノードを持つか、非NILの子ノードを全く持たない場合がある。Nが赤の子ノードを持っている場合は、赤の子ノードを黒く塗った後、その子ノードとNを置き換えるだけである。
すべての赤黒木は単純な二分探索木の特殊なケースであるため、赤黒木に対する探索や木の走査などの読み取り専用操作は、二分探索木で使われるものと何の変更もない。しかし、挿入や削除の直後は赤黒木の性質に反する場合があるため、これを修復して赤黒木を平衡にすることをリバランシングという。操作における最悪時間計算量は、O記法で O ( log  n ) {\displaystyle {\mathcal {O}}(\log n)} ( n {\displaystyle n} は木の要素数)、平均では、 O ( log  n ) {\displaystyle {\mathcal {O}}(\log n)} または償却された O ( 1 ) {\displaystyle {\mathcal {O}}(1)} 、色の変更には定数(実際には非常に速い) と小さい数になり、木の回転は3回以内(挿入は2回)となる。
挿入と削除の操作の詳細は、例としてC++のコードを用いて説明する。サンプルコードでは、以下の型定義とマクロ、および回転のためのヘルパー関数を使用する。
この提案では、挿入と削除(非常に単純なケースを除く)の両方を、ノード、エッジ、カラーの6つの組合せで分解し、ケースと呼ぶことにする。ケースを修復(リバランシング)するコードは、後続のケースのコードを使用することがある。この提案では、挿入と削除の両方について、根とループに黒レベルを1つずつ近づけるケースを正確に含み、他の5つのケースはそれ自体で木をリバランシングする。より複雑なケースは、図に描かれる。
変数 N はカレントノードを表し、図中では N と表される。
は赤ノードを、 は(黒高さ ≥ 1 の)非NILの黒ノードを表し、(非NIL)ノード は赤・黒ノードのどちらでも良いが、同じ図の中では同じ色である。真のNILノードは図に描かれない。
図には3つの列と2~4つのアクションが含まれる。 左の列は最初の反復を、右の列はそれ以上の反復を、中央の列は1つのケースを異なるアクションに分割したものを表す。 動作 "entry" は、ケースを定義するノードの集まりとその色を示し、ほとんどの場合、いくつかの要件に違反している。