赤黒木の紹介

1. 序章

この記事では、赤黒木とは何か、そしてなぜそれらがそのような人気のあるデータ構造であるのかを学びます。

まず、二分探索木と2〜3木を見ていきます。 ここから、赤黒木がバランスの取れた2〜3本の木の異なる表現と見なされる方法を見ていきます。

この記事の目的は、赤黒木を簡単な方法で説明することです。そのため、挿入と削除のすべての可能なケースのコード例や詳細な例については詳しく説明しません。

2. 二分探索木

二分探索木（BST）は、すべてのノードに0、1、または2つの子ノードがあるツリーです。 子ノードのないノードはリーフと呼ばれます。 さらに、ノードの左の子の値はノードの値よりも小さく、右の子の値はノードの値よりも大きくする必要があります。

簡単な例から始めましょう：

要素4、8、12、16、18、24、32があります。 要素16をルート（a）としてツリーを開始し、8と24（b）を挿入し、最終的に要素を挿入できます。 4、12、18 、および 32 （c）。 左の子は常に親よりも小さく、右の子は常に親よりも大きいことに注意してください。 ツリーの高さがlognであり、nが要素の数であることが簡単にわかります。

ツリー内の要素を検索する場合は、ルートから始めることができます。 探している要素がルートと等しい場合、これで完了です。 小さい場合は左に検索を続け、大きい場合は右に検索を続けます。 要素が見つかるまで、またはリーフノード（黄色）に到達するまで続行します。 検索の時間計算量がO（log n）になることは非常に簡単です。

ただし、ツリーの構造は、要素が挿入される順序に大きく依存します。 24、32、16、18、12、8、4 の順序で要素を挿入すると、結果のツリーはバランスが取れなくなります（d）。 ソートされた順序で要素を挿入すると、結果はノードごとに1つの子のみを持つツリーになります（e）。 これは実際にはリストであり、ツリーではありません。 つまり、最悪の場合の検索の複雑さと要素は O（n）です。

3. バランスの取れた2〜3木

3.1. 2-3ツリーの定義

次に、2〜3の木を見ていきます。これは、要素をツリーに挿入する順序に関係なく、バランスの取れたツリーを維持するのに役立ちます。 2-3ツリーは、2種類のノードを持つツリーです。 2ノードには1つの値と2つの子ノードがあり（ここでも、左側の子の値は小さく、右側の子の値は大きくなります）、3ノードには2つの値と3つの子ノードがあります。

3ノードの左の子は、親の左の値よりも小さくなっています。 真ん中の子の値は2つの親の値の中間にあり、右の子の値は親の右の値よりも大きくなっています。

 3.2. 2-3ツリーへの要素の挿入

ツリーのバランスを保ちながら、要素 32、24、18、16、12、8、4を2-3ツリーに挿入する方法を見てみましょう。

32 から始めます。これにより、ルートノード（a）のみを持つツリーが得られます。 次に、 24 を挿入します。これにより、ルートに3ノードが得られます（b）。

次に、ルートの左の子として次の要素 18 を挿入します（18は24よりも小さいため）。 これにより、ツリーのバランスが崩れます。 24 を3ノードから移動し、ルートノードにすることで、バランスの取れたツリーを取得できます。

結果は、2ノードのみのバランスの取れたツリーになります（b）。

次に挿入する要素は16です。 ここでも、不均衡なツリー（a）で終わります。 今回は、 16 を1レベル上に移動するだけで、 18 （b）と一緒に3ノードを形成できます。

次に、作成した3ノードの左の子として 12 を挿入します（a）。 ツリーのバランスをとるために、最初に 12 を1レベル上に移動して、一時的な4ノードを形成します（b）。

これで、中央の要素 16 をルートに移動して、4ノードを分割できます。これにより、バランスの取れたツリーが得られます（c）。

8 の挿入は非常に簡単になりました。最初に、 12 （a）の左の子を作成し、次に要素を1レベル上に移動して、で3ノードを形成します。 12 （b）。

