イントロ
2番目の記事では、さまざまなバランスの取れたツリーの特性の概要を説明します。 特徴として、私は操作の基本原則（操作の実装の説明なし）、操作の速度、不均衡なツリーと比較した追加のメモリ消費、さまざまな興味深い事実、および追加資料へのリンクを意味します。
赤黒檀
他の名前：赤黒木、RB木。
この構造では、頂点の色を2色（名前が示すとおり、赤と黒:)に維持し、次の規則に従ってバランスをとっています。
- 赤いトップは赤いトップの息子になることはできません
- 葉の黒の深さは同じです（黒の深さは、ルートからの途中の黒の頂点の数を指します）
- ツリールートブラック
ここでは、葉の定義をわずかに変更し、欠席の息子を置き換える特別なヌル頂点と呼んでいます。 このようなピークは黒であると見なされます。
例：
n個の頂点を持つ正しい赤黒木の最大の深さを見てみましょう。
最も深い葉を取ります。 深さhにします。 ルール1により、ルートからのパス上の頂点の少なくとも半分は黒になります。つまり、木の黒の高さはh / 2以上になります。 このようなツリーでは、少なくとも2 ^（h / 2）-1の黒の頂点が存在することがわかります（葉ではない場合、黒の深さkの各黒の頂点は、黒の深さk + 1の子孫を少なくとも2つ持つ必要があるため） 次に、2 ^（h / 2）-1 <= nまたはh <= 2 * log2（n + 1）。
赤黒ツリーを使用したすべての基本操作は、O（h）、つまり上記で証明したO（log n）で実装できます。 従来の実装は、多数のケースの分析に基づいており、理解するのはかなり困難です。 たとえば、Chris Okasakiの記事には、よりシンプルで理解しやすいオプションがあります。 残念ながら、ツリー内の挿入操作のみを説明しています。 従来の実装と比較した単純さは、基本ツリーの変更（ローテーション）の数を最適化することではなく、わかりやすさに焦点を当てることによって得られます。
このタイプのバランスの取れたツリーを実装するには、各頂点に追加の1ビットの情報（色）を格納する必要があります。 これにより、アライメントが原因で多くのオーバーヘッドが発生する場合があります。 このような場合、追加のメモリ要件なしで構造を使用することをお勧めします。
赤と黒の木が広く使用されています-標準ライブラリでのset / mapの実装、Linuxカーネルでのさまざまなアプリケーション（クエリのキューイング、ext3などで）、おそらく他の多くの同様のニーズのシステム
赤黒の木はB木と密接に関連しています。 順序4のBツリー（または2-3-4ツリー ）と同一であると言えます。 詳細については、ウィキペディアの記事、または前の記事で言及した「アルゴリズム：構築と分析」を参照してください。
ウィキペディアの記事
英語版ウィキペディアの記事（操作の説明）
赤と黒の木のビジュアライザー
AAツリー
追加の制限が課される赤と黒の木材の修正：赤のトップは右の息子にしかなれません。 赤黒のDerovoが2-3-4ツリーと同型である場合、AAツリーは2-3ツリーと同型です。
追加の制限により、操作は赤黒木よりも実装が簡単です（分析するケースの数を減らすことにより）。 木の高さの推定値は同じまま、2 * log2（n）です。 時間効率はほぼ同じですが、実装では色ではなく、通常は異なる特性（頂点の「レベル」）を保存するため、オーバーヘッドはメモリからバイトに達します。
英語版ウィキペディアの記事
AVLツリー
それは、それを発明したソビエトの数学者の名前にちなんで名付けられました：G.M. Adelson-Welsky and E.M. ランディサ。
ツリーに次の制限を課します：任意の頂点で、左と右のサブツリーの高さは1以下でなければなりません。高さhを持つツリーは少なくともF_h頂点を含む必要があることを証明することは簡単です。F_iはi番目のフィボナッチ数です。 F_i〜phi ^ n（phi =（sqrt（5）+1）/ 2は黄金比）であるため、n個の頂点を持つツリーの高さはlog2（n）/ log2（phi）〜1.44 * log2（n）を超えることはできません
赤黒ツリーの実装と同様に、実装はケースの分析に基づいており、理解するのは非常に難しく（赤黒よりも単純ですが）、すべての基本操作に対してO（log（n））の複雑さがあります。 動作させるには、左右のサブツリーの高さの差を各頂点に保存する必要があります。 1を超えないため、先頭に2ビットを使用すれば十分です。
詳細な説明は、N。Wirthの本「Algorithms + Data Structures = Programs」またはA. Shen の本「Programming：Theorems and Problems」にあります。
ウィキペディアの記事
デカルトの木
他の名前：デカルトツリー、トレープ（ツリー+ヒープ）、デュチャ（ツリー+ヒープ）。
平面上に木を描くと、キーは頂点のx座標に対応します（順序付けのため）。 次に、y座標（高さと呼びます）を入力できます。これは、頂点の高さが子の高さよりも大きい（同じプロパティがバイナリツリーに基づく別のデータ構造の値を持っている-ヒープ。したがって、その構造の名前の2番目のバリアント）
高さがランダムに選択された場合、ヒーププロパティを満たすツリーの高さはO（log（n））である可能性が最も高いことがわかります。 数値実験は、高さが約3 * log（n）であることを示しています。
操作の実装は単純で論理的であるため、この構造はスポーツプログラミングで非常に人気があります）。 テスト結果によると、時間内で最も効果的であると認識されました（赤黒、AAおよびAVLツリー、スキップリスト（バイナリツリーではなく、同様のスコープを持つ構造）および基数ツリー）。 残念ながら、メモリにかなり大きなオーバーヘッドがあり（高さを格納するために頂点あたり2〜4バイト）、保証されたパフォーマンスが必要な場合（OSカーネルなど）には適していません。
スプレイツリー
このデータ構造は、前述のすべてのデータ構造とは大きく異なります。 実際には、ツリーの構造に制限はありません。 さらに、その過程で、ツリーは完全に不均衡になる可能性があります！
スプレイツリーの基本はスプレイ操作です。 目的の頂点（または不在の場合はそれに最も近い頂点）を見つけ、基本回転の特別なシーケンス（順序のプロパティは保持するが構造を変更するツリー上のローカル操作）でルートに「引き出し」ます。 これにより、すべての基本操作をツリーで簡単に表現できます。 スプレーの操作シーケンスは、ツリーが「魔法のように」素早く動作するように選択されています。
スプレイ操作の魔法を知っているこれらのツリーは実装が容易ではありませんが、非常に簡単であるため、ACM ICPC、Topcoderなどでも非常に人気があります。
そのようなツリーでは、O（log（n））操作の複雑さを保証することは不可能であることは明らかです（現在アンバランスなツリーで深い頂点を見つけるように求められたらどうなりますか？）。 代わりに、O（log（n））操作の償却された複雑さが保証されます。つまり、サイズnのツリーを持つm操作のシーケンスはO（（n + m）* log（n））で機能します。 さらに、スプレイツリーにはいくつかの魔法の特性があり、実際には他のオプションよりもはるかに効果的です。 たとえば、最近アクセスされたピークはルートに近く、それらへのアクセスは加速されます。 さらに、要素にアクセスする確率が固定されている場合、スプレーツリーは、バイナリツリーの他の実装よりも遅くなく漸近的に動作することが証明されています。 もう1つの利点は、追加情報を保存する必要がないため、メモリのオーバーヘッドがないことです。
他のオプションとは異なり、ツリー内の検索操作はツリー自体を変更するため、要素に均等にアクセスすると、スプレーツリーの動作が遅くなります。 ただし、実際には、実際のパフォーマンスが向上することがよくあります。 テストではこれを確認しています。Firefox、VMWare、Squidに基づいて取得したテストでは、スプレイツリーは赤黒ツリーやAVLツリーと比較して1.5〜2倍のパフォーマンスの向上を示しています。 同時に、合成テストでは、スプレーツリーの動作が1.5倍遅くなります。 残念ながら、個々の操作のパフォーマンスが保証されていないため、スプレイツリーはリアルタイムシステム（OSのカーネル、ガベージコレクターなど）および汎用ライブラリーでは受け入れられません。
英語版ウィキペディアの記事
R. TarjanおよびD. Slatorによるオリジナル記事
ケープゴートツリー
このツリーは、メモリからのオーバーヘッドがないという点で、前のツリーと似ています。 ただし、このツリーは完全にバランスが取れています。 さらに、ツリーの「剛性」の係数0 <アルファ<0.5は任意に設定でき、ツリーの高さは値k * log（n）+1（k = log2（1 /アルファ））によって上から制限されます。 残念ながら、変更操作は過去のツリーのように償却されます。
剛性係数は、パフォーマンスのバランスに大きく影響します。ツリーが「硬い」ほど、高さが低くなり、検索が速くなりますが、修正操作の順序を維持するのが難しくなります。 たとえば、AVLツリーは赤黒で「タフ」であるため、その検索はより速く機能し、修正はより遅くなります。 スケープゴートツリーを使用する場合、これらの操作のバランスは、ツリーの特定のアプリケーションに応じて選択できます。
英語版ウィキペディアの記事
もう少し言葉
最後の2つのツリーは、競合他社とは大きく異なります。 たとえば、リンク/カットツリーデータ構造の効果的な実装で使用できるのは、グラフ内で最も高速な既知のフロー検索アルゴリズムの基礎として使用されるものだけです。 一方、減価償却の本質により、多くのアルゴリズム、特にロープの構築には使用できません。 これらのツリー、特にスプレーツリーの特性は、現在、理論家によって活発に研究されています。
バランスの取れたツリーに加えて、次のトリックを使用できます。通常のバイナリツリーを実装し、プロセスで定期的にバランスを取り直します。 これにはいくつかのアルゴリズムがあります。たとえば、O（n）で機能するDSWアルゴリズム
次のシリーズで
デカルトツリーとその実装について詳しく説明します
一般的なリンク
ツリービジュアライザー （概要からすべてのツリーを視覚化できます）