stanford-oval/wikipedia huggingface dataset:
赤黒木
アプリケーションと関連するデータ構造

赤黒木は挿入時間、削除時間、探索時間において、最悪のケースを保証する。これはリアルタイムシステムのような時間センシティブなアプリケーションにおいて価値あるのみならず、最悪のケースを保証する他のデータ構造における価値ある部品となっている。 例えば、計算幾何学で用いられる多くのデータ構造は赤黒木をベースとしているし、現行のLinuxカーネルで用いられる CFS （Completely Fair Scheduler）では赤黒木を使用している。
AVL木は  {\mathcal {O}}(\log n)の探索、挿入、削除をサポートする。もう一つのデータ構造である、AVL木は、赤黒木よりも厳密な平衡性を持っているため、挿入や削除は遅くなるが、検索は早くなる。このため、AVL木は一度構築して、再構成する必要のないデータ構造にとっては魅力的である。例えば、言語辞書（または、アセンブラやインタープリタの命令コードのようなプログラム辞書）などのように。
また、赤黒木はAVL木よりも条件が多いため、実装が面倒である。
赤黒木はまた、最も一般的な永続データ構造のひとつであり、関数型言語で特に価値がある。変化後に前のバージョンを保持できるように、連想配列や集合 (プログラミング)を構築するのに使われる。赤黒木の永続バージョンは、各挿入や各削除において  {\mathcal {O}}(\log n) の（時間に加えて）空間を要する。
操作

すべての赤黒木は単純な二分探索木の特殊なケースであるため、赤黒木に対する探索や木の走査などの読み取り専用操作は、二分探索木で使われるものと何の変更もない。しかし、挿入や削除の直後は赤黒木の性質に反する場合があるため、これを修復して赤黒木を平衡にすることをリバランシングという。操作における最悪時間計算量は、O記法で  {\mathcal {O}}(\log n)（ n は木の要素数）、平均では、 {\mathcal {O}}(\log n) または償却された  {\mathcal {O}}(1)、色の変更には定数（実際には非常に速い） と小さい数になり、木の回転は3回以内（挿入は2回）となる。
挿入と削除の操作の詳細は、例として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 )
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)
操作 > サンプルコードと挿入図・削除図に関する注記

この提案では、挿入と削除（非常に単純なケースを除く）の両方を、ノード、エッジ、カラーの6つの組合せで分解し、ケースと呼ぶことにする。ケースを修復（リバランシング）するコードは、後続のケースのコードを使用することがある。この提案では、挿入と削除の両方について、根とループに黒レベルを1つずつ近づけるケースを正確に含み、他の5つのケースはそれ自体で木をリバランシングする。より複雑なケースは、図に描かれる。
変数 N はカレントノードを表し、図中では N と表される。
は赤ノードを、 は（黒高さ ≥ 1 の）非NILの黒ノードを表し、（非NIL）ノード  は赤・黒ノードのどちらでも良いが、同じ図の中では同じ色である。真のNILノードは図に描かれない。
図には3つの列と2～4つのアクションが含まれる。
左の列は最初の反復を、右の列はそれ以上の反復を、中央の列は1つのケースを異なるアクションに分割したものを表す。
動作 "entry" は、ケースを定義するノードの集まりとその色を示し、ほとんどの場合、いくつかの要件に違反している。
カレントノードNは青い枠で囲まれ、他のノードはNとの関係によってラベル付けされている。
回転が有効であると判断された場合は、次の動作は "rotate" とラベル付された絵となる。
再色付けが有効であると判断された場合は、次の動作は "color" とラベル付された絵となる。
まだ修復の必要がある場合、ノードの集まりは、新たに割り当てられたカレントノードNで挿入または削除のループ不変条件を満たし、再び青枠を持つようになる。また、Nに対して他のノードが新たに割り当てられる可能性もある。この動作は "reassign "とラベル付けされている。
その後に続く動作は、他のケースのコードを再利用し、根に1つ近い黒レベルの反復となることもある。
番号が書かれた黒丸を頂点とする三角形（）は、赤黒木の部分木（要件4に従ってその親に接続）を表し、黒高さは反復レベルから1を引いた値に等しい。つまり最初の反復では0である。その部分木の根は、赤でも黒でもよい。
番号が書かれた三角形（）は、黒高さが1つ少ない赤黒木の部分木を表し、すなわちその親は2回目の反復で黒高さが0になる。
操作 > 挿入

