logo

TechCodeview

赤黒木の紹介

二分探索木 基本的なものです データ構造、 ただし、ツリーのバランスが崩れると、パフォーマンスが低下する可能性があります。 赤黒の木々 の一種です バランス二分探索木 一連のルールを使用してバランスを維持し、次のような操作の対数的な時間の複雑さを確保します。 挿入、削除、検索 ツリーの初期形状に関係なく。 赤黒の木々 変更のたびに簡単な色分けスキームを使用してツリーを調整し、自己バランスをとります。

赤黒の木



目次

赤黒木とは何ですか?

あ 赤黒の木 自己バランス調整です 二分探索木 ここで、各ノードには追加の属性、つまり色があり、次のいずれかになります。 赤 または 黒 。これらのツリーの主な目的は、挿入と削除中にバランスを維持し、効率的なデータの取得と操作を保証することです。

1 ～ 100 のローマ字番号

赤黒木の性質

あ 赤黒の木 には次の特性があります。



  1. ノードの色 : 各ノードは赤または 黒 。
  2. ルートプロパティ : 木の根元は常に 黒 。
  3. レッドプロパティ : 赤いノードは赤い子を持つことができません (パス上に 2 つの連続する赤いノードはありません)。
  4. ブラックプロパティ : ノードからその子孫の null ノード (葉) までのすべてのパスには、同じ数の 黒 ノード。
  5. リーフプロパティ : すべてのリーフ (NIL ノード) は 黒 。

これらのプロパティにより、ルートからリーフまでの最長パスの長さが最短パスの 2 倍を超えないようになり、ツリーのバランスと効率的なパフォーマンスが維持されます。

赤黒木の例

の 正しい赤黒ツリー 上の画像では、ルートからリーフ ノードまでのすべてのパスに同じ数の黒いノードがあることが保証されます。この場合、1 つあります (ルート ノードを除く)。



の 間違った赤黒木 としての赤黒特性に従いません。 2つの赤いノード 互いに隣接しています。もう 1 つの問題は、リーフ ノードへのパスの 1 つに黒いノードがまったくないのに、他の 2 つのパスには黒いノードが含まれていることです。

なぜ赤黒の木なのでしょうか？

ほとんどの BST 操作 (検索、最大、最小、挿入、削除など) には時間がかかります。 おお） h は高さです。 BST 。これらの操作にかかるコストは、 の上） 歪んでいる 二分木。 木の高さを残しておけば O(log n) 挿入と削除のたびに、上限を保証できます。 O(log n) これらすべての操作に。赤黒木の高さは常に O(log n) ここで、n はツリー内のノードの数です。

tostringメソッドJava
Noさん。アルゴリズム時間計算量
1.検索O(log n)
2.入れるO(log n)
3.消去O(log n)

比較 AVL ツリー :

AVL ツリーは、赤黒ツリーに比べてバランスが取れていますが、挿入および削除中により多くの回転が発生する可能性があります。したがって、アプリケーションで頻繁に挿入と削除が行われる場合は、赤黒ツリーを優先する必要があります。挿入と削除の頻度が低く、検索の操作がより頻繁である場合、 AVLツリー 赤黒ツリーよりも優先されるべきです。

赤黒の木はどのようにしてバランスを確保するのでしょうか?

バランスを理解するための簡単な例は、赤黒ツリーでは 3 つのノードのチェーンが不可能であるということです。色の任意の組み合わせを試し、そのすべてが赤黒ツリーのプロパティに違反するかどうかを確認できます。

3 ノードの赤黒ツリーの適切な構造

Red-Black Tree の興味深い点:

  • の 黒 赤黒ツリーの高さは、ルート ノードからリーフ ノードまでのパス上の黒いノードの数です。リーフノードも次のようにカウントされます。 黒 ノード。それで、高さのある赤黒の木 h もっている 黒の高さ>= h/2 。
  • 赤黒の木の高さ n ノードは h<= 2 対数 2 (n + 1) 。
  • すべての葉 (NIL) は、 黒 。
  • の 黒 ノードの深さは、ルートからそのノードまでの黒いノードの数、つまり黒い祖先の数として定義されます。

