Trieを変更して、人気（特定の種類の重量）による結果の表示をサポートするにはどうすればよいですか？

Question

Trieデータ構造の振る舞いを、たとえばある単語の人気度によって自動補完をサポートするように変更するにはどうすればいいですか？

私は各ノードが人気順にソートされたリンクリストを保持していると考えていましたが、これはいい考えですか？オートコンプリートが表示される単語の順序を知る方法はありますか？

Answer 1

まず、あなたはトライノードに属性popularityを追加する必要があり、常にノードが選択されている、あなたはあなたがで始まるすべての単語間の提案を取得したいと仮定しましょう、それはpopularityその後、

1ずつだ増加します"abc"

最初に、あなたは "abc"を表すノードに到達するまでトライで歩きます。そして、In-Orderツリーを呼ぶことができます。そのノードはtraversal startで始まり、常にノードにアクセスします。 priority_queue（またはheap）を使用して、定義したとおりにノードをソートします。ノードをソートするように定義すると、最大のものがpopularityが優先されます。

トラバーサルを実行した後、ヒープから要素を1つずつ（必要な数だけ）削除することができます。削除する各要素は、すべての要素の間で最大になります（最初の要素はすべての第二は、すべての要素間の最大は、あなたが時間と空間の複雑さに興味がある場合は、これを読むことができます

---

）など、左のようになります。

このアプローチは、単語の時間O（サイズを取ります）を使ってルートノードを見つけたら、O（n lg n）を実行してノードをソートし、次にO（k lg n）を押して、表示する必要がある最初のk個の要素を取得します。簡単に言えば、時間の複雑さはO（n lg n）であり、空間の複雑さはヒープのためO（n）です。