挿入は、新しい（非NIL）ノード（Nとする）を、二分探索木における、間順走査での先行ノードのキーが新しく挿入するノードのキーより小さく、かつ新しく追加するノードのキーが後行ノードのキーより小さくなるNILノードの位置に配置することから始まる。（多くの場合、この位置は、挿入操作の直前に木内を探索した結果であり、ノード P と、P->child[dir] == NIL を持つ方向 dir で構成される。）新しく挿入されたノードは一時的に赤色となり、すべての経路に以前と同じ数の黒ノードが含まれるようにする。しかし、その親ノード（例えばP）が赤である場合、この操作は赤違反を引き起こす。
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 {
リバランシングループは以下の不変条件を持つ。
カレントノードNは、各反復の開始時に （赤）である。
要件4は、Pも赤の場合（Nで赤違反）、N←Pを除き、すべてのペア node←parent で満たされる。
他のすべての性質（要件5を含む）は、木全体で満たされている。
操作 > 挿入 > 挿入図に関する注記

| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| 前の状態 | 前の状態 | 前の状態 | 前の状態 | ケース → | 回転 | 割り当て | 後の状態 | 後の状態 | 後の状態 | 後の状態 | → 次 | Δh |
| P | G | U | x | ケース → | 回転 | 割り当て | P | G | U | x | → 次 | Δh |
| — |  |  |  | I3 |  |  |  |  |  |  | → |  |
|  |  |  |  | I1 |  |  |  |  |  |  | → |  |
|  | — |  |  | I4 |  |  |  |  |  |  | → |  |
|  |  |  |  | I2 |  | N:=G |  ? |  |  |  |  ? | 2 |
|  |  |  | i | I5 | P↶N | N:=P |  |  |  | o | I6 | 0 |
|  |  |  | o | I6 | P↷G |  |  |  |  |  | → |  |
挿入: この一覧表では、前の列で、ノード群の起こりうるすべてのケースをカバーしている。
図表において、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も同様に再割り当てが行われる可能性がある。
ケースによってノードに変更があった場合、後の状態の列グループに示される。
次の列の矢印→は、このステップでリバランシングが完了したことを意味する。後の状態の列がちょうど1つのケースとなる場合、そのケースが次のケースとして示され、そうでない場合は疑問符が示される。
ループは挿入ケース1と挿入ケース2の章に含まれ、ケースI2では、Gが新しいカレントノードNになるという意味で、リバランシングの問題が  \Delta h=2 レベル高い木にエスカレートされる。そのため、木の修復には最大で  {\tfrac {h}{2}} 回の繰り返しが必要になる（ここで  h は木の高さ）。エスカレーションの確率は各反復で指数関数的に減少するので、総リバランシングコストは平均で一定であり、実際に償却された定数になる。
ループの本体から、ケースI1は単独で抜け、ケースI4、I6、I5 + I6、I3への終了分岐がある。
回転はI6とI5 + I6の時にループの外側で発生する。したがって、合計で最大2回の回転が発生する。
操作 > 挿入 > 挿入ケース1

カレントノードの親Pは黒であるから、要件4が成立する。ループ不変条件により、要件5も成立する。
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は黒
→ 記号の説明
挿入ケース2
操作 > 挿入 > 挿入ケース2

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

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

親Pは赤で根。Nも赤なので、要件4に違反する。しかし、Pの色を変えると、木は赤黒木の形になり、木の黒高さが1つ増える。
Case_I4: // Pは根かつ赤:
  P->color = BLACK;
  return; // 挿入完了
→ 記号の説明
挿入ケース5
操作 > 挿入 > 挿入ケース5

親Pは赤だが、おじUは黒。最終的な目標は、親ノードPを祖父母の位置に回転させることだが、NがGの内側の孫の場合（つまり、NがGの右子の左子またはGの左子の右子の場合）、これはうまくいかない。Pでdir-回転を行うと、カレントノードNとその親Pの役割が入れ替わる。この回転により、Nを通る経路（図中の2の部分木）が追加され、Pを通る経路（図中の4の部分木）が削除される。しかし、PもNも赤なので、要件5は維持される。要件4はケース6で復元される。
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に該当する
  }
→ 記号の説明
挿入ケース6
操作 > 挿入 > 挿入ケース6

カレントノードNは、Gの外側の孫（左子の左子または右子の右子）であることが確定している。今度はGで(1-dir)-回転して、Gの代わりにPを置き、PをNとGの親とすると、要件4に違反するため、Gは黒、Gの前の子Pは赤となる。PとGの色を入れ替えた後の木は、要件4を満たしている。黒Gを経由していた経路はすべて黒Pを経由するようになったので、要件5も満たしたままである。
// Case_I6 (Pは赤 && Uは黒 && NはGの外側の孫):
  RotateDirRoot(T,G,1-dir); // Gは根である可能性がある
  P->color = BLACK;
  G->color = RED;
  return; // 挿入完了
} // RBinsert1の終了
このアルゴリズムは、補助的なデータ構造を使用せずに入力を変換し、補助的な変数のためにわずかな記憶領域を余分に使用するだけなので、インプレースである。
操作 > 削除（シンプルなケース）