赤黒ツリーの基本操作:

赤黒ツリーの基本的な操作には次のものが含まれます。

intからcharへ
  1. 挿入
  2. 検索
  3. 削除
  4. 回転

1. 挿入

赤黒ツリーに新しいノードを挿入するには、次の 2 段階のプロセスが必要です。 二分探索木 (BST) の挿入 、続いて赤黒プロパティの違反を修正します。

挿入手順

  1. BSTインサート : 標準の BST と同様に新しいノードを挿入します。
  2. 違反を修正する :
    • 新しいノードの親が 黒 、プロパティは違反されていません。
    • もし親が 赤 、ツリーが Red プロパティに違反している可能性があるため、修正が必要です。

挿入中の違反を修正する

新しいノードを 赤 ノードでは、ノードの親と叔父 (親の兄弟) の色に応じて、いくつかのケースが発生する可能性があります。

  • ケース 1: おじさんは赤い : 親と叔父を次のように色変更します。 黒 、そして祖父母は 赤 。次に、ツリーを上に移動して、さらに違反がないか確認します。
  • ケース 2: おじさんは黒人 :
    • サブケース 2.1: ノードは正しい子です : 親に対して左回転を実行します。
    • サブケース 2.2: ノードは左の子です : 祖父母に対して右回転を実行し、適切に色を変更します。

2. 検索する

赤黒ツリー内のノードの検索は、標準のノードの検索と似ています。 二分探索木 (BST) 。検索操作は、 根 に 葉 、ターゲット値と現在のノードの値を比較し、それに応じて左または右に移動します。

検索手順

  1. ルートから始める : ルート ノードから検索を開始します。
  2. 木を横断する :
    • ターゲット値が現在のノードの値と等しい場合、ノードが見つかります。
    • ターゲット値が現在のノードの値より小さい場合は、左側の子に移動します。
    • ターゲット値が現在のノードの値より大きい場合は、右側の子に移動します。
  3. 繰り返す : ターゲット値が見つかるか、NIL ノードに到達する (値がツリーに存在しないことを示す) まで、このプロセスを続けます。

3. 削除

Red-Black Tree からノードを削除するには、BST の削除を実行し、続いて発生した違反を修正するという 2 段階のプロセスが必要です。

削除手順

  1. BSTの削除 : 標準の BST ルールを使用してノードを削除します。
  2. フィックスダブルブラック :
    • 黒ノードが削除されると、二重黒状態が発生する可能性があり、特定の修正が必要になります。

削除時の違反の修正

黒ノードが削除されると、兄弟の色とその子の色に基づいて二重黒の問題を処理します。

  • ケース 1: 兄弟は赤です : 親を回転し、兄弟と親の色を変更します。
  • ケース 2: 兄弟が黒人である :
    • サブケース 2.1: 兄弟の子供は黒人である : 兄弟の色を変更し、二重の黒を上に伝播させます。
    • サブケース 2.2: 兄弟の子供の少なくとも 1 人が赤毛である :
      • 兄弟の遠い子が赤い場合 : 親と兄弟に対して回転を実行し、適切に色を変更します。
      • 兄弟の近くの子供が赤い場合 : 兄弟とその子を回転し、上記と同様に処理します。

4. 回転

回転は、赤黒ツリー (RBT) のバランスの取れた構造を維持するための基本的な操作です。これらはツリーのプロパティを維持するのに役立ち、根から葉までの最長パスが最短パスの長さの 2 倍を超えないようにすることができます。回転には 2 つのタイプがあります。 左回転 そして 右回転。

1. 左回転

ノード 𝑥 での左回転 バツ 動きます 𝑥 バツ 左とその右の子 𝑦 まで そして 𝑥まで バツ の場所。

左回転の可視化 
Before Rotation:  x      y   /    a b  After Left Rotation:  y  /   x b  /  a>

左回転ステップ:

  1. セット そして ～の正しい子供になること バツ 。
  2. 動く そして の左サブツリーを バツ の右側のサブツリー。
  3. の親を更新します バツ そして そして 。
  4. アップデート バツ の親が指す そして の代わりに バツ 。
  5. セット そして が残した子供 バツ 。
  6. アップデート バツ の親は そして 。

