您如何更改 Trie 以支持按受欢迎程度（某种权重）显示结果？
How can you change Trie to support showing results by popularity (certain kind of weights)?
我想知道如何更改 Trie 数据结构的行为以支持通过某些词的流行度自动完成？
我在想每个节点都有一个按流行度排序的链表，这是个好主意吗？但是你怎么知道自动完成将显示的单词顺序？
首先，你必须添加一个属性 popularity 到 trie 节点，并且总是选择一个节点，你将它的 popularity 增加 1.
那么，假设您想获得所有以 "abc" 开头的单词之间的建议。
首先，你在 trie 中正常行走，直到到达代表 "abc" 的节点，然后你可以调用一个 In-Order 树遍历从那个节点开始，并且总是访问一个节点，您将其添加到 priority_queue（或 heap）中，这将按照您定义的方式对节点进行排序。您可以定义它以对节点进行排序，因为最大的 popularity 将是优先级。
遍历完成后，你可以一个一个的从堆中移除元素（任意数量），你移除的每个元素将是所有剩余元素中最大的（第一个元素将是最大的）其中，第二个将是所有剩余元素中最大的，依此类推。）
如果您对时间和 space 复杂性感兴趣，可以阅读本文：
这种方法需要时间 O(size of word) 来找到根节点，然后 O(n lg n) 来排序你想要的节点，然后 O(k lg n) 来获得你需要的前 k 个元素以显示。简而言之，时间复杂度为 O(n lg n) 并且 space 复杂度为 O(n) 因为堆。
我想知道如何更改 Trie 数据结构的行为以支持通过某些词的流行度自动完成？
我在想每个节点都有一个按流行度排序的链表，这是个好主意吗？但是你怎么知道自动完成将显示的单词顺序？
首先，你必须添加一个属性 popularity 到 trie 节点，并且总是选择一个节点，你将它的 popularity 增加 1.
那么，假设您想获得所有以 "abc" 开头的单词之间的建议。
首先，你在 trie 中正常行走，直到到达代表 "abc" 的节点，然后你可以调用一个 In-Order 树遍历从那个节点开始，并且总是访问一个节点，您将其添加到 priority_queue（或 heap）中，这将按照您定义的方式对节点进行排序。您可以定义它以对节点进行排序，因为最大的 popularity 将是优先级。
遍历完成后，你可以一个一个的从堆中移除元素（任意数量），你移除的每个元素将是所有剩余元素中最大的（第一个元素将是最大的）其中，第二个将是所有剩余元素中最大的，依此类推。）
如果您对时间和 space 复杂性感兴趣，可以阅读本文：
这种方法需要时间 O(size of word) 来找到根节点，然后 O(n lg n) 来排序你想要的节点，然后 O(k lg n) 来获得你需要的前 k 个元素以显示。简而言之，时间复杂度为 O(n lg n) 并且 space 复杂度为 O(n) 因为堆。