ラベル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の子が黒なら、要件5によって2つ目の黒の非NILの子が強制されるからである。
もし、Nが赤のノードである場合、非NILの子を持つことはできない。なぜなら要件4によりNの子は黒でなければならないからであり、さらに、先ほどの議論と同様に、黒い子を1つだけ持つことはできない。その結果、赤のノードNは子を持たず、単に削除されるだけである。
もし、Nが黒ノードであれば、1つの赤の子ノードを持つか、非NILの子ノードを全く持たない場合がある。Nが赤の子ノードを持っている場合は、赤の子ノードを黒く塗った後、その子ノードとNを置き換えるだけである。
操作 > 非根の黒葉ノードの削除

複雑なケースは、Nが根でなく、黒色で、NILの子だけを持つ（⇔色が正確な子を持たない）場合である。最初の反復で、NはNILに置き換えられる。
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が黒
リバランシングループは以下の不変条件を持つ。
各反復の始めに、Nの黒高さは反復番号から1を引いたものに等しく、これは最初の反復では0であり、上位の反復ではNは真の黒ノード  であることを意味する。
Nを通る経路の黒ノード数は削除前より1つ少ないが、それ以外の経路では変化しないので、他の経路が存在する場合はPで黒違反が発生することになる。
他のすべての性質（性質4を含む）は、木全体で満たされている。
操作 > 非根の黒葉ノードの削除 > 削除図に関する注記

| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| 前の状態 | 前の状態 | 前の状態 | 前の状態 | ケース → | 回転 | 割り当て | 後の状態 | 後の状態 | 後の状態 | 後の状態 | → 次 | Δh |
| P | C | S | D | ケース → | 回転 | 割り当て | P | C | S | D | → 次 | Δh |
| — |  |  |  | D2 |  |  |  |  |  |  | → |  |
|  |  |  |  | D3 | P↶S | N:=N |  |  ? |  |  ? |  ? | 0 |
|  |  |  |  | D1 |  | N:=P |  ? |  |  |  |  ? | 1 |
|  |  |  |  | D4 |  |  |  |  |  |  | → |  |
|  |  |  |  | D5 | C↷S | N:=N |  |  |  |  | D6 | 0 |
|  |  |  |  | D6 | P↶S |  |  |  |  |  | → |  |
削除: この一覧表では、前の状態の列で、ノード群の起こりうるすべてのケースをカバーしている。
図表において、PがNの親ノード、SがNの兄弟ノード、CがSのNと同じ方向の子ノード（近いおい）、DがSのもう一方の子ノード（遠いおい）となる（Sは削除前のNの黒高さが1でなければならないので最初の反復でNILノードにはなれないが、CとDはNILノードになってもよい）。
図では、カレントノードNが親Pの左の子となっているが、Nは左右どちら側にも存在することが可能である。サンプルコードでは、サイド変数 dir によって、両方の可能性をカバーしている。
削除の初め（最初の反復）では、Nは削除されるノードの代わりにNILノードである。親ノードでの位置だけが重要なので、削除図の左欄には （意味：カレントノードNはNILノードで左の子）で記号化される。操作を進めると、（黒高さ ≥ 1の）非NILのノードもカレントノードになる可能性がある(例：ケースD1参照)。
削除図にある黒丸（ と ）を数えることで、Nを通る経路は他の経路より黒丸が1つ少ないことがわかる。これはPでの黒違反を意味する。
前の状態の列グループはケースを定義し、その名前がケースの列で与えられる。そのため、空欄のセルの値は無視される。
一覧表の行は、すべての可能なRBケースをカバーし、理解しやすいように並べられている。
回転の列は、回転がリバランシングに寄与しているかどうかを示す。
割り当ての列は、後続のステップに入る前にNへの割り当てが行われることを示す。これにより、他のノードP、C、S、Dも同様に再割り当てが行われる可能性がある。
ケースによってノードに変更があった場合、後の状態の列グループに示される。
次の列の矢印→は、このステップでリバランシングが完了したことを意味する。後の状態の列がちょうど1つのケースとなる場合、そのケースが次のケースとして示され、そうでない場合は疑問符が示される。
ループは Start_D から削除ケース1までのセクションに含まれ、親Pが新しいカレントノードNになることで、リバランスの問題が木で  \Delta h=1 レベル高くエスカレートされる。そのため、木の修復には最大で  h 回の繰り返しが必要になる（ h は木の高さ）。エスカレーションの確率は各反復で指数関数的に減少するので、総リバランシングコストは平均で一定であり、実際に償却された定数になる。（ただ、余談だが Mehlhorn & Sandersが指摘している。"AVL木は一定の償却更新コストをサポートしない"これは、削除後のリバランシングには当てはまるが、AVL挿入には当てはまらない。）
ループの本体からは、ケースD3、D6、D5 + D6、D4、D2への分岐があり、削除ケース3セクションは、それ自体でケースD6、D5、D4への3種類の分岐がある。
D6とD5 ＋ D6とD3 ＋ D5 ＋ D6で回転が発生するが、すべてループの外側である。したがって、最大で合計3回の回転が発生する。
→ 記号の説明
削除ケース1
操作 > 非根の黒葉ノードの削除 > 削除ケース1

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