左回転の擬似コード:

左回転 
// Utility function to perform left rotation void leftRotate(Node* x) {  Node* y = x->右;  x->右 = y->左;  if (y->left != NIL) { y->left->parent = x;  y->親 = x->親;  if (x->parent == nullptr) { root = y;  } else if (x == x->parent->left) { x->parent->left = y;  } else { x->親->右 = y;  y->left = x;  x->親 = y; }>>

2. 右回転

ノード 𝑥 での右回転 バツ 動きます 𝑥 バツ 右とその左の子 𝑦 まで そして 𝑥まで バツ の場所。

クラスタリング
右回転の視覚化: 
Befor Right Rotation:   x  /  y  /   a b After Right Rotation:  y  /   a x  /  b>

右回転のステップ:

  1. セット そして ～の左の子になる バツ 。
  2. 動く そして の右側のサブツリーを バツ の左サブツリー。
  3. の親を更新します バツ そして そして 。
  4. アップデート バツ の親が指す そして の代わりに バツ 。
  5. セット そして の右の子 バツ 。
  6. アップデート バツ の親は そして 。

右回転の擬似コード:

C++ 
// Utility function to perform right rotation void rightRotate(Node* x) {  Node* y = x->左;  x->左 = y->右;  if (y->right != NIL) { y->right->parent = x;  y->親 = x->親;  if (x->parent == nullptr) { root = y;  } else if (x == x->parent->right) { x->parent->right = y;  } else { x->親->左 = y;  y->right = x;  x->親 = y; }>>

ローテーションをいつ実行するか?

赤黒ツリーの回転は通常、ツリーのプロパティを維持するために挿入および削除中に実行されます。ローテーションのシナリオは次のとおりです。

1. 挿入後の違反の修正

新しいノードが挿入されると、常に赤色で表示されます。これにより、特に次のような Red-Black Tree プロパティの違反が発生する可能性があります。

  • ルートは次のとおりである必要があります 黒 。
  • 赤 ノードは持つことができません 赤 子供たち。

インサートを固定する場合のケース分析:

  • ケース 1: 再カラーと上方向への伝播
    • 新しいノードの親と叔父が両方とも 赤 、親と叔父を次のように色変更します。 黒 、そして祖父母は 赤 。次に、修正を祖父母に再帰的に適用します。
  • ケース 2: 回転と再着色
    • 新しいノードの叔父が 黒 新しいノードが左の子の右の子である場合 (またはその逆)、回転を実行して新しいノードを上に移動して位置合わせします。
    • 新しいノードの叔父が 黒 新しいノードが左の子の左の子 (または右の右) である場合は、回転を実行し、親と祖父母の色を変更して違反を修正します。

2. 削除後の違反の修正

削除後、プロパティを復元するためにツリーを修正する必要がある場合があります。

  • 黒のノードが削除されるか、赤のノードが黒のノードに置き換えられると、二重黒の状況が発生する可能性があります。

削除を修正するためのケース分析:

ラドヤード・キプリングの言葉を言い換えると
  • ケース 1: 兄弟は赤です
    • 兄弟と親の色を変更し、回転を実行します。
  • ケース 2: 兄弟が黒人で、子供が黒人である場合
    • 兄弟の色を赤に変更し、問題を親に移動します。
  • ケース 3: 兄弟が黒人で、少なくとも 1 人の赤人の子供がいる
    • 回転して色を変更して、二重黒の問題を修正します。

赤黒ツリーの実装:

以下は、挿入、検索、回転機能を含む Red-Black Tree の詳細な実装です。

