实施 - 将元素插入特里

问题描述：

我正在开发一个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

答

特里结构应该是这样的

     ROOT 
      overflow/ \st 
        O  O 
          \ack 
          O 
           \overflow 
           O

通常你不需要使用哈希表作为线索的一部分;特里本身已经是一个高效的索引数据结构。当然，你可以做到这一点。

但无论如何，你的步骤（2）应该在搜索过程中实际下降trie，而不仅仅是查询散列函数。通过这种方式，您可以轻松找到插入点，而不需要稍后作为单独的步骤进行搜索。我相信步骤（3）是错误的，你不需要重新排列一个trie，事实上你不应该能够，因为它只是你存储在trie中的额外的字符串片段。 ;看到上面的图片。

谢谢。我知道标准的'trie'看起来像你的解释。但是我需要每个节点代表整个单词而不仅仅是后缀。按降序查找要插入的位置似乎是一个体面的想法。再次感谢。 – 2010-02-11 15:06:38

这听起来像你想要的是一个HAT-trie。看看它。 – 2010-02-11 15:15:48

@Appu：如果您的节点有一个父链接，即使路径只包含“后缀”，您也可以始终获得完整的文字包， – 2010-02-11 18:56:42

答

做了你一个机会，看看这一个.. http://linux.thai.net/~thep/datrie/datrie.html#Insert

答

以下是插入算法的Java代码。

public void insert(String s){ 
    Node current = root; 
    if(s.length()==0) //For an empty character 
    current.marker=true; 
    for(int i=0;i<s.length();i++){ 
    Node child = current.subNode(s.charAt(i)); 
    if(child!=null){ 
    current = child; 
    } 
    else{ 
    current.child.add(new Node(s.charAt(i))); 
    current = current.subNode(s.charAt(i)); 
    } 
    // Set marker to indicate end of the word 
    if(i==s.length()-1) 
    current.marker = true; 
    } 
}

有关更详细的教程，请参阅here。

实施 - 将元素插入特里

相关推荐