赤黒木のソースを表示

{{Infobox data structure
|name=赤黒木
|type=[[木構造 (データ構造)|木構造]]
|invented_by=[[:en:Rudolf Bayer]]
|invented_year=1972
|space_avg=<math>\mathcal{O}(n)</math>
|space_worst=<math>\mathcal{O}(n)</math>
|search_avg=<math>\mathcal{O}(\log n)</math><ref name="wiscurl">{{cite web | url=http://pages.cs.wisc.edu/~paton/readings/Red-Black-Trees/ | title=Red–Black Trees | author=James Paton | accessdate=2021-12-22}}</ref>
|search_worst=<math>\mathcal{O}(\log n)</math><ref name="wiscurl"/>
|insert_avg=[[償却解析|償却された]] <math>\mathcal{O}(1)</math><ref name="InfoBU">リバラシングのみ (検索は無し)、[[#amortized|Tarjan and Mehlhorn]]を参照。</ref>
|insert_worst=<math>\mathcal{O}(\log n)</math><ref name="wiscurl"/>
|delete_avg=[[償却解析|償却された]] <math>\mathcal{O}(1)</math><ref name="InfoBU"/>
|delete_worst=<math>\mathcal{O}(\log n)</math><ref name="wiscurl"/>
}}

'''赤黒木'''（あかくろぎ）は、[[コンピュータ科学]]の[[データ構造]]である[[平衡2分探索木|平衡二分木]]の一種で、主に[[連想配列]]の実装に用いられている。'''2色木'''、'''レッド・ブラック・ツリー'''ともいう。

このデータ構造は[[1972年]]のルドルフ・ベイヤー ([[:en:Rudolf Bayer]]) の発明である"symmetric binary B-trees"が元となっており、赤黒木という名前自体は [[1978年]]にレオニダス・ギッバス ([[:en:Leonidas J. Guibas]]) とロバート・セジウィック ([[:en:Robert Sedgewick (computer scientist)|en:Robert Sedgewick]]) によって発表された論文による。

赤黒木は、探索、挿入、削除などの操作における最悪[[計算理論|時間計算量]]が[[O記法|O]](log ''n'')（''n''は木の要素数）と短く、複雑ではあるが実用的なデータ構造として知られている。

この日本語版は概要のみの解説であり、具体的なアルゴリズムはwikipedia英語版([[:en:Red-black_tree|Red-black_tree]])に掲載されている。

== 用語 ==
{{Multiple image
|direction= vertical
|header=赤黒木の例
|state=expanded
|width=500
|image1=Red-black tree example.svg
|caption1=図1: 明示的な葉(NIL)を持つ赤黒木
|image2=Red-black tree example with sockets.svg
|caption2=図2: 左右の暗黙のドッキングポイントを持つ赤黒木
}}
赤黒木は[[二分木]]の一種であり、[[コンピュータ科学]]においてテキストの断片や数（例:図1や図2の数値）などの[[比較]]可能な[[データ]]を組織化する際に用いられる。データは二分木の[[頂点 (グラフ理論)|ノード]]に配置され、そのうちでスタート地点となる「どのノードの[[子]]でもないノード」を[[根]]という。根は2つまでの「子」（根に接続しているノード）をもつことができる。そして、その子もまた2つまで子をもつことができ、その子も……、以下同様である。このようにして、根から、他の木内のノードへの経路ができる。

赤黒木における[[葉]]（図1の<span style="background:black">&thinsp;<span style="color:white">NIL</span>&thinsp;</span>）はデータを持たないノードである。この葉は実際にメモリ上に置かれる必要はなく[[ヌルポインタ]]で表すこともできるが、独立のノードとみなしたほうがいくつかのアルゴリズムの記述が簡単になる。 また、[[部分木]]とは、木のうちある一つのノードから[[到達可能]]な部分を取り出して一つの木とみたとき、その取り出した木をいう。

赤黒木は[[二分木#二分探索木|二分探索木]]であり、すなわち、各ノードのもつ値が

* そのノードの右部分木に含まれるノードのもつ値より大きくない
* そのノードの左部分木に含まれるノードのもつ値より小さくない

という性質をもつようにつくられる。これによって、木の中から特定の値をさがすことや、すべての値を順番にあたることなどが素早くできるわけである。

ノードの'''黒深さ'''は、根からそのノードまでの黒ノードの数（すなわち黒祖先の数）と定義される。赤黒木の'''黒高さ'''は、根から葉までのどの経路にもある黒のノードの数であり、[[#req5|要件5]]により一定である（代わりに、任意の葉のノードの黒深さとして定義することもできる）。 <ref name="Mehlhorn2008">{{cite book
 |chapter=7. Sorted Sequences
 |chapter-url=http://people.mpi-inf.mpg.de/~mehlhorn/ftp/Toolbox/SortedSequences.pdf
 |title=Algorithms and Data Structures: The Basic Toolbox
 |url=http://people.mpi-inf.mpg.de/~mehlhorn/Toolbox.html
 |last1=Mehlhorn |first1=Kurt |author-link1=Kurt Mehlhorn
 |last2=Sanders|first2=Peter |author-link2=Peter Sanders (computer scientist)
 |publisher=Springer |location= Berlin/Heidelberg
 |year=2008
 |isbn=978-3-540-77977-3
 |doi=10.1007/978-3-540-77978-0 |citeseerx=10.1.1.148.2305
}}</ref>{{rp|154–165}}
ノードの黒高さは、そのノードが根とする部分木の黒高さである。この記事では、NILノードの黒高さは0とする。なぜなら、その部分木は図2が示唆するように空であり、その木の高さも0であるからである。

== 用途と利点 ==
赤黒木という[[データ構造]]は、最悪のケースにおける[[計算量]]が、データの挿入・削除・検索のいずれにおいても、データ構造のうちで最善のものの一つである。このため、[[リアルタイムシステム|リアルタイム・コンピューティング]]のような時間計算量に敏感なアプリケーションにおいて有益である。また、[[計算幾何学]]で用いるデータ構造など、最悪のケースでの計算量を保証する必要のあるデータ構造の基礎としても有用なことが多い。
赤黒木と同様に平衡二分木である[[AVL木]]は、赤黒木に比べて平衡性についての条件が厳しく、そのためAVL木では最悪のケースを想定すると挿入や削除の際の回転操作の回数が赤黒木より多くなってしまう。

赤黒木は[[関数型プログラミング]]においても部分的に重要であり、[[永続的データ構造]]を実現するデータ構造の一つとして、変更後も以前の値を保持し続けるような[[連想配列]]や[[集合 (プログラミング)|集合]]を実装する際に広く用いられるものの一つである。なお、このような[[永続性 (計算機科学)|永続性]]をもったタイプの赤黒木では、挿入や削除のたびに、時間だけでなく <math>\mathcal{O}(\log n)</math> のオーダーの[[空間計算量|空間]]が必要となる。

赤黒木は[[2-3-4木]]に[[アイソメトリック]]である。すなわち、任意の2-3-4木に対して、少なくとも一つの赤黒木でその2-3-4木と同じデータを同じ順序でもつものが存在する。このとき、2-3-4木における挿入および削除の各操作は、赤黒木におけるカラー・フリッピングおよび回転の各操作に等価であり、そのため、2-3-4木を考えることは赤黒木の背景にある理論を理解する上で重要である。実用性の高くない2-3-4木が、[[アルゴリズム]]の入門書において赤黒木の直前によく紹介されているのは、このためである。

== 性質 ==
赤黒木は、各ノードに「赤」または「黒」という「色」をつけた[[二分木#二分探索木|二分探索木]]であり、赤黒木として有効なものであるためには、通常の二分探索木としての条件のほか、以下の条件が要求される。<ref name="Cormen2009">{{cite book
 |last1=Cormen |first1=Thomas |author-link1=Thomas H. Cormen
 |last2=Leiserson |first2=Charles |author-link2=Charles E. Leiserson
 |first3=Ronald |last3=Rivest |author-link3=Ron Rivest
 |first4=Clifford |last4=Stein |author-link4=Clifford Stein
 |chapter=13. Red–Black Trees
 |title=Introduction to Algorithms |title-link=Introduction to Algorithms
 |edition=3rd |year=2009 |publisher=[[MIT Press]] |isbn=978-0-262-03384-8
 |pages=[https://archive.org/details/introductiontoal00corm_805/page/n328 308]–309
}}</ref>

# 各ノードは赤か黒の色をもつ。
# 根は黒である  (この条件はしばし省かれる。根は赤から黒に変えることはできるので、解析にはほとんど影響しない)。
# {{Anchors|consideredBlack}}葉 (NIL) はすべて黒である。葉はすべて根と同じ色である。
# {{Anchors|req4}}赤のノードは黒ノードを2つ子に持つ（したがって、赤のノードの親ノードは黒である）。
# {{Anchors|req5}}任意のノードについて、そのノードから子孫の葉までの道に含まれる黒いノードの数は、選んだ葉によらず一定である（この条件は、「根から葉までの道に含まれる黒いノードの数は、葉によらず一定である」と言い換えることができる）。

これらの条件から、次の赤黒木の重要な性質が導かれる。

* 根から葉まで道で最長のものの長さは、根から葉までの道で最短のものの長さの二倍を超えない。

これは、赤黒木がある程度の平衡性をもっているということである。挿入・削除・検索といった操作は最悪のケースでは木の[[木 (数学)#根つき木|高さ]]に比例した時間を要するので、このような赤黒木の性質から理論的に[[計算量|最悪時間計算量]]の見積もりが立つことになる。これは通常の[[二分木#二分探索木|二分探索木]]と異なる赤黒木の特徴である。

先ほどの条件からなぜ今の性質が導かれるのかを確認するには、条件4からわかる「赤黒木の根から葉までの道において赤のノードが2つ続くことはない」という性質がカギになる。すなわち、条件をみたす最短の道というのはすべて黒のノードからなる道であり、条件を満たす最長の道というのは赤と黒のノードが交互に現れるような道となる。そして、条件5より、根から葉までの道がすべて同じ個数の黒のノードを含むことから、最長の道の長さは最短の道の長さの二倍を超えないという上記の性質が導かれる。（ここで、根と葉は黒のノードである。）

一般に、データの[[木構造 (データ構造)]]による表現では、ノードが一つだけの子をもつことや、葉ノードがデータをもつこと（言い換えれば、データをもつノードが子をもたないこと）を可能としている場合も多い。赤黒木においてもそのような考え方を導入することができないわけではないが、それをすると先ほどの性質をいくつかの点で修正する必要が生じ、またアルゴリズムが複雑になってしまう。そのため、この記事においては、今まで説明したように「空の葉」（nil leaf、null leaf）を用い、葉はデータをもたずただ木の終端を意味するだけのノードであるとした。なお、このような葉ノードは図をかく際には省略することも多く、その結果、赤黒木が先ほどの条件をみたさないように見えることがある。しかしもちろん、実際には内部の（つまり、葉ではない）ノードはすべて、空の葉を含めて2つの子をもっているわけである。

ところで、赤黒木について、二分木の（ノードではなく）辺に色がついたものであるという説明がなされていることもある。これは、この記事における「ノードの色」を「ノードとその親とを連結する辺の色」に読み替えたものである（ただし、「根ノードの色」に対応するものはないため、この記事での条件2にあたる条件が不要となる）。

== アプリケーションと関連するデータ構造 ==
赤黒木は挿入時間、削除時間、探索時間において、最悪のケースを保証する。これは[[リアルタイムシステム]]のような時間センシティブなアプリケーションにおいて価値あるのみならず、最悪のケースを保証する他のデータ構造における価値ある部品となっている。 例えば、[[計算幾何学]]で用いられる多くのデータ構造は赤黒木をベースとしているし、現行の[[Linux]]カーネルで用いられる '''CFS '''（[[Completely Fair Scheduler]]）では赤黒木を使用している。

[[AVL木]]は <math>\mathcal{O}(\log n)</math>の探索、挿入、削除をサポートする。もう一つのデータ構造である、AVL木は、赤黒木よりも厳密な平衡性を持っているため、挿入や削除は遅くなるが、検索は早くなる。このため、AVL木は一度構築して、再構成する必要のないデータ構造にとっては魅力的である。例えば、言語辞書（または、アセンブラやインタープリタの命令コードのようなプログラム辞書）などのように。

また、赤黒木は[[AVL木]]よりも条件が多いため、実装が面倒である。

赤黒木はまた、最も一般的な[[永続データ構造]]のひとつであり、[[関数型言語]]で特に価値がある。変化後に前のバージョンを保持できるように、[[連想配列]]や[[集合 (プログラミング)]]を構築するのに使われる。赤黒木の永続バージョンは、各挿入や各削除において <math>\mathcal{O}(\log n)</math> の（時間に加えて）空間を要する。

== 操作 ==
すべての赤黒木は単純な二分探索木の特殊なケースであるため、赤黒木に対する探索や木の走査などの読み取り専用操作は、二分探索木で使われるものと何の変更もない。しかし、挿入や削除の直後は赤黒木の性質に反する場合があるため、これを修復して赤黒木を平衡にすることをリバランシングという。{{Anchors|amortized}}操作における最悪時間計算量は、[[O記法]]で <math>\mathcal{O}(\log n)</math>（<math>n</math> は木の要素数）、平均では、<math>\mathcal{O}(\log n)</math> または償却された <math>\mathcal{O}(1)</math>、色の変更には定数（実際には非常に速い）<ref name="tarjan">{{cite journal|last=Tarjan|first=Robert Endre|author-link=ロバート・タージャン|title=Amortized Computational Complexity|journal=SIAM Journal on Algebraic and Discrete Methods|date=April 1985|volume=6|issue=2|pages=306–318|doi=10.1137/0606031|url=http://www.cs.duke.edu/courses/fall11/cps234/reading/Tarjan85_AmortizedComplexity.pdf}}</ref>{{rp|310}} <ref name="Mehlhorn2008"/>{{rp|158}}と小さい数になり、[[木の回転]]は3回以内（挿入は2回）となる。

挿入と削除の操作の詳細は、例として[[C++]]のコードを用いて説明する。サンプルコードでは、以下の型定義とマクロ、および回転のためのヘルパー関数を使用する。

<syntaxhighlight lang="c">
// 基本の型定義:

enum color_t { BLACK, RED };

struct RBnode {     // 赤黒木のノード
  RBnode* parent;   // == NULL (木のルートの時)
  RBnode* child[2]; // == NIL (子が空の時)
    // Index is:
    //   LEFT  := 0, if (key < parent->key)
    //   RIGHT := 1, if (key > parent->key)
  enum color_t color;
  int key;
};

#define NIL   NULL // ヌルポインタまたは番兵ノードへのポインタ
#define LEFT  0
#define RIGHT 1
#define left  child[LEFT]
#define right child[RIGHT]

struct RBtree { // 赤黒木
  RBnode* root; // == NIL (木が空の時)
};

// ルートでない非NILの RBnode* N の子方向（∈ { LEFT, RIGHT }）を取得する
#define childDir(N) ( N == (N->parent)->right ? RIGHT : LEFT )
</syntaxhighlight>

[[Image:Tree rotation animation 250x250.gif|right|Animation of tree rotations taking place.]]
<syntaxhighlight lang="c">
RBnode* RotateDirRoot(
    RBtree* T,   // 赤黒木
    RBnode* P,   // 部分木の根 (Tの根であってもよい)
    int dir) {   // dir ∈ { LEFT, RIGHT }
  RBnode* G = P->parent;
  RBnode* S = P->child[1-dir];
  RBnode* C;
  assert(S != NIL); // 真のノードへのポインターを要求する
  C = S->child[dir];
  P->child[1-dir] = C; if (C != NIL) C->parent = P;
  S->child[  dir] = P; P->parent = S;
  S->parent = G;
  if (G != NULL)
    G->child[ P == G->right ? RIGHT : LEFT ] = S;
  else
    T->root = S;
  return S; // 部分木の新しい根
}

#define RotateDir(N,dir) RotateDirRoot(T,N,dir)
#define RotateLeft(N)    RotateDirRoot(T,N,LEFT)
#define RotateRight(N)   RotateDirRoot(T,N,RIGHT)
</syntaxhighlight>

{{Anchors|explan}}
=== サンプルコードと挿入図・削除図に関する注記 ===
この提案では、挿入と削除（非常に単純なケースを除く）の両方を、ノード、エッジ、カラーの6つの組合せで分解し、ケースと呼ぶことにする。ケースを修復（リバランシング）するコードは、後続のケースのコードを使用することがある。この提案では、挿入と削除の両方について、根とループに黒レベルを1つずつ近づけるケースを正確に含み、他の5つのケースはそれ自体で木をリバランシングする。より複雑なケースは、図に描かれる。

* 変数 <code>N</code> はカレントノードを表し、図中では '''N''' と表される。
* [[Image:RedNode.svg|13px|baseline]] は赤ノードを、[[Image:BlackNode.svg|13px|baseline]] は（黒高さ &ge; 1 の）非NILの黒ノードを表し、（非NIL）ノード [[Image:RedOrBlackNode.svg|13px|baseline]] は赤・黒ノードのどちらでも良いが、同じ図の中では同じ色である。真のNILノードは図に描かれない。
* 図には3つの列と2～4つのアクションが含まれる。
** 左の列は最初の反復を、右の列はそれ以上の反復を、中央の列は1つのケースを異なるアクションに分割したものを表す。<ref name="pullout">左の列は右の列よりはるかに少ないノードしか含まず、特に削除の場合はそうである。これは、挿入と削除のリバランシングループから最初の反復を引き出すことで、ある程度の効率を得られることを示している。なぜなら、名前付きノードの多くは最初の反復ではNILノードであり、後で決定的に非NILノードとなるからである。（[[#C-eval|この章のコメント]]を参照.）</ref>
*# 動作 "entry" は、ケースを定義するノードの集まりとその色を示し、ほとんどの場合、いくつかの[[#性質|要件]]に違反している。<br />カレントノード'''N'''は青い枠で囲まれ、他のノードは'''N'''との関係によってラベル付けされている。
*# [[木の回転|回転]]が有効であると判断された場合は、次の動作は "rotate" とラベル付された絵となる。
*# 再色付けが有効であると判断された場合は、次の動作は "color" とラベル付された絵となる。<ref>わかりやすくするために、回転は再色付けの前に行われる。しかし、この2つのアクションは可換であるため、回転を[[末尾再帰|末尾]]に行うことも自由である。</ref>
*# まだ修復の必要がある場合、ノードの集まりは、新たに割り当てられたカレントノード'''N'''で挿入または削除のループ不変条件を満たし、再び青枠を持つようになる。また、'''N'''に対して他のノードが新たに割り当てられる可能性もある。この動作は "reassign "とラベル付けされている。<br />その後に続く動作は、他のケースのコードを再利用し、根に1つ近い黒レベルの反復となることもある。
* 番号が書かれた黒丸を頂点とする三角形（[[Image:TriangleTop.svg|baseline]]）は、赤黒木の部分木（[[#req4|要件4]]に従ってその親に接続）を表し、黒高さは反復レベルから1を引いた値に等しい。つまり最初の反復では0である。その部分木の根は、赤でも黒でもよい。<br />番号が書かれた三角形（[[Image:TriangleSubtree.svg|baseline]]）は、黒高さが1つ少ない赤黒木の部分木を表し、すなわちその親は2回目の反復で黒高さが0になる。

{{Anchors|C-eval}}
;コメント
: 簡単のため、サンプルコードでは[[論理和]]と
:: <code>U == NIL || U->color == BLACK ''// 黒とみなす''</code>
: [[論理積]]を
:: <code>U != NIL && U->color == RED &nbsp; ''// 黒でないとみなす''</code>
: 使用する。
: そのため、<code>U == NIL</code> の場合、論理和・論理積ともに式全体が評価されないことに留意する必要がある。この場合、どちらの場合も <code>U->color</code>は評価されない（[[短絡評価]]参照）。<br />(<code>黒とみなす</code>というコメントは、[[#consideredBlack|要件2]]に準じたものである。）
: この提案<ref name="pullout"/>が実現すれば、関連する<code>if</code>文の発生頻度を大幅に減らすことができる。

=== 挿入 ===
挿入は、新しい（非NIL）ノード（'''N'''とする）を、二分探索木における、[[木構造 (データ構造)|間順走査]]での先行ノードのキーが新しく挿入するノードのキーより小さく、かつ新しく追加するノードのキーが後行ノードのキーより小さくなるNILノードの位置に配置することから始まる。（多くの場合、この位置は、挿入操作の直前に木内を探索した結果であり、ノード <code>P</code> と、<code>P->child[dir] == NIL</code> を持つ方向 <code>dir</code> で構成される。）新しく挿入されたノードは一時的に赤色となり、すべての経路に以前と同じ数の黒ノードが含まれるようにする。しかし、その親ノード（例えば'''P'''）が赤である場合、この操作は[[#ViolR|赤違反]]を引き起こす。

<syntaxhighlight lang="C++">
void RBinsert1(
  RBtree* T,         // -> 赤黒木
  struct RBnode* N,  // -> 挿入するノード
  struct RBnode* P,  // -> Nの親ノード（NULLでも可）
  byte dir)          // Nを挿入するPの側（LEFTまたはRIGHT）
{
  struct RBnode* G;  // -> Pの親ノード
  struct RBnode* U;  // -> Nのおじ

  N->color = RED;
  N->left  = NIL;
  N->right = NIL;
  N->parent = P;
  if (P == NULL) {   // 親がない場合
    T->root = N;     // Nが赤黒木Tの新しい根とし、
    return; // 挿入完了。
  }
  P->child[dir] = N; // NをPのdir側の子として挿入する
  // (do while)ループを開始する
  do {
</syntaxhighlight>

{{Anchors|loopInvariantI}}リバランシングループは以下の[[ループ不変条件|不変条件]]を持つ。
* カレントノード'''N'''は、各反復の開始時に [[File:RedNode.svg|13px]]（赤）である。
* [[#req4|要件4]]は、'''P'''も赤の場合（'''N'''で[[#ViolR|赤違反]]）、'''N'''←'''P'''を除き、すべてのペア node←parent で満たされる。
* 他のすべての性質（[[#req5|要件5]]を含む）は、木全体で満たされている。

==== 挿入図に関する注記 ====
{| class="wikitable floatright" style="text-align:center;"
|- style="background:#E8E8E8;font-size:smaller;"
|colspan="4"| ''前の状態'' ||rowspan="2"|ケース<br />→||rowspan="2"| ''回転'' ||rowspan="2"| ''割り当て'' ||colspan="4"| ''後の状態'' ||rowspan="2"| →<br />''次'' ||rowspan="2"| ''&Delta;h''
|- style="background:#E8E8E8"
| '''P''' || '''G''' || '''U''' ||style="width:.8em;"| ''x'' || '''P''' || '''G''' || '''U''' ||style="width:.8em;"| ''x''
|-
| — || || || || [[#挿入ケース3|'''I3''']] || || ||colspan="4"| || → ||
|-
| [[File:BlackNode.svg|13px]] || || || || [[#挿入ケース1|'''I1''']] || || ||colspan="4"| || → ||
|-
| [[File:RedNode.svg|13px]] || — || || || [[#挿入ケース4|'''I4''']] || || || [[File:BlackNode.svg|13px]] ||colspan="3"| || → ||
|-
| [[File:RedNode.svg|13px]] || [[File:BlackNode.svg|13px]] || [[File:RedNode.svg|13px]] || || [[#挿入ケース2|'''I2''']] || || '''N''':='''G''' || ? ||colspan="3"| || ? || 2
|-
| [[File:RedNode.svg|13px]] || [[File:BlackNode.svg|13px]] || [[File:BlackNode.svg|13px]] || i || [[#挿入ケース5|'''I5''']] || '''P'''↶'''N''' || '''N''':='''P''' || [[File:RedNode.svg|13px]] || [[File:BlackNode.svg|13px]] || [[File:BlackNode.svg|13px]] || o || '''I6''' || 0
|-
| [[File:RedNode.svg|13px]] || [[File:BlackNode.svg|13px]] || [[File:BlackNode.svg|13px]] || o || [[#挿入ケース6|'''I6''']] || '''P'''↷'''G''' || || [[File:BlackNode.svg|13px]] || [[File:RedNode.svg|13px]] || [[File:BlackNode.svg|13px]] || || → ||
|-
|colspan="13" style="text-align:left;font-size:smaller;"| 挿入: この一覧表では、前の列で、ノード群の起こりうるすべてのケース<ref name="cases">[[#Pfaff a|Ben Pfaff]]でも同じような分割が見られる。</ref>をカバーしている。
|}
* 図表において、'''P'''は'''N'''の親、'''G'''は'''N'''の祖父母、'''U'''は'''N'''のおじを表す。
* 図では、'''P'''は'''G'''の左の子として表されているが、'''P'''は左右どちら側にも存在する可能性がある。サンプルコードでは、サイド変数 <code>dir</code> によって、両方の可能性をカバーしている。
* '''N'''は挿入ノードであるが、操作を進めると他のノードもカレントノードになる可能性がある（ケース[[#挿入ケース2|'''I2''']]を参照）。
* 図で、'''P'''が'''N'''と同じく赤色の場合は、[[#ViolR|赤違反]]であることを表している。
* x列は子の向きの変化を表し、o（外側）は'''P'''と'''N'''がともに左またはともに右の子であることを意味し、i（内側）は'''P'''から'''N'''への方向が'''G'''から'''P'''への方向と違うことを意味する。
* ''前の状態''の列グループはケースを定義し、その名前が''ケース''の列で与えられる。そのため、空欄のセルの値は無視される。したがって、ケース[[#挿入ケース2|'''I2''']]の場合、対応する図では'''N'''の子方向は1つだが、サンプルコードでは両方の可能性をカバーしている。
* 一覧表の行は、すべての可能なRBケースをカバーし、理解しやすいように並べられている。
* ''回転''の列は、回転がリバランシングに寄与しているかどうかを示す。
* ''割り当て''の列は、後続のステップに入る前に'''N'''への割り当てが行われることを示す。これにより、他のノード'''P'''、'''G'''、'''U'''も同様に再割り当てが行われる可能性がある。
* ケースによってノードに変更があった場合、''後の状態''の列グループに示される。
* ''次''の列の矢印→は、このステップでリバランシングが完了したことを意味する。''後の状態''の列がちょうど1つのケースとなる場合、そのケースが次のケースとして示され、そうでない場合は疑問符が示される。
* ループは[[#挿入ケース1|挿入ケース1]]と[[#挿入ケース2|挿入ケース2]]の章に含まれ、ケース[[#挿入ケース2|'''I2''']]では、'''G'''が新しいカレントノード'''N'''になるという意味で、リバランシングの問題が <math>\Delta h=2</math> レベル高い木にエスカレートされる。そのため、木の修復には最大で <math>\tfrac{h}2</math> 回の繰り返しが必要になる（ここで <math>h</math> は木の高さ）。エスカレーションの確率は各反復で指数関数的に減少するので、総リバランシングコストは平均で一定であり、実際に[[#amortized|償却された定数]]になる。
* ループの本体から、ケース[[#挿入ケース1|'''I1''']]は単独で抜け、ケース[[#挿入ケース4|'''I4''']]、[[#挿入ケース6|'''I6''']]、[[#挿入ケース5|'''I5 + I6''']]、[[#挿入ケース3|'''I3''']]への終了分岐がある。
* 回転は[[#挿入ケース6|'''I6''']]と[[#挿入ケース5|'''I5 + I6''']]の時にループの外側で発生する。したがって、合計で最大2回の回転が発生する。

====挿入ケース1====
カレントノードの親'''P'''は黒であるから、[[#req4|要件4]]が成立する。[[#loopInvariantI|ループ不変条件]]により、[[#req5|要件5]]も成立する。
<syntaxhighlight lang="c">
    if (P->color == BLACK) {
      // Case_I1 (Pは黒):
      return; // 挿入完了
    }
    // ここからPは赤
    if ((G = P->parent) == NULL) 
      goto Case_I4; // Pは赤かつ根
    // else: Pは赤 そして G!=NULL.
    dir = childDir(P); // ノードPが位置するGの側（右か左か）
    U = G->child[1-dir]; // おじ
    if (U == NIL || U->color == BLACK) // Uが黒とみなされると
      goto Case_I56; // Pは赤 && Uは黒
</syntaxhighlight>

<!--actions: [e=entry,][r=rotation,][c=color,][a=reassign]-->
<!--actions: eca-->
{{Multiple image
|align=right
|state=expanded
|header_align=center
|header=[[#explan|→ <small>記号の説明</small>]]
|image1=Red-black_tree_insert_case_B0t.svg
|width1=113
|caption1=<small>最初の反復</small>
|image2=Red-black_tree_perpendic_579_en.svg
|width2=12
|image3=Red-black_tree_insert_case_B1t.svg
|width3=129
|caption3=<small>上位の反復</small>
|footer=挿入ケース2
}}

====挿入ケース2====
親'''P'''とおじ'''U'''の両方が赤なら、両方を黒に塗り替え、祖父母'''G'''を赤にすることで[[#req5|要件5]]を維持することが可能となる。親やおじを通る経路は必ず祖父母を通るので、これらの経路上の黒ノードの数は変わっていない。しかし、祖父母'''G'''が赤の親を持つ場合、[[#req4|要件4]]に違反する可能性がある。'''G'''を'''N'''にラベル付けした後、ループ不変条件が満たされるので、1つ上の黒レベル（＝2の木レベル）でリバランシングを繰り返すことができるようになる。
<syntaxhighlight lang="c">
    // Case_I2 (PとUが赤):
    P->color = BLACK;
    U->color = BLACK;
    G->color = RED;
    N = G; // 新しいカレントノード
    // 1段階上の黒を反復
    //   (= 2の木レベル)
  } while ((P = N->parent) != NULL);
  // (do while)ループの終了
</syntaxhighlight>

====挿入ケース3====
[[#挿入ケース2|挿入ケース2]]は <math>\tfrac{h-1}2</math> 回実行され、木の合計高さが1増加し、現在 <math>h</math> となる。カレントノード'''N'''は木の（赤）根であり、すべての赤黒木の性質が満たされている。
<syntaxhighlight lang="c">
  // (do while)ループを抜ける(Case_I2から抜け出した後)。
  // Case_I3: Nは根であり、赤。
  return; // 挿入完了
</syntaxhighlight>

====挿入ケース4====
親'''P'''は赤で根。'''N'''も赤なので、[[#req4|要件4]]に違反する。しかし、'''P'''の色を変えると、木は赤黒木の形になり、木の黒高さが1つ増える。
<syntaxhighlight lang="c">
Case_I4: // Pは根かつ赤:
  P->color = BLACK;
  return; // 挿入完了
</syntaxhighlight>

<!--actions: era-->
{{Multiple image
|align=left
|state=expanded
|header_align=center
|header=[[#explan|→ <small>記号の説明</small>]]
|image1=Red-black_tree_insert_case_C0.svg
|width1=85
|caption1=<small>最初の反復</small>
|image2=Red-black_tree_perpendic_639era_en.svg
|width2=12
|image3=Red-black_tree_insert_case_C1.svg
|width3=129
|caption3=<small>上位の反復</small>
|footer=挿入ケース5
}}

====挿入ケース5====
親'''P'''は赤だが、おじ'''U'''は黒。最終的な目標は、親ノード'''P'''を祖父母の位置に回転させることだが、'''N'''が'''G'''の内側の孫の場合（つまり、'''N'''が'''G'''の右子の左子または'''G'''の左子の右子の場合）、これはうまくいかない。'''P'''で{{nowrap|<code>dir</code>-回転}}を行うと、カレントノード'''N'''とその親'''P'''の役割が入れ替わる。この回転により、'''N'''を通る経路（図中の2の部分木）が追加され、'''P'''を通る経路（図中の4の部分木）が削除される。しかし、'''P'''も'''N'''も赤なので、[[#req5|要件5]]は維持される。[[#req4|要件4]]はケース6で復元される。
<syntaxhighlight lang="c">
Case_I56: // Pは赤 && Uは黒:
  if (N == P->child[1-dir])
  { // Case_I5 (Pは赤 && Uは黒 && NはGの内側の孫):
    RotateDir(P,dir); // Pは根にはならない
    N = P; // 新しいカレントノード
    P = G->child[dir]; // Nの新しい親
    // Case_I6に該当する
  }
</syntaxhighlight>

<!--actions: erc-->
{{Multiple image
|align=right
|state=expanded
|header_align=center
|header=[[#explan|→ <small>記号の説明</small>]]
|image1=Red-black_tree_insert_case_D0rot.svg
|width1=85
|caption1=<small>最初の反復</small>
|image2=Red-black_tree_perpendic_639_en.svg
|width2=12
|image3=Red-black_tree_insert_case_D1rot.svg
|width3=129
|caption3=<small>上位の反復</small>
|footer=挿入ケース6
}}

====挿入ケース6====
カレントノード'''N'''は、'''G'''の外側の孫（左子の左子または右子の右子）であることが確定している。今度は'''G'''で{{nowrap|<code>(1-dir)</code>-回転}}して、'''G'''の代わりに'''P'''を置き、'''P'''を'''N'''と'''G'''の親とすると、[[#req4|要件4]]に違反するため、'''G'''は黒、'''G'''の前の子'''P'''は赤となる。'''P'''と'''G'''の色を入れ替えた後の木は、[[#req4|要件4]]を満たしている。黒'''G'''を経由していた経路はすべて黒'''P'''を経由するようになったので、[[#req5|要件5]]も満たしたままである。
<syntaxhighlight lang="c">
  // Case_I6 (Pは赤 && Uは黒 && NはGの外側の孫):
  RotateDirRoot(T,G,1-dir); // Gは根である可能性がある
  P->color = BLACK;
  G->color = RED;
  return; // 挿入完了
} // RBinsert1の終了
</syntaxhighlight>

このアルゴリズムは、補助的なデータ構造を使用せずに入力を変換し、補助的な変数のためにわずかな記憶領域を余分に使用するだけなので、[[In-placeアルゴリズム|インプレース]]である。

===削除（シンプルなケース）===
ラベル'''N'''は、入力時に削除されるノードであるカレントノードを表す。

もし、'''N'''が根で、非NILの子を持たない場合、'''N'''はNILノードに置き換えられ、その後、木は空になり、赤黒木の形になる。

もし、'''N'''が2つの非NILの子を持つ場合、'''N'''の左側の部分木の最大要素（これは間順走査での'''N'''の先行ノード）または'''N'''の右側の部分木の最小要素（これは間順走査での'''N'''の後行ノード）のいずれかへの追加のナビゲーションは、（[[二分探索木#削除|ここ]]に示すように）'''N'''との間に他のノードが存在しないノードを見つける。この置換ノードは'''R'''と呼ばれ、部分木の最大または最小要素として、最大で1つの非NILの子を持つ。ユーザが定義したノード構造からソフトウェアを完全に独立させるために、'''N'''との間のすべての赤黒い木のポインタは、'''R'''との間のすべての赤黒木のポインタと交換され、'''N'''のRB-colorも'''R'''に与えられる。ノード間の順序関係は、'''N'''と'''R'''間の順序（'''N'''を除去することによって直ちに解決する問題）を除いて保存され、'''N'''は最大1つの非NILの子を持つ。

もし、'''N'''がちょうど1つだけ非NILの子を持つなら、'''N'''の子は赤でなければならない。もし'''N'''の子が黒なら、[[#req5|要件5]]によって2つ目の黒の非NILの子が強制されるからである。

もし、'''N'''が赤のノードである場合、非NILの子を持つことはできない。なぜなら[[#req4|要件4]]により'''N'''の子は黒でなければならないからであり、さらに、先ほどの議論と同様に、黒い子を1つだけ持つことはできない。その結果、赤のノード'''N'''は子を持たず、単に削除されるだけである。

もし、'''N'''が黒ノードであれば、1つの赤の子ノードを持つか、非NILの子ノードを全く持たない場合がある。'''N'''が赤の子ノードを持っている場合は、赤の子ノードを黒く塗った後、その子ノードと'''N'''を置き換えるだけである。

===非根の黒葉ノードの削除===
複雑なケースは、'''N'''が根でなく、黒色で、NILの子だけを持つ（⇔色が正確な子を持たない）場合である。最初の反復で、'''N'''はNILに置き換えられる。

<syntaxhighlight lang="c">
void RBdelete2(
  RBtree* T,         // -> 赤黒木
  struct RBnode* N)  // -> 削除対象ノード
 {
  struct RBnode* P = N->parent;  // -> Nの親ノード
  byte dir;          // Nの位置するPの側 (∈ { LEFT, RIGHT })
  struct RBnode* S;  // -> Nの兄弟ノード
  struct RBnode* C;  // -> 近いおい
  struct RBnode* D;  // -> 遠いおい

  // P != NULL, Nは根ではないので。
  dir = childDir(N); // ノードNが位置する親Pの側（LEFT か RIGHT）
  // 親PのNをNILに置き換える:
  P->child[dir] = NIL;
  goto Start_D;      // ループに移動する

  // (do while)-ループの開始:
  do {
    dir = childDir(N);   // ノードNの位置する親Pの側
Start_D:
    S = P->child[1-dir]; // Nの兄弟 (黒高さ >= 1)
    D = S->child[1-dir]; // 遠いおい
    C = S->child[  dir]; // 近いおい
    if (S->color == RED)
      goto Case_D3;                  // Sが赤 ===> P+C+Dが黒
    // S is black:
    if (D != NIL && D->color == RED) // 黒でないとみなす
      goto Case_D6;                  // Dが赤 && Sが黒
    if (C != NIL && C->color == RED) // 黒でないとみなす
      goto Case_D5;                  // Cが赤 && S+Dが黒
    // ここでは、両方のおい == NIL (最初の反復) または黒 (上位の反復).
    if (P->color == RED)
      goto Case_D4;                  // Pが赤 && C+S+Dが黒
</syntaxhighlight>

{{Anchors|loopInvariantD}}リバランシングループは以下の[[ループ不変条件|不変条件]]を持つ。
* 各反復の始めに、'''N'''の黒高さは反復番号から1を引いたものに等しく、これは最初の反復では0であり、上位の反復では'''N'''は真の黒ノード [[File:BlackNode.svg|13px]] であることを意味する。
* '''N'''を通る経路の黒ノード数は削除前より1つ少ないが、それ以外の経路では変化しないので、他の経路が存在する場合は'''P'''で[[#ViolB|黒違反]]が発生することになる。
* 他のすべての性質（[[#req4|性質4]]を含む）は、木全体で満たされている。

====削除図に関する注記====
{| class="wikitable floatright" style="text-align:center;"
|- style="background:#E8E8E8;font-size:smaller;"
|colspan="4"| ''前の状態'' ||rowspan="2"|''ケース''<br />→||rowspan="2"| ''回転'' ||rowspan="2"|''割り当て'' ||colspan="4"| ''後の状態'' ||rowspan="2"|→<br />''次'' ||rowspan="2"| ''&Delta;h''
|- style="background:#E8E8E8"
| '''P''' || '''C''' || '''S''' || '''D''' || '''P''' || '''C''' || '''S''' || '''D'''
|-
| — || || || || [[#削除ケース2|'''D2''']] || || ||colspan="4"| || → ||
|-
| [[File:BlackNode.svg|13px]] || [[File:BlackNode.svg|13px]] || [[File:RedNode.svg|13px]] || [[File:BlackNode.svg|13px]] || [[#削除ケース3|'''D3''']] || '''P'''↶'''S''' || '''N''':='''N''' || [[File:RedNode.svg|13px]] || ? || [[File:BlackNode.svg|13px]] || ? || ? || 0
|-
| [[File:BlackNode.svg|13px]] || [[File:BlackNode.svg|13px]] || [[File:BlackNode.svg|13px]] || [[File:BlackNode.svg|13px]] || [[#削除ケース1|'''D1''']] || || '''N''':='''P''' || ? ||colspan="3"| || ? || 1
|-
| [[File:RedNode.svg|13px]] || [[File:BlackNode.svg|13px]] || [[File:BlackNode.svg|13px]] || [[File:BlackNode.svg|13px]] || [[#削除ケース4|'''D4''']] || || || [[File:BlackNode.svg|13px]] || [[File:BlackNode.svg|13px]] || [[File:RedNode.svg|13px]] || [[File:BlackNode.svg|13px]] || → ||
|-
| [[File:RedOrBlackNode.svg|13px]] || [[File:RedNode.svg|13px]] || [[File:BlackNode.svg|13px]] || [[File:BlackNode.svg|13px]] || [[#削除ケース5|'''D5''']] || '''C'''↷'''S''' || '''N''':='''N''' || [[File:RedOrBlackNode.svg|13px]] || || [[File:BlackNode.svg|13px]] || [[File:RedNode.svg|13px]] || '''D6''' || 0
|-
| [[File:RedOrBlackNode.svg|13px]] || || [[File:BlackNode.svg|13px]] || [[File:RedNode.svg|13px]] || [[#削除ケース6|'''D6''']] || '''P'''↶'''S''' || || [[File:BlackNode.svg|13px]] || || [[File:RedOrBlackNode.svg|13px]] || [[File:BlackNode.svg|13px]] || → ||
|-
|colspan="13" style="text-align:left; font-size:smaller;"| 削除: この一覧表では、''前の状態''の列で、ノード群の起こりうるすべてのケース<ref name="cases"/>をカバーしている。
|}

* 図表において、'''P'''が'''N'''の親ノード、'''S'''が'''N'''の兄弟ノード、'''C'''が'''S'''の'''N'''と同じ方向の子ノード（近いおい）、'''D'''が'''S'''のもう一方の子ノード（遠いおい）となる（'''S'''は削除前の'''N'''の黒高さが1でなければならないので最初の反復でNILノードにはなれないが、'''C'''と'''D'''はNILノードになってもよい）。
* 図では、カレントノード'''N'''が親'''P'''の左の子となっているが、'''N'''は左右どちら側にも存在することが可能である。サンプルコードでは、サイド変数 <code>dir</code> によって、両方の可能性をカバーしている。
* 削除の初め（最初の反復）では、'''N'''は削除されるノードの代わりにNILノードである。親ノードでの位置だけが重要なので、削除図の左欄には [[Image:NilBlue.svg|8px]]（意味：カレントノード'''N'''はNILノードで左の子）で記号化される。操作を進めると、（黒高さ &ge; 1の）非NILのノードもカレントノードになる可能性がある(例：ケース[[#削除ケース1|'''D1''']]参照)。
* 削除図にある黒丸（[[File:BlackNode.svg|13px]] と [[Image:TriangleTop.svg]]）を数えることで、'''N'''を通る経路は他の経路より黒丸が1つ少ないことがわかる。これは'''P'''での[[#ViolB|黒違反]]を意味する。
* ''前の状態''の列グループはケースを定義し、その名前が''ケース''の列で与えられる。そのため、空欄のセルの値は無視される。
* 一覧表の行は、すべての可能なRBケースをカバーし、理解しやすいように並べられている。
* ''回転''の列は、回転がリバランシングに寄与しているかどうかを示す。
* ''割り当て''の列は、後続のステップに入る前に'''N'''への割り当てが行われることを示す。これにより、他のノード'''P'''、'''C'''、'''S'''、'''D'''も同様に再割り当てが行われる可能性がある。
* ケースによってノードに変更があった場合、''後の状態''の列グループに示される。
* ''次''の列の矢印→は、このステップでリバランシングが完了したことを意味する。''後の状態''の列がちょうど1つのケースとなる場合、そのケースが次のケースとして示され、そうでない場合は疑問符が示される。
* ループは <code>Start_D</code> から[[#削除ケース1|削除ケース1]]までのセクションに含まれ、親'''P'''が新しいカレントノード'''N'''になることで、リバランスの問題が木で <math>\Delta h=1</math> レベル高くエスカレートされる。そのため、木の修復には最大で <math>h</math> 回の繰り返しが必要になる（<math>h</math> は木の高さ）。エスカレーションの確率は各反復で指数関数的に減少するので、総リバランシングコストは平均で一定であり、実際に[[#amortized|償却された定数]]になる。（ただ、余談だが Mehlhorn & Sandersが指摘している。"AVL木は一定の償却更新コストをサポートしない"<ref name="Mehlhorn2008"/>{{rp|165,158}}これは、削除後のリバランシングには当てはまるが、AVL挿入には当てはまらない。<ref>Dinesh P. Mehta, Sartaj Sahni (Ed.) ''Handbook of Data Structures and Applications'' 10.4.2</ref>）
* ループの本体からは、ケース[[#削除ケース3|'''D3''']]、[[#削除ケース6|'''D6''']]、[[#削除ケース5|'''D5 + D6''']]、[[#削除ケース4|'''D4''']]、[[#削除ケース2|'''D2''']]への分岐があり、[[#削除ケース3|削除ケース3]]セクションは、それ自体でケース'''D6'''、'''D5'''、'''D4'''への3種類の分岐がある。
* '''D6'''と'''D5 ＋ D6'''と'''D3 ＋ D5 ＋ D6'''で回転が発生するが、すべてループの外側である。したがって、最大で合計3回の回転が発生する。

<!--actions: eca-->
{{Multiple image
|align=right
|state=expanded
|header_align=center
|header=[[#explan|→ <small>記号の説明</small>]]
|image1=Red-black_tree_delete_case_B0t.svg
|width1=95
|caption1=<small>最初の反復</small>
|image2=Red-black_tree_perpendic_579_en.svg
|width2=12
|image3=Red-black_tree_delete_case_B1t.svg
|width3=156
|caption3=<small>上位の反復</small>
|footer=削除ケース1
}}

====削除ケース1====
'''P'''、'''S'''、'''S'''の子は黒である。'''S'''を赤にした後、'''S'''を通るすべての経路（正確には'''N'''を通らない経路）は、黒ノードが1つ少なくなる。ここで、'''P'''をルートとする部分木のすべての経路は同じ数の黒ノードを持つが、'''P'''を通らない経路より1つ少ないので、まだ[[#req4|要件4]]に違反している可能性がある。'''P'''を'''N'''にラベル付けした後、[[#loopInvariantD|ループ不変条件]]が満たされるので、1上の黒レベル（=1上の木レベル）でリバランシングを繰り返すことができる。
<syntaxhighlight lang="c">
    // Case_D1 (P+C+S+Dは黒):
    S->color = RED;
    N = P; // 新しいカレントノード (根かもしれない)
    // 1黒レベル(1木レベル)を上げながら反復する
  } while ((P = N->parent) != NULL);
  // (do while)-ループの終了
</syntaxhighlight>

====削除ケース2====
カレントノード'''N'''が新しい根となる。すべての経路から1つの黒ノードが削除されたので、RB性質は維持される。木の黒高さは1減少する。
<syntaxhighlight lang="c">
  // Case_D2 (P == NULL):
  return; // 削除完了
</syntaxhighlight>

{{clear}}
<!--actions: rca-->
{{Multiple image
|align=left
|state=expanded
|header_align=center
|header=[[#explan|→ <small>記号の説明</small>]]
|image1=Red-black_tree_delete_case_A0rot.svg
|width1=121
|caption1=<small>最初の反復</small>
|image2=Red-black_tree_perpendic_799_en.svg
|width2=12
|image3=Red-black_tree_delete_case_A1rot.svg
|width3=156
|caption3=<small>上位の反復</small>
|footer=削除ケース3
}}

====削除ケース3====
兄弟ノード'''S'''は赤だから、'''P'''とおいの'''C'''と'''D'''は黒でなければならない。'''P'''で{{nowrap|<code>dir</code>-回転}}すると、'''S'''が'''N'''の祖父母ノードになる。そして、'''P'''と'''S'''の色を反転させても、'''N'''を通る経路は黒ノードが1つ少ないままである。しかし、'''N'''は赤の親'''P'''と黒の兄弟'''S'''を持っているので、ケースD4、D5、D6の変換で赤黒木の形を復元することができる。
<syntaxhighlight lang="c">
Case_D3: // Sは赤 && P+C+Dは黒:
  RotateDirRoot(T,P,dir); // Pは根かもしれない
  P->color = RED;
  S->color = BLACK;
  S = C; // != NIL
  // ここで: Pは赤 && Sは黒
  D = S->child[1-dir]; // 遠いおい
  if (D != NIL && D->color == RED)
    goto Case_D6;      // Dは赤 && Sは黒
  C = S->child[  dir]; // 近いおい
  if (C != NIL && C->color == RED)
    goto Case_D5;      // Cは赤 && S+Dは黒
  // それ以外のC+Dは黒とみなす。
  // Case_D4に該当する。
</syntaxhighlight>

{{clear}}
<!--actions: ec-->
{{Multiple image
|align=right
|state=expanded
|header_align=center
|header=[[#explan|→ <small>記号の説明</small>]]
|image1=Red-black_tree_delete_case_C0.svg
|width1=95
|caption1=<small>最初の反復</small>
|image2=Red-black_tree_perpendic_419_en.svg
|width2=12
|image3=Red-black_tree_delete_case_C1.svg
|width3=156
|caption3=<small>上位の反復</small>
|footer=削除ケース4
}}

====削除ケース4====
兄弟'''S'''と'''S'''の子どもは黒だが、'''P'''は赤である。'''S'''と'''P'''の色を交換しても、'''S'''を通る経路の黒ノードの数には影響しないが、'''N'''を通る経路の黒ノードが1つ追加され、削除された黒ノードの分を補うことができる。

<syntaxhighlight lang="c">
Case_D4: // Pは赤 && S+C+Dは黒:
  S->color = RED;
  P->color = BLACK;
  return; // 削除完了
</syntaxhighlight>

{{clear}}
<!--actions: rca-->
{{Multiple image
|align=left
|state=expanded
|header_align=center
|header=[[#explan|→ <small>記号の説明</small>]]
|image1=Red-black_tree_delete_case_D0rot.svg
|width1=95
|caption1=<small>最初の反復</small>
|image2=Red-black_tree_perpendic_919_en.svg
|width2=12
|image3=Red-black_tree_delete_case_D1rot.svg
|width3=156
|caption3=<small>上位の反復</small>
|footer=削除ケース5
}}

====削除ケース5====
兄弟'''S'''は黒、'''S'''の'''N'''に近い子'''C'''は赤、'''S'''の'''N'''に遠い子'''D'''は黒である。'''S'''で{{nowrap|<code>(1-dir)</code>-回転}}した後、おい'''C'''は'''S'''の親となり、'''N'''の新しい兄弟となる。'''S'''と'''C'''の色を交換する。どの経路も黒ノードの数は同じだが、'''N'''には黒の兄弟があり、その遠い方の子は赤なので、ケースD6に適合するノード群となる。'''N'''もその親'''P'''もこの変換の影響を受けず、'''P'''は赤にも黒にもなる（図中の [[Image:RedOrBlackNode.svg|13px]]）。
<syntaxhighlight lang="c">
Case_D5: // C red && S+D black:
  RotateDir(S,1-dir); // S is never the root
  S->color = RED;
  C->color = BLACK;
  D = S;
  S = C;
  // now: D red && S black
  // fall through to Case_D6
</syntaxhighlight>

{{clear}}
<!--actions: erc-->
{{Multiple image
|align=right
|state=expanded
|header_align=center
|header=[[#explan|→ <small>記号の説明</small>]]
|image1=Red-black_tree_delete_case_E0rot.svg
|width1=95
|caption1=<small>最初の反復</small>
|image2=Red-black_tree_perpendic_639_en.svg
|width2=12
|image3=Red-black_tree_delete_case_E1rot.svg
|width3=128
|caption3=<small>上位の反復</small>
|footer=削除ケース6
}}

====削除ケース6====
兄弟'''S'''は黒、'''S'''の遠い子'''D'''は赤である。'''P'''で{{nowrap|<code>dir</code>-回転}}した後、兄弟'''S'''は'''P'''と'''S'''の遠い子'''D'''の親となる。'''P'''と'''S'''の色を交換し、'''D'''を黒にする。部分木の根は依然として同じ色、すなわち赤か黒（図中の [[Image:RedOrBlackNode.svg|13px]]）であり、これは変換前も変換後も同じ色を指している。こうすることで、[[#req4|要件4]]が守られる。'''N'''を通らない部分木の経路（図中の'''D'''とノード3を通る経路）は、以前と同じ数の黒ノードを通るが、'''N'''には黒ノードの祖先が1つ追加される。'''P'''が黒くなったか、'''P'''が黒かったのに'''S'''の祖父母が黒くなったか、のどちらかである。したがって、'''N'''を通過する経路は、さらに1つの黒ノードを通過するので、[[#req5|要件5]]が回復し、全体の木は赤黒木の形になる。

<syntaxhighlight lang="c">
Case_D6: // Dは赤 && Sは黒:
  RotateDirRoot(T,P,dir); // Pは根かもしれない
  S->color = P->color;
  P->color = BLACK;
  D->color = BLACK;
  return; // 削除終了
} // RBdelete2の終了
</syntaxhighlight>

このアルゴリズムは、補助的なデータ構造を使用せずに入力を変換し、補助的な変数のためにわずかな記憶領域を余分に使用するだけなので、[[In-placeアルゴリズム|インプレース]]である。

== 脚注 ==
{{reflist}}

== 関連項目 ==
* [[木構造 (データ構造)|木構造]]
* [[木の回転]]
* [[二分探索木]]
* [[平衡二分探索木]]
* [[AA木]]（赤黒木の一種）
* [[AVL木]]
* [[B木]]（[[2-3木]], [[2-3-4木]], [[B+木]], [[B*木]]）
* [[スプレー木]]

== 外部リンク ==
* {{Wayback|url=http://www.geocities.jp/h2fujimura/mutter/tree/red-black-tree.html |title=情報処理概論(Java) |date=20160501205829}}

{{データ構造}}

{{DEFAULTSORT:あかくろき}}
[[Category:二分木]]
[[Category:探索木]]