1. 序章

赤-黒（RB）ツリーは、バランスの取れたタイプの二分探索木です。 このチュートリアルでは、その最も重要なアプリケーションのいくつかを学習します。

2. RBツリーを使用する動機

前のチュートリアルでは、時間の動的セットで二分探索木の基本操作を学習しました。

これらの操作は、ツリーの高さが小さい場合は高速ですが、ツリーの高さが大きい場合は、リンクリストで得られるパフォーマンスと同等になります。 RBツリーは、可能なバランスの取れたツリースキームの1つを表しており、最悪の場合、ツリーの要素数を使用して基本的な操作を時間内に実行できます。 。

3. RBツリーのプロパティ

RBツリーは、標準のバイナリツリーのキーとポインタに加えて、REDまたはBLACKの色と呼ばれるバイナリフィールドも含むバイナリ検索ツリーです。 任意のパス上のノードに色を付けるための正確なルールにより、RBツリー内のパスが他のパスの2倍を超えることはなく、ほぼバランスの取れたツリーが得られます。

3.1. 着色

存在しないノードの各子はNULLの価値があり、次のプロパティがあります。

  • 各ノードは赤または黒です
  • 各NULLノードは黒です
  • ノードが赤の場合、両方の子は黒です
  • あるノードから別のノードへの各単純なパスには、同じ数の黒いノードが含まれています

3.2. 身長

含まれていないノードから子孫までの黒いノードの数は、ノードのb-heightと呼ばれます。 RBツリーの-heightは、そのルートの-heightです。

RBツリーの関心は、ノードのツリーの場合、最大の高さが古典的な二分木の改善であるという事実にあります。

RBツリーではINSERTおよびDELETE操作に時間がかかります。 これらはツリーの構造を変更するため、結果のツリーが上記のプロパティに違反している可能性があります。 この場合、いくつかのノードの色を変更し、ポインタの構造を変更する必要があります。これは回転と呼ばれるメカニズムです。 。

4. アプリケーション

RBツリーは、他のアルゴリズムとの関連で、INSERT、DELETE、およびSEARCH操作の最適な計算時間を保証します。 この事実により、リアルタイムアプリケーションなど、計算時間の観点から機密性の高いアプリケーションでの使用が可能になります。

ただし、その特性により、RBツリーを多数のアプリケーションの基礎となるデータ構造の基本的な構成要素として使用することもできます。

4.1. AVL木

AVLツリー（Adelson-Velsky and Landisツリー）は、発明された最初の自己平衡二分探索木でした。 AVLツリーでは、2つの子サブツリーの高さの差は最大で1つです。 この条件が満たされない場合は、リバランスが必要です。

AVLツリーは、平均的な場合と最悪の場合の両方で、SEARCH、INSERT、およびDELETEの複雑な時間をサポートするもう1つの構造です。 AVL木は赤黒に着色することができます。 したがって、それらはRBツリーのサブセットです。 最悪の場合の高さはRBツリーの最悪の場合の高さの0.720倍であるため、AVLツリーはより厳密にバランスが取れています。

4.2. タンゴの木

高速検索用に最適化されたバイナリ検索ツリーの一種であるタンゴツリーの元の説明では、特にデータ構造の一部としてRBツリーを使用しています。

4.3. 関数型プログラミング

RBツリーは、連想配列を構築するための関数型プログラミングで使用されます。

このアプリケーションでは、RBツリーは 2-4ツリーと連携して機能します。これは、子を持つすべてのノードに2つ、3つ、または4つの子ノードがある自己バランス型データ構造です。

2〜4ツリーごとに、同じ順序のデータ要素を持つ対応するRBツリーがあります。 2〜4ツリーでのINSERTおよびDELETE操作は、RBツリーでのカラーフリッピングおよびローテーションと同等であることを示すことができます。

この結果は、RBツリーが2〜3ツリーまたは2〜4ツリーと等角になる可能性があることを示すために一般化されています。これは、Guibas and Sedgewick（1978）による結果です。

4.4. Java

前の段落に加えて、プログラミング言語C++およびJavaでのRBツリーの使用に関するいくつかの注意事項を報告します：

  • JavaのTreeSetおよびTreeMapは、順序付けと並べ替えにRBツリーを使用します
  • HashMap も、 LinkedList の代わりにRBツリーを使用して、衝突するハッシュコードを持つさまざまな要素を格納します。 これにより、そのような要素を検索する時間の複雑さが改善され、ハッシュコードが衝突する要素の数はどこになりますか。

4.5. 計算幾何学

計算幾何学におけるRBツリーのアプリケーションは数多くあります。 ここでは、2つの興味深い例を示します。

4.6. Linuxカーネル

Completely Fair Scheduler（CFS）は、Linuxカーネルの2.6.23リリースから利用可能なプロセススケジューラの名前です。 平均使用率を最大化することを目的としてCPUを管理します。 CFSはツリー内のタスクを表し、次に実行するタスクを見つけます。

CFSは、仮想ランタイム（vruntime）を使用して各タスクをRBツリーに格納します。 ツリーの左端のノードは、vruntimeが最小のノードになります。 CFSが実行する次のタスクを選択する必要がある場合、CFSは左端のノードを選択します 。

LinuxカーネルでのRBツリーのもう1つの使用法は、メモリ管理に関するものです。 RBツリーは、プロセスの仮想メモリセグメントを追跡します。ここで、範囲の開始アドレスがキーとして機能します。

4.7. 機械学習

潜在的に、RBツリーには、機械学習とデータマイニングに十分なアプリケーションスペースがあり、従来のアルゴリズムのパフォーマンスを向上させることができます。

たとえば、時間の複雑さを軽減するために、K-meanクラスタリングアルゴリズムで使用されます。

4.8. データベースエンジン

データベースエンジンのデータインデックスは、RBツリーを直接または間接的に使用します。

たとえば、MySQLは B +ツリーを使用します。これは、Bツリーの一種と見なすことができます。 RBツリーは、4次のBツリーと構造が似ています。

B+ツリーには次の特徴があります。

  • 非リーフノードはデータを保存しません。 インデックスのみを保存します（冗長性）–これにより複数のインデックスを保存できます
  • リーフノードには、すべてのインデックスフィールドが含まれます
  • リーフノードは、パフォーマンスを向上させるポインタに接続されています

5. 結論

このチュートリアルでは、RBツリーのいくつかの重要なアプリケーションについて簡単に説明しました。 他の手法との関係に注目する価値があります。これにより、多くの実装内で並べ替えおよび検索操作の効率を高めることができます。

私たちの意見では、Linuxカーネルでのそれらの使用は特に興味深いものです。 RBツリーに関連するコードの自由に利用できる部分は、複雑な実際の問題の中でアルゴリズムをどのように使用できるかを教えてくれます。