Trie实现-在trie中插入元素

Question

我正在开发一个Trie数据结构，其中每个节点代表一个单词。因此，单词st、stack、stackoverflow和overflow将排列为

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

我的Trie内部使用HashTable，所以所有节点查找都需要固定的时间。下面是我提出的将一个项插入trie的算法。

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

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

使用的语言: C++

Answer 1

trie应该是这样的

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

通常，您不需要使用哈希表作为trie的一部分；trie本身已经是一个有效的索引数据结构。你当然能做到。

但是无论如何，步骤(2)实际上应该在搜索过程中降低trie，而不仅仅是查询散列函数。通过这种方式，您可以很容易地找到插入点，并且不需要稍后作为单独的步骤搜索它。

我认为步骤(3)是错误的，您不需要重新排列trie，事实上您不应该能够重新排列，因为存储在trie中的只是附加的字符串片段；请参见上面的图片。

Answer 2

下面是插入算法的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;
  } 
 } 

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