ツリーは、再帰ノードの一般的な構造です。木の種類はたくさんあります。人気のあるものは二分木と平衡木です。トライはツリーの一種で、プレフィックス ツリー、デジタル検索ツリー、検索ツリーなど、多くの名前で知られています (したがって、「トライ」という名前が付けられています)。
木の種類ごとに、目的、構造、および動作が異なります。たとえば、バイナリ ツリーには、比較可能な項目 (数値など) のコレクションが格納されます。したがって、数値のセットを格納したり、数値で表すことができる他のデータ (ハッシュ可能なオブジェクトなど) のインデックスを作成したりするために使用できます。その構造はソートされているため、単一のアイテムをすばやく検索できます。バランス ツリーなどの他のツリー構造も、原理的には同様です。
トライは、その構造でシーケンスを表します。個々の単一の値ではなく、一連の値を格納するという点で大きく異なります。再帰の各レベルは、「入力リストの項目 I の値は何か」を示します。これは、単一の検索値を各ノードと比較する二分木とは異なります。
試行の長所:
検索時間は、検索文字列の長さにのみ依存します。
検索ミスには、いくつかの文字 (特に、検索文字列とツリーに格納されたコーパスの間の最も長い共通プレフィックス) の調査のみが含まれます。
トライでは一意のキーの衝突はありません。
ハッシュ関数を提供したり、より多くのキーがトライに追加されたときにハッシュ関数を変更したりする必要はありません。
トライでは、エントリをキーでアルファベット順に並べることができます。
残念ながら、完璧なデータ構造はありません。したがって、試行にもいくつかの欠点があります。
コンテナーが大きすぎてメモリに収まらない場合は常に、トライはデータの検索時にハッシュ テーブルよりも遅くなる可能性があります。ハッシュ テーブルでは、1 回のアクセスにさえ、より少ないディスク アクセスが必要になりますが、トライでは、長さ m の文字列に対して O(m) 回のディスク読み取りが必要になります。
ハッシュ テーブルは通常、1 つの大きな連続したメモリ チャンクに割り当てられますが、トライ ノードはヒープ全体にまたがることができます。したがって、前者は局所性の原則をよりよく利用します。
トライの理想的な使用例は、テキスト文字列の保存です。理論的には、数値からオブジェクトまで、あらゆる値を文字列化して保存することができます。しかし、たとえば、浮動小数点数を格納する場合、周期的または超越的な数などの長い無意味なパス、または問題により 0.1+0.2 などの特定の浮動小数点演算の結果を生成するエッジ ケースがいくつかあります。倍精度表現で。
試行には、ノードと参照のメモリ オーバーヘッドがあります。
プレフィックス検索を頻繁に実行する必要がある場合は、試行を使用します (longestPrefix または keysWithPrefix )。データがディスクなどの低速サポートに格納されている場合、またはメモリの局所性が重要な場合は常にハッシュ テーブルを使用します。
