4

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

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

我的 Trie 在HashTable内部使用，因此所有节点查找都需要固定时间。以下是我想出的将项目插入特里树的算法。

  1. 检查 trie 中是否存在项目。如果存在，则返回，否则转到步骤2。
  2. 迭代中的每个字符key并检查单词是否存在。这样做直到我们得到一个可以将新值添加为子节点的节点。如果没有找到节点，它将被添加到根节点下。
  3. 插入后，重新排列插入新节点的节点的兄弟姐妹。这将遍历所有兄弟节点并与新插入的节点进行比较。如果任何节点以与新节点相同的字符开头，它将从那里移动并添加为新节点的子节点。

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

使用语言：C++

4

2 回答 2

7

特里应该看起来像这样

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

通常你不需要使用哈希表作为 trie 的一部分。trie 本身已经是一种高效的索引数据结构。你当然可以这样做。

但无论如何，您的步骤 (2) 实际上应该在搜索期间下降 trie，而不仅仅是查询哈希函数。通过这种方式，您可以轻松找到插入点，而无需稍后作为单独的步骤进行搜索。

我认为步骤（3）是错误的，您不需要重新排列 trie，事实上您不应该这样做，因为它只是您存储在 trie 中的附加字符串片段；见上图。

于 2010-02-11T15:00:56.290 回答
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;
  } 
 }

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

于 2012-07-26T10:41:51.110 回答