トライで特定のプレフィックスを検索することは O(M) で行われることを知っています。ここで、M はトライに挿入される任意の単語の最大長です。
しかし、特定のプレフィックスで始まるすべての要素を取得する時間の複雑さはどのくらいでしょうか?
私は可能な答えについて考えました：
O(M+n) ここで、n はプレフィックスで始まる単語の数です。アイデア: プレフィックスの検索は O(M) にあります。次に、指定されたプレフィックスで始まるすべての単語を含むサブトリーがあり、それをトラバースするだけです。問題 (おそらく): プレフィックス ツリーに単語より多くのノードがあります。しかし、私がそれらを見る必要がないように、何らかの形の効率的な保存があるのではないでしょうか?
すべての単語が長さ L の同じプレフィックスで始まるトライがあるとします。ここで、そのプレフィックスで始まるすべての単語を報告するには、トライを完全に検索する必要があり、O(n) の時間がかかります。ここで、n はトライ内のノードの総数。
ここでの課題は、いくつかのプレフィックスで始まるトライ内のすべての単語を検索すると、プレフィックスの長さとは関係のない多くのノードを検索する必要がある場合があることです。トライに含まれるノードによって異なります。
このような検索を頻繁に行うことがわかっている場合は、パトリシア トライ (基数トライとも呼ばれます) の使用を検討することをお勧めします。これは、各エッジに複数の文字でラベルを付けることができるトライであり、1 つの子と 1 つの親を持つノードは許可されていません。トライをこのように保存すると、特定のサブトライの単語に対応するすべてのノードにアクセスするのに必要な時間が O(z) であることを示すことができます。ここで、z は見つかった単語の数です。これが機能する理由は、パトリシア トライのすべての非リーフ ノードに少なくとも 2 つの子があるため、z 個のリーフ ノードを含むサブトライには z 個の内部ノードがあるためです (これを確認するのは良い演習です)。したがって、すべての葉を検出できます。 O（z）ノードをスキャンしただけです。彼ら自身。これで問題がなければ、大幅な時間の節約になる可能性があります。