カレントノードNが新しい根となる。すべての経路から1つの黒ノードが削除されたので、RB性質は維持される。木の黒高さは1減少する。
// Case_D2 (P == NULL):
  return; // 削除完了
→ 記号の説明
削除ケース3
操作 > 非根の黒葉ノードの削除 > 削除ケース3

兄弟ノードSは赤だから、PとおいのCとDは黒でなければならない。Pでdir-回転すると、SがNの祖父母ノードになる。そして、PとSの色を反転させても、Nを通る経路は黒ノードが1つ少ないままである。しかし、Nは赤の親Pと黒の兄弟Sを持っているので、ケースD4、D5、D6の変換で赤黒木の形を復元することができる。
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に該当する。
→ 記号の説明
削除ケース4
操作 > 非根の黒葉ノードの削除 > 削除ケース4

兄弟SとSの子どもは黒だが、Pは赤である。SとPの色を交換しても、Sを通る経路の黒ノードの数には影響しないが、Nを通る経路の黒ノードが1つ追加され、削除された黒ノードの分を補うことができる。
Case_D4: // Pは赤 && S+C+Dは黒:
  S->color = RED;
  P->color = BLACK;
  return; // 削除完了
→ 記号の説明
削除ケース5
操作 > 非根の黒葉ノードの削除 > 削除ケース5

兄弟Sは黒、SのNに近い子Cは赤、SのNに遠い子Dは黒である。Sで(1-dir)-回転した後、おいCはSの親となり、Nの新しい兄弟となる。SとCの色を交換する。どの経路も黒ノードの数は同じだが、Nには黒の兄弟があり、その遠い方の子は赤なので、ケースD6に適合するノード群となる。Nもその親Pもこの変換の影響を受けず、Pは赤にも黒にもなる（図中の ）。
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
→ 記号の説明
削除ケース6
操作 > 非根の黒葉ノードの削除 > 削除ケース6

兄弟Sは黒、Sの遠い子Dは赤である。Pでdir-回転した後、兄弟SはPとSの遠い子Dの親となる。PとSの色を交換し、Dを黒にする。部分木の根は依然として同じ色、すなわち赤か黒（図中の ）であり、これは変換前も変換後も同じ色を指している。こうすることで、要件4が守られる。Nを通らない部分木の経路（図中のDとノード3を通る経路）は、以前と同じ数の黒ノードを通るが、Nには黒ノードの祖先が1つ追加される。Pが黒くなったか、Pが黒かったのにSの祖父母が黒くなったか、のどちらかである。したがって、Nを通過する経路は、さらに1つの黒ノードを通過するので、要件5が回復し、全体の木は赤黒木の形になる。
Case_D6: // Dは赤 && Sは黒:
  RotateDirRoot(T,P,dir); // Pは根かもしれない
  S->color = P->color;
  P->color = BLACK;
  D->color = BLACK;
  return; // 削除終了
} // RBdelete2の終了
このアルゴリズムは、補助的なデータ構造を使用せずに入力を変換し、補助的な変数のためにわずかな記憶領域を余分に使用するだけなので、インプレースである。
Animation of tree rotations taking place.
バリシャーノ

| バリシャーノ Barisciano |
| --- | --- |
 
行政
国:   イタリア
州:   アブルッツォ
県／大都市:   ラクイラ
CAP（郵便番号）:  67021
市外局番:  0862
ISTATコード:  066009
識別コード:  A667
分離集落:  #分離集落参照
隣接コムーネ:  #隣接コムーネ参照
地震分類:  zona 2 (sismicità media)
気候分類:  zona E, 2877 GG
公式サイト:  リンク
人口
人口:  1,764  人 (2018-01-01)
人口密度:  22.5 人/km2
文化
住民の呼称:  bariscianesi
守護聖人:  聖フラヴィアーノ (San Flaviano)
祝祭日:  11月25日
地理
座標:  北緯42度19分31秒 東経13度35分36秒﻿ / ﻿北緯42.32528度 東経13.59333度﻿ / 42.32528; 13.59333座標: 北緯42度19分31秒 東経13度35分36秒﻿ / ﻿北緯42.32528度 東経13.59333度﻿ / 42.32528; 13.59333
標高:  940 (568 - 1965)  m
面積:  78.56  km2
  バリシャーノの位置
  ラクイラ県におけるコムーネの領域
 ポータル イタリア
テンプレートを表示
バリシャーノ（イタリア語: Barisciano）は、イタリア共和国アブルッツォ州ラクイラ県にある、人口約1,800人の基礎自治体（コムーネ）。
地理 > 位置・広がり > 隣接コムーネ

隣接するコムーネは以下の通り。
カステルヴェッキオ・カルヴィージオ
フォッサ
ラークイラ
ポッジョ・ピチェンツェ
プラータ・ダンシドーニア
サン・デメトリオ・ネ・ヴェスティーニ
サン・ピーオ・デッレ・カーメレ
サント・ステーファノ・ディ・セッサーニオ
行政 > 分離集落

