トライと赤黒木は、文字列を格納するのに非常に効率的です。
時間の複雑さはどちらが優れていますか? 空間の複雑さはどうですか？
3483 次
1 に答える
14
これは、格納する文字列やトライの表現方法など、多くの要因によって異なります。
赤黒木では、各操作 (挿入、削除、検索など) で O(log n) 文字列比較を行う必要があります。共通のプレフィックスを持たない 2 つの文字列を比較する場合、または文字列が小さい 2 つの文字列を比較する場合、比較のコストは小さくなります。比較の最悪のケースは、ある文字列が別の文字列のプレフィックスである場合です。この場合、すべての文字を読み取る必要があります。したがって、文字列の赤黒木で長さ L の文字列を検索したい場合、最悪の場合、O(L log n) の比較を行うことで O(L log n) の作業を行うことになります。入力文字列のすべての文字。ただし、最良の場合、これには O(log n) 時間しか必要ありません。これは、比較が常にすぐに失敗する場合に発生します。
スペースの使用に関しては、赤/黒のツリーには、ノードごとに 2 つのポインターと、文字列ごとに 1 つのノードが必要です。(通常、赤/黒のビットはポインターの下位ビットにパックできます)。したがって、合計スペースは 2n + (すべての文字列の合計の長さ) です。
トライでは、挿入、削除、およびルックアップは、最悪の場合 (入力のすべての文字を考慮する必要がある場合) で O(L) になり、最良の場合 (早期にトライから外れる場合) で O(1) になります。これは赤黒ツリーよりも O(log n) 倍高速であり、大規模なコレクションでは重要になる可能性があります。ただし、より多くのポインター追跡が関係し、スキャンする文字の連続した配列がないため、トライは局所性が低くなります。
メモリ使用量に関しては、サイズ k のアルファベットのトライは通常、合計 kn 個のポインターを必要とします。ここで、n はノードの数です。アルファベットのサイズが大きい場合、これは赤/黒ツリーよりも大幅に悪化する可能性があります。ただし、パトリシア ツリー表現を使用してトライを圧縮するか、より効率的なデータ構造を使用して子ポインターを格納するか、トライから DAWG を構築することにより、そのスペース オーバーヘッドを削減できます。
お役に立てれば！
于 2013-01-21T19:32:53.020 に答える