赤黒木
カレントノードNは青い枠で囲まれ、他のノードはNとの関係によってラベル付けされている。 回転が有効であると判断された場合は、次の動作は "rotate" とラベル付された絵となる。 再色付けが有効であると判断された場合は、次の動作は "color" とラベル付された絵となる。 まだ修復の必要がある場合、ノードの集まりは、新たに割り当てられたカレントノードNで挿入または削除のループ不変条件を満たし、再び青枠を持つようになる。また、Nに対して他のノードが新たに割り当てられる可能性もある。この動作は "reassign "とラベル付けされている。その後に続く動作は、他のケースのコードを再利用し、根に1つ近い黒レベルの反復となることもある。
番号が書かれた黒丸を頂点とする三角形()は、赤黒木の部分木(要件4に従ってその親に接続)を表し、黒高さは反復レベルから1を引いた値に等しい。つまり最初の反復では0である。その部分木の根は、赤でも黒でもよい。番号が書かれた三角形()は、黒高さが1つ少ない赤黒木の部分木を表し、すなわちその親は2回目の反復で黒高さが0になる。
兄弟ノードSは赤だから、PとおいのCとDは黒でなければならない。Pでdir-回転すると、SがNの祖父母ノードになる。そして、PとSの色を反転させても、Nを通る経路は黒ノードが1つ少ないままである。しかし、Nは赤の親Pと黒の兄弟Sを持っているので、ケースD4、D5、D6の変換で赤黒木の形を復元することができる。
カレントノードの親Pは黒であるから、要件4が成立する。ループ不変条件により、要件5も成立する。
親Pは赤だが、おじUは黒。最終的な目標は、親ノードPを祖父母の位置に回転させることだが、NがGの内側の孫の場合(つまり、NがGの右子の左子またはGの左子の右子の場合)、これはうまくいかない。Pでdir-回転を行うと、カレントノードNとその親Pの役割が入れ替わる。この回転により、Nを通る経路(図中の2の部分木)が追加され、Pを通る経路(図中の4の部分木)が削除される。しかし、PもNも赤なので、要件5は維持される。要件4はケース6で復元される。