最後に挿入する要素4を使用すると、挿入が少し複雑になります。 まず、左（a）を作成し、それを1レベル上に移動して、一時的な4ノード（b）を作成します。 これで、中央の要素 8 を1レベル上に移動して、ルートに4ノードを取得できます（c）。

最後のステップでは、ルートノードとして 16 を抽出することにより、4ノードを分割します（d）。

3.3. 挿入の複雑さ

上記の例は、バランスの取れたツリーを維持するような方法で要素を挿入できることを示しています。 ただし、挿入ごとに実行する操作は、コードで表現するのが非常に複雑です。 その理由は、3つの異なるタイプのノード（2ノード、3ノード、および4ノード）が必要なためです。

さらに、要素を3ノードまで移動して3ノードにマージしたり、3ノードを2ノードに分割したりするには、いくつかの異なるケースを区別する必要があります。

次のセクションでは、赤黒木がこの複雑さを軽減するのにどのように役立つかを見ていきます。

4. 赤黒木

4.1. 2-3木との対応

赤黒木は本質的に2-3の木の異なる表現です。 例に直接飛び込みましょう：

（a）のツリーは、前のセクションで見たように2〜3ツリーを示しています。 3つのノードを赤でマークしました。これにより、赤黒木に直接アクセスできます。 すべての3ノードを2つの2ノードに分割し、2つの間のリンクを赤でマークします。

これはまた、赤黒木の2つの主要な特性に直接つながります。

• 赤いリンクの後には常に2つの黒いリンクが続きます（分割した3ノードの後に3つの黒いリンクが続くため）。
• ルートからリーフノードへのパスには、常に同じ数の黒いリンクが含まれています（これは、2〜3ツリーのバランスが取れているという事実から直接得られます）。

さらに、次の2つの条件を追加します。

• 左の子（小さい子ノード）へのリンクのみが赤になります。 この条件により、実装がさらに簡素化されます。
• すべての葉にはヌルリンク（nil）があります。

4.2. なぜこの表現？

つまり、ツリーの実装と操作が簡素化されます。 バイナリツリーの場合と同じ操作を使用できます（たとえば、値の検索は「通常の」バイナリツリーの場合とまったく同じように機能します）。

4.3. 挿入

赤黒木に新しい値を挿入するには、新しいリーフノードとして新しいノードを追加します。 もちろん、これは不均衡なツリーにつながります。 ツリーのバランスをとるために、最初に新しいノードへのリンクを赤で色付けします。

次に、ツリーのバランスを取り直すために必要な操作は3種類だけです。 これらの操作を見てみましょう。

最初の操作は左回転です。 ここでは、2つのリンクを移動して、サブツリー（a）をサブツリー（b）に変換します。

2番目の操作は右回転です。これは左回転の正反対です。

3番目の操作は色の反転です。 2つの赤いリンクを2つの黒いリンクに変更し、親リンクを赤いリンクに変更できます。

ここで重要なのは、3つの操作すべてがローカル操作であるということです。つまり、ツリー全体に影響を与えることはありません。

この記事では、挿入の完全な例については説明しません。 ここで強調する主なポイントは、これらの3つの簡単な操作により、ツリーのバランスを簡単に再調整できることです。

4.4. 挿入の例

赤黒木に要素を挿入する例を見てみましょう。 挿入する要素は37（オレンジ色の背景）で、ルートは青色の背景で表示されます。

まず、ルートから始めて、要素を挿入するリーフノードが見つかるまでツリーを歩きます。 この場合、 37 がツリーの最大の要素になるため、右端にあります。 新しいノードへのリンクはredで、（a）に示すようなツリーが表示されます。

親要素36に2つの赤いリンクがあるため、2番目のステップは flip-colors 操作であり、（b）に示すようなツリーに移動します。

値が28のノードには2つの赤いリンクがあるため、3番目のステップは flip-colors 操作であり、（c）に示すようなツリーになります。

