赤黒木
P、S、Sの子は黒である。Sを赤にした後、Sを通るすべての経路(正確にはNを通らない経路)は、黒ノードが1つ少なくなる。ここで、Pをルートとする部分木のすべての経路は同じ数の黒ノードを持つが、Pを通らない経路より1つ少ないので、まだ要件4に違反している可能性がある。PをNにラベル付けした後、ループ不変条件が満たされるので、1上の黒レベル(=1上の木レベル)でリバランシングを繰り返すことができる。
挿入は、新しい(非NIL)ノード(Nとする)を、二分探索木における、間順走査での先行ノードのキーが新しく挿入するノードのキーより小さく、かつ新しく追加するノードのキーが後行ノードのキーより小さくなるNILノードの位置に配置することから始まる。(多くの場合、この位置は、挿入操作の直前に木内を探索した結果であり、ノード P と、P->child[dir] == NIL を持つ方向 dir で構成される。)新しく挿入されたノードは一時的に赤色となり、すべての経路に以前と同じ数の黒ノードが含まれるようにする。しかし、その親ノード(例えばP)が赤である場合、この操作は赤違反を引き起こす。
リバランシングループは以下の不変条件を持つ。
カレントノードNは、各反復の開始時に (赤)である。
要件4は、Pも赤の場合(Nで赤違反)、N←Pを除き、すべてのペア node←parent で満たされる。
他のすべての性質(要件5を含む)は、木全体で満たされている。
親PとおじUの両方が赤なら、両方を黒に塗り替え、祖父母Gを赤にすることで要件5を維持することが可能となる。親やおじを通る経路は必ず祖父母を通るので、これらの経路上の黒ノードの数は変わっていない。しかし、祖父母Gが赤の親を持つ場合、要件4に違反する可能性がある。GをNにラベル付けした後、ループ不変条件が満たされるので、1つ上の黒レベル(=2の木レベル)でリバランシングを繰り返すことができるようになる。
ケースによってノードに変更があった場合、後の状態の列グループに示される。
次の列の矢印→は、このステップでリバランシングが完了したことを意味する。後の状態の列がちょうど1つのケースとなる場合、そのケースが次のケースとして示され、そうでない場合は疑問符が示される。
ループは Start_D から削除ケース1までのセクションに含まれ、親Pが新しいカレントノードNになることで、リバランスの問題が木で Δ h = 1 {\displaystyle \Delta h=1} レベル高くエスカレートされる。そのため、木の修復には最大で h {\displaystyle h} 回の繰り返しが必要になる( h {\displaystyle h} は木の高さ)。エスカレーションの確率は各反復で指数関数的に減少するので、総リバランシングコストは平均で一定であり、実際に償却された定数になる。(ただ、余談だが Mehlhorn & Sandersが指摘している。"AVL木は一定の償却更新コストをサポートしない"これは、削除後のリバランシングには当てはまるが、AVL挿入には当てはまらない。)
ループの本体からは、ケースD3、D6、D5 + D6、D4、D2への分岐があり、削除ケース3セクションは、それ自体でケースD6、D5、D4への3種類の分岐がある。
D6とD5 + D6とD3 + D5 + D6で回転が発生するが、すべてループの外側である。したがって、最大で合計3回の回転が発生する。
カレントノードNが新しい根となる。すべての経路から1つの黒ノードが削除されたので、RB性質は維持される。木の黒高さは1減少する。