データ構造の区間木
このセクションでは、区間木とは何かを確認します。名前が示すように、区間木は区間に関連付けられている木です。したがって、区間木について説明する前に、基本的な区間を見てみましょう。
間隔は基本的に範囲です。したがって、1つの間隔が[a、b]と記述されている場合、範囲がaから始まり、bで終わることを示します。
ここで、間隔[10、20]があるとします。したがって、3つの範囲値があります。最初は-∞から10、10から20、最後は20から∞
ここで、[15、25]から2番目の間隔を作成するとします。したがって、これは次のようになります-
[18、22]から別の間隔を作ると、次のようになります-
したがって、異なる間隔とサブ間隔があります。以下のようなものです
| 間隔名 | 間隔の範囲 | サブインターバル |
| 間隔1 | [10、20] | [10、15]、[15、18]、[18、20] |
| 間隔2 | [15、25] | [15、18]、[18、20]、[20、22]、[22、25] |
| 間隔3 | [18、22] | [18、20]、[20、22] |
この情報から区間木を作ることができます。サブインターバルはサブツリー内に配置されます。
区間木では、すべてのリーフノードがすべての基本区間を表しています。これらの葉の上に、完全な二分木を構築します。
-
データ構造の範囲ツリー
範囲ツリーは、ポイントのリストを保持するための順序付けられたツリーデータ構造として定義されます。これにより、特定の範囲内のすべてのポイントを効率的に取得でき、通常は2次元以上で実装されます。 O（log d のクエリ時間が速いことを除いて、kdツリーと同じです。 n + k）が、O（n log d-1 のストレージが悪い n）、dはスペースの次元を示し、nはツリー内のポイントの数を示し、kは特定のクエリで取得されたポイントの数を示します。範囲ツリーは、間隔ツリーで区別できます。ポイントを格納して特定の範囲内のポイントを効率的に取得できるようにする代わりに、間隔ツリーは間隔を保存し、特定のポ
-
データ構造内の高さが制限されたハフマンツリー
高さ制限または深さ制限のハフマンツリーの図を以下に示します ツリーの深さの制限は、ほとんどの実際のハフマンの実装が対処しなければならない重要な問題です。 ハフマン構造は高さや深さを制限しません。もしそうなら、それが「最適」である可能性はありません。確かに、ハフマンツリーの最大の深さはフィボナッチ数列によって制限されますが、それは必要以上の深さのための十分な余地を残します。 ハフマンツリーの深さを制限する理由は何ですか？高速ハフマンデコーダーはルックアップテーブルを実装します。メモリコストを軽減するために複数のテーブルレベルを実装することは可能ですが、Huff0などの非常に高速なデコ