バリシャーノには、以下の分離集落（フラツィオーネ）がある。
Picenze (Petogna,Villa di Mezzo,San Martino)
関西東通

| --- | --- |
 
種類:  株式会社
本社所在地:   日本 〒531-0076 大阪府大阪市北区大淀中1丁目16番7号
設立:  1985年7月 （株式会社ティ・ディー・シーとして）
業種:  情報・通信業
法人番号:  8120001067309 
事業内容:  テレビ番組の制作・技術協力業務
代表者:  代表取締役社長 根岸秀尚
資本金:  2,840万円
売上高:  26億4,788万円（2022年3月期）
従業員数:  175名（2022年4月1日現在）
決算期:  3月
主要株主:  株式会社TBSアクト 株式会社MBSメディアホールディングス 朝日放送グループホールディングス株式会社 関西テレビ放送株式会社 讀賣テレビ放送株式会社 テレビ大阪株式会社
主要子会社:  株式会社東通インフィニティー 株式会社ライズ・アップ 株式会社東通企画
外部リンク:  https://www.kansai-totsu.com/
テンプレートを表示
株式会社関西東通（かんさいとうつう、英: Kansai Totsu,Inc.）は、TBSアクト（旧・東通）のグループ企業で、主に在阪局のテレビ番組制作に携わる技術プロダクションである。
沿革

1985年7月に「株式会社ティ・ディー・シー」として設立。2005年に東通クリエイト（のちに東通エーヴィセンターと統合し、現・東通インフィニティー）から4つの部門についての営業譲渡を受け、同4月「株式会社東通テクノサービス」に社名を改める。
この間、東通子会社で、在阪テレビ局と取引関係があった大阪東通（1968年設立）が経営難と、地上デジタルテレビ放送対応の設備投資の資金不足などから2001年に民事再生法を申請・倒産し、その後東通本社が受け皿となって同社の大阪支社として業務を引き継いだ が、2010年に東通大阪支社の業務を東通テクノサービスが継承すると共に、同年2月に現社名に改め今日にいたる。なお親会社であった東通は、2021年4月1日をもって、TBSアート&テクノロジー、並びにTBSホールディングスグループと東通グループの傘下にあった技術関連会社12社との合併による「TBSアクト」へ統合されたが、当社は社名変更されない。
関連会社

TBSアクト（旧東通）
東通インフィニティー
ライズ・アップ
東通企画
著名関係者

福家雅明（元阪神タイガース投手。Tigers-aiのタイガース主催試合中継ディレクター、スカイAの『猛虎キャンプリポート』レポーター）
ルーカスランド

| ルーカスランド |
| --- | --- |
欧字表記:  Lucasland
品種:  サラブレッド
性別:  牝
毛色:  鹿毛
生誕:  1962年
死没:  不明
父:  Lucero
母:  Lavant
母の父:  Le Lavandou
生国:   イギリス
馬主:  J Baillie
調教師:  Jack Waugh
競走成績
生涯成績:  21戦8勝
テンプレートを表示
ルーカスランド (Lucasland、1962年 - 不明) は、イギリスの競走馬。主な勝ち鞍は1966年のジュライカップ、ダイアデムステークス。他、1966年ナンソープステークス2着。
エリック・エルディン（英語版）が主戦騎手を務め、生涯成績は21戦8勝。
引退後は繁殖牝馬となり、その牝系は現在まで残っている。
主なファミリーライン

牝系図の主要な部分（太字はGI級競走優勝馬）は以下の通り。 *印は日本輸入馬
Lucasland 1962
Land Ho 1969
Bright Landing 1978
Upper Strata 1985
Her Ladyship 1991
*タイトルド 1996
キャッチータイトル 2003
メジャーエンブレム 2013（阪神JF、NHKマイルC、クイーンC）
Lord of Men 1993（サラマンドル賞）
Eastern Shore 1979
Flirtation 1994
Attraction 2001（英1000ギニー、愛1000ギニー、コロネーションS、サンチャリオットS、愛メイトロンS）
Danger Ahead 1982
Have A Care 1988
Tradizione 1994
Tradizione Slam 2007
Super Corinto 2018（ラテンアメリカ大賞、チリ競馬場大賞）
Cuidadosa Fitz 1997
Cuidadosa Halo 2004
Halo Holiday 2014（エンリケアセバル大賞、ラプラタオークス）
Luckhurst 1972
Stumped 1977
Sonic Lady 1983（愛1000ギニー、サセックスS、ムーラン・ド・ロンシャン賞）
*ソニンク 1996 ---ソニンク系へ
牝系図の出典：Galopp-Sieger、牝系検索α
血統表