C++ 
#include  using namespace std; // Node structure for the Red-Black Tree struct Node {  int data;  string color;  Node *left, *right, *parent;  Node(int data)  : data(data)  , color('RED')  , left(nullptr)  , right(nullptr)  , parent(nullptr)  {  } }; // Red-Black Tree class class RedBlackTree { private:  Node* root;  Node* NIL;  // Utility function to perform left rotation  void leftRotate(Node* x)  {  Node* y = x->右;  x->右 = y->左;  if (y->left != NIL) { y->left->parent = x;  y->親 = x->親;  if (x->parent == nullptr) { root = y;  } else if (x == x->parent->left) { x->parent->left = y;  } else { x->親->右 = y;  y->left = x;  x->親 = y;  } // 右回転を実行するユーティリティ関数 void rightRotate(Node* x) { Node* y = x->left;  x->左 = y->右;  if (y->right != NIL) { y->right->parent = x;  y->親 = x->親;  if (x->parent == nullptr) { root = y;  } else if (x == x->parent->right) { x->parent->right = y;  } else { x->親->左 = y;  y->right = x;  x->親 = y;  // 挿入後に Red-Black Tree プロパティを修正する関数 void fixInsert(Node* k) { while (k != root && k->parent->color == 'RED') { if (k->parent == k->parent->parent->left) { Node* u = k->parent->parent->right; // おじさん if (u->color == 'RED') { k->parent->color = 'BLACK';  u->color = 'BLACK';  k->親->親->色 = 'RED';  k = k->親->親;  } else { if (k == k->親->right) { k = k->親;  leftRotate(k);  k->親->色 = 'BLACK';  k->親->親->色 = 'RED';  rightRotate(k->親->親);  } } else { ノード * u = k->親->親->左; // おじさん if (u->color == 'RED') { k->parent->color = 'BLACK';  u->color = 'BLACK';  k->親->親->色 = 'RED';  k = k->親->親;  } else { if (k == k->parent->left) { k = k->parent;  rightRotate(k);  k->親->色 = 'BLACK';  k->親->親->色 = 'RED';  leftRotate(k->親->親);  ルート->カラー = 'BLACK';  } // インオーダートラバーサルヘルパー関数 void inorderHelper(Node* node) { if (node != NIL) { inorderHelper(node->left);  コート<< node->データ<< ' ';  inorderHelper(node->右）;  } } // 検索ヘルパー関数 Node* searchHelper(Node* node, int data) { if (node == NIL || data == node->data) { return node;  if (データ< node->data) { return searchHelper(node->left, data);  return searchHelper(node->right, data);  } public: // コンストラクター RedBlackTree() { NIL = new Node(0);  NIL->カラー = 'BLACK';  NIL->左 = NIL->右 = NIL;  ルート = NIL;  } // 挿入関数 void insert(int data) { Node* new_node = new Node(data);  new_node->left = NIL;  new_node->right = NIL;  ノード * 親 = nullptr;  ノード* 現在 = ルート;  // BST 挿入 while (current != NIL) {parent = current;  if (新しいノード->データ< current->データ) { 現在 = 現在->左;  } else { 現在 = 現在->右;  new_node->parent = 親;  if (parent == nullptr) { root = new_node;  else if (new_node->data< parent->データ) { 親 -> 左 = 新しいノード;  } else { 親->右 = new_node;  } if (new_node->parent == nullptr) { new_node->color = 'BLACK';  戻る;  if (new_node->parent->parent == nullptr) { return;  fixInsert(new_node);  } // インオーダートラバーサル void inorder() { inorderHelper(root); } // 検索関数 Node* search(int data) { return searchHelper(root, data);  } }; int main() { RedBlackTree rbt;  // 要素の挿入 rbt.insert(10);  rbt.挿入(20);  rbt.挿入(30);  rbt.挿入(15);  // 順序トラバーサル cout<< 'Inorder traversal:' << endl;  rbt.inorder(); // Output: 10 15 20 30  // Search for a node  cout << '
Search for 15: '  << (rbt.search(15) != rbt.search(0))  << endl; // Output: 1 (true)  cout << 'Search for 25: '  << (rbt.search(25) != rbt.search(0))  << endl; // Output: 0 (false)  return 0; }>

