赤黒木
ラベルNは、入力時に削除されるノードであるカレントノードを表す。
もし、Nが根で、非NILの子を持たない場合、NはNILノードに置き換えられ、その後、木は空になり、赤黒木の形になる。
もし、Nが2つの非NILの子を持つ場合、Nの左側の部分木の最大要素(これは間順走査でのNの先行ノード)またはNの右側の部分木の最小要素(これは間順走査でのNの後行ノード)のいずれかへの追加のナビゲーションは、(ここに示すように)Nとの間に他のノードが存在しないノードを見つける。この置換ノードはRと呼ばれ、部分木の最大または最小要素として、最大で1つの非NILの子を持つ。ユーザが定義したノード構造からソフトウェアを完全に独立させるために、Nとの間のすべての赤黒い木のポインタは、Rとの間のすべての赤黒木のポインタと交換され、NのRB-colorもRに与えられる。
赤黒木は二分木の一種であり、コンピュータ科学においてテキストの断片や数(例:図1や図2の数値)などの比較可能なデータを組織化する際に用いられる。データは二分木のノードに配置され、そのうちでスタート地点となる「どのノードの子でもないノード」を根という。根は2つまでの「子」(根に接続しているノード)をもつことができる。そして、その子もまた2つまで子をもつことができ、その子も......、以下同様である。このようにして、根から、他の木内のノードへの経路ができる。
赤黒木に置ける葉(図1の NIL )はデータを持たないノードである。この葉は実際にメモリ上に置かれる必要はなくヌルポインタで表すこともできるが、独立のノードとみなしたほうがいくつかのアルゴリズムの記述が簡単になる。 また、部分木とは、木のうちある一つのノードから到達可能な部分を取り出して一つの木とみたとき、その取り出した木をいう。