| 0 | 1 | 2 | 3 | 4 |
| --- | --- | --- | --- | --- |
| ルーカスランド(Lucasland)の血統 | ルーカスランド(Lucasland)の血統 | ルーカスランド(Lucasland)の血統 | （血統表の出典） | （血統表の出典） |
| 父系 | フェアウェイ系  | フェアウェイ系  | フェアウェイ系  |  |
| 父 Lucero 1953 黒鹿毛 | 父の父*ソロナウエー 1946 鹿毛 | Solferino | Fairway | Fairway |
| 父 Lucero 1953 黒鹿毛 | 父の父*ソロナウエー 1946 鹿毛 | Solferino | Sol Speranza | Sol Speranza |
| 父 Lucero 1953 黒鹿毛 | 父の父*ソロナウエー 1946 鹿毛 | Anyway | Grand Glacier | Grand Glacier |
| 父 Lucero 1953 黒鹿毛 | 父の父*ソロナウエー 1946 鹿毛 | Anyway | The Widow Murphy | The Widow Murphy |
| 父 Lucero 1953 黒鹿毛 | 父の母Cuguan 1942 栗毛 | Fair Trial | Fairway | Fairway |
| 父 Lucero 1953 黒鹿毛 | 父の母Cuguan 1942 栗毛 | Fair Trial | Lady Juror | Lady Juror |
| 父 Lucero 1953 黒鹿毛 | 父の母Cuguan 1942 栗毛 | Tracemond | Abbots Trace | Abbots Trace |
| 父 Lucero 1953 黒鹿毛 | 父の母Cuguan 1942 栗毛 | Tracemond | Icemond | Icemond |
| 母 Lavant 1955 鹿毛 | 母の父Le Lavandou 1944 鹿毛 | Djebel | Tourbillon | Tourbillon |
| 母 Lavant 1955 鹿毛 | 母の父Le Lavandou 1944 鹿毛 | Djebel | Loika | Loika |
| 母 Lavant 1955 鹿毛 | 母の父Le Lavandou 1944 鹿毛 | Lavande | Rustom Pasha | Rustom Pasha |
| 母 Lavant 1955 鹿毛 | 母の父Le Lavandou 1944 鹿毛 | Lavande | Livadia | Livadia |
| 母 Lavant 1955 鹿毛 | 母の母Firle 1938 黒鹿毛 | Noble Star | Hapsburg | Hapsburg |
| 母 Lavant 1955 鹿毛 | 母の母Firle 1938 黒鹿毛 | Noble Star | Hesper | Hesper |
| 母 Lavant 1955 鹿毛 | 母の母Firle 1938 黒鹿毛 | Versicle | Sickle | Sickle |
| 母 Lavant 1955 鹿毛 | 母の母Firle 1938 黒鹿毛 | Versicle | Verdict | Verdict |
| 母系(F-No.) | (FN:B3) | (FN:B3) | (FN:B3) |  |
| 5代内の近親交配 | Phalaris 5.5×5、Son-in-Law 5×5、Desmond 5×5、Fairway 4×4（父内） | Phalaris 5.5×5、Son-in-Law 5×5、Desmond 5×5、Fairway 4×4（父内） | Phalaris 5.5×5、Son-in-Law 5×5、Desmond 5×5、Fairway 4×4（父内） |  |
出典: ↑    ↑    ↑   
半弟ソーブレスド（父Princely Gift）は1968年のジュライカップ勝ち馬。引退後には種牡馬として日本に輸入されている。
母Lavantの半妹Yasminの子孫にアイリッシュ1000ギニー勝ち馬のJet Setting（英語版）がいる。
4代母Verdictは1924年コロネーションカップ勝ち馬。
西インド (曖昧さ回避)

インド西部
西インド（にしインド、昔は「せいインド」）
西インド (en:Western India)。インド内務省が定める、インド国内の西部地域。
大航海時代における新世界のうち、アメリカ州の呼称。
西インド会社。17世紀から18世紀にアメリカ州との貿易を目的に設立された特許会社。
狭義には南北アメリカ大陸の間の西インド諸島。カリブ海、カリブ海地域も参照。
西インド連邦。1962年まで西インド諸島に存在したイギリス連邦内の自治領。
バリスタ (漫画)

| 漫画：バリスタ |
| --- | --- |
原作・原案など: 花形怜（原作・原案）
作画: むろなが供未
出版社: 芳文社
掲載誌: 週刊漫画TIMES
レーベル: 芳文社コミックス
発表期間: 2010年 - 2013年
巻数: 全10巻
テンプレート - ノート
プロジェクト: 漫画
ポータル: 漫画
『バリスタ』は、原作・原案：花形怜、漫画：むろなが供未による日本の漫画。2010年から2013年まで『週刊漫画TIMES』（芳文社）にて連載された。単行本は全10巻。
ストーリー

