AVLツリーとその適用範囲

私の意見では、最も有用なツリー構造について少し説明することにしました。 AVLツリーはバイナリツリー（各頂点には2つ以下の息子があります）で、識別子が各頂点に割り当てられ（ツリーに格納されます）、識別子は次のルールに従います：左息子ID <親ID <右息子ID。

つまり ツリーを左から右に再帰的に移動すると、IDが昇順で、右から左に-降順でソートされます。

さらに、ツリーは可能な限りバランスが取れています。左のサブツリーの高さは、右のサブツリーの高さと最大1異なります。



ここで興味深いのは、ログ（N）Nを使用してツリー内の要素（IDの数）の存在を確認することです。 結局、ルートから降りる必要があり、ツリーは可能な限り対称であるため、その高さはlog（N）+1です

幸いなことに、他の有用なデータを頂点に添付することを誰も禁止していないため、IDによる任意のデータの選択にはlog（N）時間かかります

悪いニュースは、定義から次のように同一のIDが存在できないことです。 各頂点の代わりに同じIDを持つ頂点のリストを作成する1つの方法と、バランスアルゴリズムを変更することです。



別のプロパティ-特定のタスクに最も近いが、それよりも小さい、またはそれ以上の配列の要素をすばやく見つけることができるため、一部のタスクでは非常に重要です。



これは興味深いです。明らかに、識別子のリストからこのようなツリーを構築できますが、非常に短い時間で要素をすばやく追加および削除できることがわかります<= log（N）（追加）



したがって、N個の要素の配列をソートするには、単純にツリーに追加します-N * log（N）そして、左から右に移動します-N i.e. 合計時間N * log（N）-別の非常に高速な配列ソート方法を作成しました



ちなみに、便利ないくつかの操作-目的のIDを持つ頂点をすばやく検索するため、SetおよびGet操作を実行して、頂点のDATAフィールドを変更します。 したがって、<= log（N）のメモリ内の特定のIDに対応するデータも更新します。



私はAVLツリーを非常に頻繁に使用します：標準のCRCハッシュでも、CRCグループをツリーに保存し、配列とリストをソートし、それを使用して配列内の要素の存在を確認し、データベースインデックスを保存し、検索結果をソートします（上記のように）、最後に、ファイルに直接書き込むこともでき、さらに高速に読み取ることもできます。

一般に、この構造はリストよりも大きくありませんが、数百倍の操作を実行できます。 1-2リンクリストの優れた代替手段。



ツリーへの追加方法について少し説明しますが、パブリックドメインには多くの完全な説明があります。

各頂点で番号のバランスを導入します。これは、上のサブツリーのどちらが左か右かを示します。

ツリーに頂点を追加すると、時々不均衡になります。 追加の手順は簡単です-ルールを使用してツリーの一番下まで行きます

左息子ID <親ID <右息子ID、つまり 新しいID <頂点IDの場合は左に、そうでない場合は右に移動します。 一番下のピークに息子を追加し、目的のパスに沿ってバランスインジケーターを更新する必要があります-降下に沿ってこれを行うことができ、上方向に戻ることができます-左のサブツリーから来た場合はバランス、そうでなければバランス++

あるレベルでbalance = 0になった場合、サブツリーのバランスが取れ、追加を終了できます（サブツリーの高さが変化しなかったため、最上部のツリー全体を再計算する必要はありません-バランス= -1が0になりました-左のサブツリーが右に追加されました）そして、整列、またはバランス= 1が0になりました-右のサブツリーが重くなり、左に追加されて整列されました）



さて、最も興味深いのは、途中のステップでbalance = -2または2になった場合、サブツリーのバランスをとることです。これは、ツリーの半分が強くオーバーウエイトしたことを意味します。左を長くします。 全体の状況は条件の確認とリンクの再配置になりますが、私は自分で紙の上でそれを理解しました-より良い認識のためにあなたに助言する3つのオプションしかありません-私はここで描くことができる言葉を特に書きませんインターネットで既製のソリューションを見つけます。



検索エンジンに関する私の記事の全内容とリストはここで更新されます： http : //habrahabr.ru/blogs/search_engines/123671/