首页 文章

Trie实现 - 将元素插入到trie中

提问于
浏览 次
4

我正在开发一个 Trie 数据结构，其中每个节点代表一个单词 . 所以单词 st ， stack ， stackoverflow 和 overflow 将被安排为

root
--st
---stack
-----stackoverflow
--overflow

我的Trie在内部使用 HashTable ，因此所有节点查找都将花费恒定时间 . 以下是我将算法插入到trie中的算法 .

  • 检查trie中是否存在项目 . 如果存在，返回，否则转到步骤2 .

  • 迭代 key 中的每个字符并检查该单词是否存在 . 这样做直到我们得到一个节点，其中新值可以作为子节点添加 . 如果未找到任何节点，则将添加到根节点下 .

  • 插入后，重新排列插入新节点的节点的兄弟节点 . 这将遍历所有兄弟节点并与新插入的节点进行比较 . 如果任何节点以与新节点相同的字符开头，则将从那里移动并添加为新节点的子节点 .

我不确定这是实现trie的正确方法 . 欢迎任何建议或改进 .

使用的语言：C

algorithm data-structures trie

3 回答

  • 0

    这个特里应该是这样的

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

    通常，您不需要使用哈希表作为trie的一部分; trie本身已经是一种有效的索引数据结构 . 当然你可以做到这一点 .

    但无论如何，你的步骤（2）实际上应该在搜索期间下降trie，而不仅仅是查询哈希函数 . 通过这种方式，您可以轻松找到插入点，而不需要在以后单独搜索它 .

    我相信步骤（3）是错误的，你不能因为它只存储在trie中的 additional 字符串片段;见上图 .

    回复于
  • 1

    以下是插入算法的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 .

    回复于
  • 6

    你有没有机会看看这个...... http://linux.thai.net/~thep/datrie/datrie.html#Insert

    回复于

相关问题