Implementing Trie - Inserting Elements into a Trie

Question

I am developing a Trie data structure where each node represents a word. So the words st , stack , stackoverflow and overflow will be located as

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

My Trie uses a HashTable internally, so the node search will continue all the time. Below is the algorithm I came up with to insert an element into a trie.

• Check for an element in a trie. If exists, return, else goto step2.
• Iterate over each character in key and check for the presence of a word. Do this until we get a node where a new value can be added as a child. If node is not found, it will be added as root node.
• After the insertion, rearrange the brothers and sisters of the node into which the new node was inserted. This will go through all the siblings and compare with the newly inserted node. If any of the nodes starts with the same characters as the new node, it will be moved from there and added as a child of the new node.

I am not sure if this is the correct way to implement trie. Any suggestions or improvements are welcome.

Used language: C ++

Answer 1

Three should look like this:

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

Usually you do not need to use hash tables as part of the trie; trie itself is already an efficient index data structure. Of course you can do it.

But in any case, your step (2) should actually go down to trie during the search, and not just request a hash function. This way you can easily find the insertion point and should not look for it later as a separate step.

I believe that step (3) is incorrect, you do not need to rebuild the trie, and in fact you should not do this, because these are only additional fragments of the line that you store in the store; see image above.

Answer 2

Below is the java code for the insert algorithm.

 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; } } 

For a more detailed guide, see here .

Answer 3

You had a chance to look at it. http://linux.thai.net/~thep/datrie/datrie.html#Insert