蒼井香樹はローマのバールで働く日本人バリスタ。イタリアを縦断し、カッフェ（コーヒー）の腕と知識を磨いた香樹は、客のどんな注文にも笑顔で応えることが出来ると、現地で高い評価を得ていた。
ある日、香樹はイタリアに700以上あるとも言われるコーヒー豆焙煎所の最大手で、バールチェーンでもあるエリジオ・ソーラ社に呼ばれ、同社が日本にオープンさせた1号店のバリスタにならないかとヘッドハントされる。本場のカッフェを日本に広めるための伝道師として意気揚々と帰国した香樹だったが、1号店で待っていたのは見習いとしての扱いだった。
単行本

原作・原案：花形怜、漫画：むろなが供未 『バリスタ』 芳文社〈芳文社コミックス〉、全10巻
第1巻 2010年03月31日発売 ISBN 978-4-8322-3196-2
第2巻 2010年07月15日発売 ISBN 978-4-8322-3209-9
第3巻 2010年11月16日発売 ISBN 978-4-8322-3224-2
第4巻 2011年03月16日発売 ISBN 978-4-8322-3237-2
第5巻 2011年07月16日発売 ISBN 978-4-8322-3256-3
第6巻 2011年11月16日発売 ISBN 978-4-8322-3272-3
第7巻 2012年04月16日発売 ISBN 978-4-8322-3291-4
第8巻 2012年11月15日発売 ISBN 978-4-8322-3330-0
第9巻 2013年05月16日発売 ISBN 978-4-8322-3352-2
第10巻 2013年11月16日発売 ISBN 978-4-8322-3379-9
野宮範子

野宮 範子（のみや のりこ、1959年3月14日 - ）は、日本のフリーアナウンサー。元北海道放送 (HBC) のアナウンサー。
北海道室蘭市出身。北海道室蘭栄高等学校、早稲田大学教育学部国語国文学科卒業。大学時代は早稲田スポーツ新聞会所属。
夫は、同じく元HBCアナウンサーでフリーアナウンサーの桜井宏。桜井との間に一男あり。
担当番組 > 北海道放送

テレポート6
ほっとないとHOKKAIDO
決定!全日本歌謡選抜
担当番組 > フリー転向後