赤黒木の利点:

  • バランスの取れた: 赤黒ツリーは自己バランス型です。つまり、左右のサブツリーの高さのバランスが自動的に維持されます。これにより、検索、挿入、削除の操作には最悪の場合でも O(log n) 時間がかかることが保証されます。
  • 効率的な検索、挿入、削除: バランスの取れた構造により、赤黒木は効率的な運用を実現します。検索、挿入、削除には、最悪の場合でも O(log n) 時間がかかります。
  • 実装が簡単: Red-Black Tree プロパティを維持するためのルールは、比較的単純で実装が簡単です。
  • 広く使われています： 赤黒ツリーは、マップ、セット、優先キューなどのさまざまなデータ構造を実装するための一般的な選択肢です。

赤黒木の短所:

  • 他のバランスの取れたツリーよりも複雑です。 AVL ツリーのような単純なバランス ツリーと比較して、赤黒ツリーにはより複雑な挿入ルールと削除ルールがあります。
  • 一定のオーバーヘッド: Red-Black Tree プロパティを維持すると、すべての挿入および削除操作にわずかなオーバーヘッドが追加されます。
  • すべてのユースケースに最適なわけではありません。 Red-Black Tree はほとんどの操作では効率的ですが、頻繁な挿入と削除が必要なアプリケーションには、一定のオーバーヘッドが大きくなる可能性があるため、最適な選択ではない可能性があります。

赤黒木の用途:

  • マップとセットの実装: 赤黒ツリーは、効率的な検索、挿入、削除が重要なマップやセットの実装によく使用されます。
  • 優先キュー: 赤黒ツリーを使用すると、優先度に基づいて要素が順序付けされる優先キューを実装できます。
  • ファイルシステム: 赤黒ツリーは、ファイルとディレクトリの構造を管理するために一部のファイル システムで使用されます。
  • インメモリデータベース: Red-Black Tree は、データを効率的に保存および取得するために、インメモリ データベースで使用されることがあります。
  • グラフィックスとゲーム開発: 赤黒の木はグラフィックスとゲームで使用できます 発達 衝突検出や経路探索などのタスクに使用します。

Red-Black Tree に関するよくある質問 (FAQ):

1. 赤黒木とは何ですか?

赤黒ツリーは、左右のサブツリーの高さのバランスを維持する自己平衡型二分探索ツリーです。これにより、検索、挿入、削除の操作には最悪の場合でも O(log n) 時間がかかることが保証されます。 Red-Black Tree は、効率的なデータ構造が必要なさまざまなアプリケーションで広く使用されています。

2. 赤黒の木はどのようにしてバランスを保っているのでしょうか?

赤黒ツリーは、ノードの色 (赤または黒) とノード間の関係に特定のルールを適用することでバランスを維持します。これらのルールにより、ツリーのバランスが保たれ、左右のサブツリーの高さの差が最大 1 になることが保証されます。

3. 赤黒ツリーを使用する利点は何ですか?

  • バランスのとれた: Red-Black Tree は自己バランス機能を備えており、効率的な検索、挿入、削除操作を保証します。
  • 効率的： これらは、ほとんどの操作で O(log n) 時間の複雑さを提供します。
  • 実装が簡単: Red-Black Tree のプロパティを維持するためのルールは比較的簡単です。
  • 広く使われています： これらは、さまざまなデータ構造やアルゴリズムを実装するための一般的な選択肢です。

4. 赤黒ツリーを使用するデメリットは何ですか?

  • AVL ツリーのような単純なバランス ツリーと比較して、赤黒ツリーにはより複雑な挿入ルールと削除ルールがあります。
  • Red-Black Tree プロパティを維持すると、すべての挿入および削除操作にわずかなオーバーヘッドが追加されます。
  • 挿入と削除が頻繁に行われるアプリケーションの場合は、他のバランスの取れたツリー構造の方が適している可能性があります。

5. 赤黒木の一般的な用途にはどのようなものがありますか?

  • マップとセットの実装
  • 優先キュー
  • ファイルシステム
  • インメモリデータベース
  • グラフィックスおよびゲーム開発 (衝突検出、経路探索)
  • DSA における Red-Black Tree の定義と意味
  • 自己平衡二分探索ツリー
  • レッドブラックツリーvsAVLツリー
  • ヒープと赤黒ツリーの違いは何ですか?
  • 赤黒ツリーへの挿入
  • 赤黒ツリーの削除
  • 赤黒の木トップダウン挿入