私は試みと三分探索木を経験しましたが、それらについていくつか質問があります。答えをグーグルで検索しましたが、具体的な答えを得ることができません。それで、ここに私の質問があります。
試行がスペース効率が悪く、TST が BST と試行の最良の組み合わせである場合、実際には試行がまったく使用されないということですか?
TST がオートコンプリートに使用されていると仮定すると、..Google の場合はどのように機能しますか? つまり、実際には固定された単語のセットなどはありません..では、TSTのツリーはどのように構築されるのでしょうか?
試行と三分探索木は、時間と空間のトレードオフを表しています。アルファベットに k 個の記号が含まれている場合、トライの各ノードには、k 個のポインターと、ノードが単語をエンコードするかどうかを示す 1 つの余分なビットが保持されます。長さ L の単語を調べるには、常に O(L) の時間がかかります。三分探索木は、ノードごとに 3 つのポインターに加えて、ノードが単語をエンコードするかどうかを示す 1 つの文字と 1 つのビットを格納します。長さ L の単語を検索するには、O(L log k) の時間がかかります。(静的な三分探索木がある場合は、重みのバランスが取れた木を使用して TST を構築できます。これにより、ルックアップ時間が O(L + log k) に改善されますが、挿入のコストが非常に高くなります。)
トライの各ノードがその子のほとんどを使用している場合、トライは三分検索ツリーよりも実質的にスペース効率と時間効率が高くなります。各ノードに比較的少数の子ノードが格納されている場合、三分探索ツリーの方がスペース効率がはるかに高くなります。通常、試行は三分探索木よりもはるかに高速です。
したがって、どちらの構造も厳密に優れているわけではありません。格納されている単語によって異なります。
ややこしい話ですが、簡潔な試行は、上記の両方のアプローチの実行可能な代替手段になり始めています。ルックアップ時間ははるかに遅くなる傾向がありますが、スペースの使用率はトライよりも優れています。繰り返しますが、他の 2 つのオプションよりも良いか悪いかはアプリケーションによって異なります。
それらを構築する方法については、試行と三分探索ツリーの両方が、単一の単語の効率的な挿入をサポートしています。事前に固定された一連の単語から構築する必要はありません。
お役に立てれば！