我想知道如何更改 Trie 数据结构的行为以支持通过某些词的流行度自动完成？
我在想每个节点都有一个按流行度排序的链表，这是个好主意吗？但是你怎么知道自动完成将显示的单词顺序呢？
最佳答案
首先，您必须向 trie 节点添加一个属性 popularity，并且总是选择一个节点，您将它的 popularity 增加 1。
然后，假设您想获得所有以“abc”开头的单词之间的建议。
首先，您在 trie 中正常行走，直到到达表示“abc”的节点，然后您可以调用一个中序树遍历从该节点开始，并且始终访问一个节点，将其添加到 priority_queue(或 heap)，它将按照您定义的方式对节点进行排序。您可以定义它以对节点进行排序，因为最大的 popularity 将是优先级。
遍历完成后，你可以一个一个的从堆中移除元素(任意数量)并且你移除的每个元素将是所有剩余元素中最大的(第一个元素将是所有元素中最大的) ，第二个将是所有剩余元素中最大的，等等。)
如果你对时间和空间复杂度感兴趣，可以阅读这篇文章:
这种方法需要时间 O(size of word) 来找到根节点，然后 O(n lg n) 来排序你想要的节点，然后 O(k lg n) 来获得你需要显示的前 k 个元素.简而言之，时间复杂度为O(n lg n)，空间复杂度为O(n)，因为有堆。
关于algorithm - 您如何更改 Trie 以支持按受欢迎程度(某种权重)显示结果？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/41766728/