我正在开发一个Trie
数据结构,其中每个节点代表一个词。所以的话st
,stack
,stackoverflow
和overflow
将被实施 - 将元素插入特里
root
--st
---stack
-----stackoverflow
--overflow
我的特里使用HashTable
内部,因此所有节点查找需要一定的时间安排。以下是我提出的将项目插入到trie中的算法。
- 检查项中是否存在项目。如果存在,则返回,否则转到步骤2。
- 迭代
key
中的每个字符并检查单词的存在。这样做直到我们得到一个可以将新值添加为小孩的节点。如果没有找到节点,它将被添加到根节点下。 - 插入后,重新排列新节点插入的节点的兄弟节点。这将遍历所有的兄弟姐妹,并与新插入的节点进行比较。如果任何节点以新节点具有的相同字符开始,则将从那里移动并添加为新节点的子节点。
我不确定这是否是实现trie的正确方法。欢迎任何建议或改进。使用
语言:C++
@Vladimir:我的意思是'Trie'不是'树'。我回滚了你的改变。 – 2010-02-11 15:08:07
我在这个答案中有一个Python特里执行:http://stackoverflow.com/questions/55210/algorithm-to-generate-anagrams/1924561#1924561 – FogleBird 2010-02-12 03:30:19
我有疑问,现在如果我突然想要检索或显示的话在建议框中堆叠,如何区分堆栈和stackoverflow?请帮忙。 – vaishali33 2015-01-08 17:32:25