情報ワイド 夕方Don!Don!（北海道テレビ）
イチオシ!（北海道テレビ）
F+ (AIR-G')
万世閣 T3 ティーキュービック (AIR-G')
Vivid Couleur (AIR-G')
野宮的コフレ (AIR-G')
さあ!トークだよ（北海道文化放送） - 月曜・火曜担当
助川氏

助川氏（すけがわし）は日本の氏族のひとつ。介河、介川とも。
助川氏概略

助川氏の本姓は藤原氏。家系は藤原秀郷の流れを汲む小野崎氏。代々、久慈郡大門村大門城に居り、助川右衛門通繁は主君佐竹義舜が佐竹氏傍流の山入氏より本城太田城を追われた際、建議して、自らの居城を修築してこれを迎え入れ、義舜が太田城に復帰する2年間、主君を守り続けたという。
その子出羽守通厚も義舜に仕えて功を挙げるという。また、『新編国志補遺』によれば天正13年（1585年）、周防守里通は本村松盛院に什物を寄こすとある。
介河氏・介川氏

また、助川氏、その一族多く分出し、家名も介河、介川などに分かれるという。
介河氏・介川氏 > 秋田藩士 介河氏・介川氏

介河氏
本姓は藤原氏。慶長7年（1602年）、隼人の代に常陸国より平鹿郡横手に住まい、道政の代に秋田城下に移り住むという。知行は45石。

なお、「秋田武鑑」では道賢(七右衛門)との関係が不分明ながら介川通景(東馬)をこの家の出身としている。
系譜 介河将監―次郎右衛門一道満―次郎右衛門―和泉守―隼人―十兵衛―道政一道次―道賢
介川通長流
介川通長は慶長7年（1602年）、常陸国より秋田に移住するという。
系譜 介川通長一通央一通婚L―通意―木工右衛門通頼
介川通重流
介川通重は慶長7年（1602年）、常陸国より秋田に移住するという。
系譜 通重一通光一通古―清右衛門
水戸藩士・義民たる介川氏・助川氏

介川善之介 諱は常徳。板橋常裕の子で介川以直の養子となる。13石3人扶持。元治元年(1864年)天狗党に加わり、捕らわれる。享年33。靖国神社合祀。
介川治三郎 水戸藩士。押役。諱は正勝。天狗党の乱に加わり、捕らわれる。慶応元年(1865年)7月6日、下総国佐倉で獄死。享年26。靖国神社合祀。
介川秋三郎 水戸藩士。目付同心組。諱は広政。天狗党に加わり、捕らわれる。慶応元年(1865年)7月16日で安房勝山で獄死。享年45。靖国神社合祀。
助川平四郎 常陸国の百姓。元治元年(1864年)、水戸で斬首。靖国神社合祀。
小笠原倫明

小笠原 倫明（おがさわら みちあき、1954年1月29日 - ）は日本の行政官。宮城県仙台市出身。民主党政権下で総務事務次官を務めたが、政権交代後、河相周夫外務事務次官、真砂靖財務事務次官、金子順一厚生労働事務次官、坂篤郎日本郵政社長などとともに就任1年未満で解任された。
概要

1976年 京都大学経済学部卒業、郵政省入省
1990年 郵政省電気通信局電気通信事業部データ通信課ネットワーク化推進室長
1991年 郵政省大臣官房文書課調査官
1992年 郵政省電気通信局電気通信事業部事業政策課調査官
1994年 郵政省電気通信局電気通信事業部業務課長
1995年 郵政省電気通信局電気通信事業部事業政策課長
1997年 郵政省大臣官房国際部国際政策課長
1998年 郵政省通信政策局政策課長
1999年 郵政省放送行政局総務課長
2001年
1月6日 総務省情報通信政策局総務課長
7月6日 総務省大臣官房参事官（大臣官房総務課担当）
2002年 総務省大臣官房総務課長
2003年1月17日 総務省東北総合通信局長
2004年 総務省関東総合通信局長
2005年
総務省大臣官房審議官（情報通信政策局担当)
総務省自治行政局公務員部長
2006年 総務省消防庁国民保護・防災部長
2007年 総務省情報通信政策局長
2008年 総務省情報通信国際戦略局長
2010年1月15日 総務審議官（郵政・通信）
2012年9月11日 総務事務次官、旧郵政省出身者が次官に就任するのは2010年1月以来。
2013年
6月 退任、総務省顧問
9月28日 総務省顧問退任
10月15日 株式会社大和総研顧問
一般財団法人日本ITU協会理事長
2015年
6月 株式会社大和証券グループ本社取締役、株式会社スカパーJSATホールディングス取締役、公益財団法人科学技術融合振興財団理事、一般財団法人財政金融企画事務所理事
7月 損害保険ジャパン日本興亜株式会社顧問
2017年7月19日 一般社団法人ドローン操縦士協会理事
2018年6月 一般財団法人マルチメディア振興センター理事長
ふるさとTV副会長、一般社団法人世界貿易センター東京理事、一般社団法人日本ミャンマー協会理事、住友商事株式会社顧問
2024年 瑞宝重光章受章
脚註

↑  河北新報、2012年9月28日朝刊3頁
↑  （世界ICTサミット2008 | 講師略歴
↑  （新社長）総務次官に小笠原氏発表 ：日本経済新聞
↑
↑  「役員人事について」株式会社大和証券グループ本社
↑  「」
↑  ふるさとTV
↑
↑  『令和6年春の受勲 勲章受章者名簿』（PDF）（プレスリリース）総務省、2024年4月29日。https://www.soumu.go.jp/main_content/000944343.pdf。2024年4月29日閲覧。
↑  『官報』号外第106号、令和6年4月30日
| 公職    |
| --- | --- | --- |
| 先代 岡本保 |  総務事務次官 2012年 - 2013年 | 次代 岡崎浩巳 |
| 先代 鈴木康雄 |  総務審議官（郵政・通信担当） 2010年 - 2012年 | 次代 桜井俊 |
レウケー

レウケー（Leuke, 古希: Λεύκη, Leukē）は、ギリシア神話に登場するニュンペー。オーケアニデスの一人。長母音を省略してレウケとも表記される。
レウケーは冥界の王ハーデースに見初められて冥界に連れて行かれたが、彼女は完全な不死の神ではなかった為に死んでしまった。これを悲しんだハーデースは、レウケーを白ポプラ（ギンドロの意味）に変えたという（なお、レウケーとは『白い』という意味）。それ以来、エーリュシオンには白ポプラが繁っているという。
後にヘーラクレースは12功業の一つとして冥界を訪れた時、エーリュシオンのレウケーの木から冠を作ったという。
濡れ

| --- | --- |
: 「濡れ」の語義については、ウィクショナリーの「ぬれる」の項目をご覧ください。
ぬれの例。木の葉が水を撥くため、接触角が大きい。
ぬれ（英語: wetting）は、固体表面に接触している気体が液体に置き換えられる現象である。産業上は接合・接着（ろう接など）や防水加工に利用されるため、ぬれ現象の解明、制御の方法などが研究されている。
現象

液体や固体の物質が、気体のように散逸せずにまとまりを維持するのは、それらの内部の原子や分子同士が互いに引き付け合っているためであるが、表面ではその力が物質の面方向に強くはたらき表面張力となって現れる。容器に収められ重力以外の外力を受けていない液体では、自重と表面張力のつり合いによって外形が定まるが、固体では固有の外形を維持する力が強いため表面張力が観察されにくい。ただし、固体と液体が接触する時は液体だけでなく固体の表面張力も顕在化する。液体の表面張力に比べて固体の表面張力が大きいと、固体に接触した液体は自ら球形になろうとするよりも固体の表面に広がろうとして良くぬれる。固体と液体が接触した場合の両者の表面張力の違いによってぬれの度合いが異なってくる。