Converting a trie into a reverse trie?

Suppose that I have a trie data structure holding a number of strings. To look up a string in the trie, I would start at the root and follow the pointer labeled with the appropriate characters of the string, in order, until I arrived at a given node.

Now suppose that I want to build a "reverse trie" for the same set of strings, where instead of looking up strings by starting with the first character, I would look up strings by starting with the last character.

Is there an efficient algorithm for turning tries into reverse tries? In the worst case I could always list off all the strings in the trie and then insert them one-at-a-time into a reverse trie, but it seems like there might be a better, more clever solution.

---

But the nodes in your trie are in essentially random order, if your ordering criteria is based on the strings' reverse. That is, given the sequence [aardvark, bat, cat, dog, elephant, fox] , which are in alphabetical order, reversing the words would not give you the sequence [xof, tnahpele, god, tac, tab, kravdraa] .

In other words, there's no "more clever solution" than to build your reverse trie.

链接地址: http://www.djcxy.com/p/61504.html

上一篇: 子序列查询的数据结构

下一篇: 将树转换为反转树？