すべての赤いリンクを左に傾けたいので、 left-rotation を実行します。これにより、 28 をルートとして、（d）のツリーにつながります。 ツリーのバランスが取れていることが簡単にわかります。

4.5. 消す

ノードを削除した後、同じ3つの操作を使用してツリーのバランスを取り直すことができます。 この記事では、完全な実装については説明しませんが、アイデアの概要を説明し、要素を削除する例をいくつか示します。

すべての例で、次の（有効な）赤黒木から始めます。

些細なケースは、赤いリンクを持つリーフノードの削除です。 2と36を削除する2つの考えられるケースを見てみましょう。

削除2

これが最も簡単なケースです。 要素2は赤いリンクの左側のノードであるため、要素を削除して、バランスを取り直すことなく、有効な赤黒木を直接取得できます。

36を削除

36 を削除する場合は、ノードを再度削除しますが、 36 は赤いリンクの右側のノードであるため、リンクを28[から変更する必要があります。 から36は、32を指します。 ここでも、有効な赤黒木が得られます。

削除8

非リーフノードを削除する場合は、最初にリーフノードにすることができます。 そのために、左側のサブツリーの最大要素または右側のサブツリーの最小要素を見つけます。 この交換では、赤黒木のプロパティは変更されません。 すべてのノードをツリーの一番下に移動できるため、リーフノードを削除する方法を理解するだけで十分です。

要素8を削除する方法を見てみましょう。 左側のサブツリーの最大値は4（a）です。 そこで、ノード8と4を交換して削除します。 8 には赤いリンクがあったため、要素 4 （b）を削除した場合と同じ簡単なケースになります。

この場合も、最終的なツリーは有効な赤黒木です（c）。

24を削除

赤いリンクの右または左のノードではないリーフノードを削除する場合は、状況が少し複雑になります。

例として、 24 （a）の削除を見てみましょう。 まず、 24と18を反転します（ 18 は左側のサブツリーの最大要素です）。

次に、赤いリンクがないツリー（b）の24を削除する必要があります。

24 が削除されたツリー（c）は、 18 に子が1つしかないため、有効な赤黒木ではなく、ツリーのバランスが取れていません。

回転（d）でツリーのバランスをとることができます。

5. 複雑

赤黒木は、挿入、検索、および削除の対数平均および最悪の場合の時間計算量を提供します。

リバランスの平均時間計算量はO（1）であり、最悪の場合の複雑さは O（log n）です。

さらに、赤黒木は、バルクおよび並列操作に関して興味深い特性を持っています。 たとえば、時間計算量 O（log（log n））および（ n / log（log n））を使用して、ソートされたリストから赤黒木を構築することができます。プロセッサ。

6. 赤黒木の応用

赤黒木の実際の使用法には、Javaコレクションライブラリの TreeSet 、 TreeMap 、およびHashmapがあります。 また、LinuxカーネルのCompletelyFairSchedulerはこのデータ構造を使用します。 Linuxは、ファイル/メモリマッピングのmmapおよびmunmap操作でも赤黒木を使用します。

さらに、赤黒木は、幾何学的範囲の検索、k-meansクラスタリング、およびテキストマイニングに使用されます。

上記の例から、赤黒木は主に内部で使用されており、開発者として日常的に使用しているにもかかわらず、あまり接触しないことがわかります。

7. 結論

この記事では、赤黒木とは何か、そしてそれらが基本的に2〜3の木の異なる表現である方法を学びました。

また、ツリーでの操作の複雑さを要約した表を確認し、最終的に、赤黒木の実際のアプリケーションを簡単に要約しました。

ただし、特定のユースケースのデータ構造の選択に関しては、考慮すべき多くの要因があります。 赤黒木は、挿入と検索に適切な平均コストが必要な場合、およびこれら2つの操作の対数最悪の場合のコストが保証されている場合に特に役立ちます。

さらに、たとえばAVLやBツリーなどの他のバランスの取れたツリーよりもリバランスのコストが低いため、ツリーを頻繁に更新する場合は、赤黒木が適しています。