プログラミング
 Computer >> コンピューター >  >> プログラミング >> プログラミング

データ構造の辞書としての二分木

抽象データ型Dictionaryを実装しようとすると、ノードは値に関連付けられます。辞書は基本的にキーのセットであり、全順序から抽出された要素である必要があります。各キーに関連付けられている追加情報がある場合がありますが、概念的な理解にはつながりません。

辞書がツリーを使用して実装されている場合、各ノードは一意のキーを保持します。ここで、ツリー内の各ノードuについて、すべてのキーはu.lであり、厳密にu.kよりも小さくなっています。そして、u.rのすべてのキーは、厳密にu.kよりも大きくなっています。ツリーは、バイナリ検索ツリーと呼ばれるこの不変条件に従って編成されます。

この不変条件の主な利点の1つは、順序付けられたトラバーサルを使用して、ソートされたキーのリストを線形時間で見つけることができることです。これは、次のように再帰的に定義できます。1つの空のツリー、何もしない、そうでない場合は、最初に左側のサブツリーで再帰し、ルートを取得して報告します。次に、右側のサブツリーに戻ります。

二分探索木に対して複数の操作を行うことができます。杖の検索は、木の高さに基づいて行われます。検索は、他のすべての操作よりも重要な操作です。


  1. データ構造の範囲ツリー

    範囲ツリーは、ポイントのリストを保持するための順序付けられたツリーデータ構造として定義されます。これにより、特定の範囲内のすべてのポイントを効率的に取得でき、通常は2次元以上で実装されます。 O（log d のクエリ時間が速いことを除いて、kdツリーと同じです。 n + k）が、O（n log d-1 のストレージが悪い n）、dはスペースの次元を示し、nはツリー内のポイントの数を示し、kは特定のクエリで取得されたポイントの数を示します。範囲ツリーは、間隔ツリーで区別できます。ポイントを格納して特定の範囲内のポイントを効率的に取得できるようにする代わりに、間隔ツリーは間隔を保存し、特定のポ

  2. データ構造の二分木とプロパティ

    このセクションでは、1つの二分木データ構造のいくつかの重要なプロパティを確認します。このような二分木があるとします。 一部のプロパティは-です レベル「l」のノードの最大数は$2^{l-1}$になります。ここで、レベルは、ルート自体を含む、ルートからノードへのパス上のノードの数です。ルートのレベルは1であると考えています。 高さhの二分木に存在するノードの最大数は$2^ {h}-1$です。ここで、heightは、ルートからリーフへのパス上のノードの最大数です。ここでは、1つのノードを持つ木の高さが1であると考えています。 n個のノードを持つ二分木では、可能な最小の高さまたは最小のレ