赤黒木
図表において、PはNの親、GはNの祖父母、UはNのおじを表す。
図では、PはGの左の子として表されているが、Pは左右どちら側にも存在する可能性がある。サンプルコードでは、サイド変数 dir によって、両方の可能性をカバーしている。
Nは挿入ノードであるが、操作を進めると他のノードもカレントノードになる可能性がある(ケースI2を参照)。
図で、PがNと同じく赤色の場合は、赤違反であることを表している。
x列は子の向きの変化を表し、o(外側)はPとNがともに左またはともに右の子であることを意味し、i(内側)はPからNへの方向がGからPへの方向と違うことを意味する。
前の状態の列グループはケースを定義し、その名前がケースの列で与えられる。そのため、空欄のセルの値は無視される。したがって、ケースI2の場合、対応する図ではNの子方向は1つだが、サンプルコードでは両方の可能性をカバーしている。
一覧表の行は、すべての可能なRBケースをカバーし、理解しやすいように並べられている。
回転の列は、回転がリバランシングに寄与しているかどうかを示す。
割り当ての列は、後続のステップに入る前にNへの割り当てが行われることを示す。これにより、他のノードP、G、Uも同様に再割り当てが行われる可能性がある。