Trie Insertion

Inserting a new word into a trie is similar to searching for an existing word. We first search to see if the word already exists in the trie. If it doesn’t, we insert the new word.

Here’s how the algorithm goes:

We establish a variable called current_node. At the beginning of our algorithm, this points to the root node.
We iterate over each character of our search string. Here, our search string represents the new word we’re inserting. We call it a search string since we’re also searching whether the string already exists in the trie.
As we point to each character of our search string, we look to see if the current_node has a child with that character as a key.
If it does, we update the current_node to become that child node, and we go back to Step 2, moving on to the next character of our search string.
If the current_node does not have a child node that matches the current character, we create such a child node and update the current_node to be this new node. We then go back to Step 2, moving on to the next character of our search string.
After we insert the final character of our new word, we add a "*" child to the last node to indicate the word is complete.

Let’s see this in action by inserting the word “can” into our earlier example trie.

Setup: We set the current_node to be the root node. We also point to the first character of our string, which is the "c", as shown in the top .

/books/45079/OEBPS/tries/insert_point_to_c.png

Step 1: The root node has a "c" child key, so we turn that key’s value into the current_node. We also point to the next character of our new word, the "a", as shown in the bottom .

Step 2: We inspect the current_node for a child with the key of "a". There is one, so we make that the current_node and point to the next character of our string, which is the "n", as shown in the top .

Step 3: The current_node does not have an "n", so we need to create that child, as shown in the bottom .

/books/45079/OEBPS/tries/insert_point_to_a.png

/books/45079/OEBPS/tries/insert_point_to_n.png

Step 4: We’re done inserting "can" into our trie, so we cap it off with a child of "*":

And we’re done!

Code Implementation: Trie Insertion

Here’s the insert method for our Trie class. You’ll note that most of it looks the same as the earlier search method:

	def insert(self, word):
	current_node = self.root

	for char in word:
	if current_node.children.get(char):
	current_node = current_node.children[char]
	else:
	new_node = trie_node.TrieNode()
	current_node.children[char] = new_node
	current_node = new_node

	current_node.children[""*] = None

The first part of this method is the same as search. It diverges when the currentNode doesn’t have the child that matches the current character. When this is the case, we add a new key-value pair to the current_node’s hash table, with the key being the current character and the value being a new TrieNode:

	new_node = trie_node.TrieNode()
	current_node.children[char] = new_node

We then update the current_node to be this new node:

current_node = new_node

We then repeat the loop until we’re done inserting our new word. Once we’re done, we add a "*" key to the final node’s hash table, with the value as None:

current_node.children["*"] = None

Like search, trie insertion takes about O(K) steps. If we count the adding of the "*" at the end, it’s technically K + 1 steps, but because we drop the constants, we express the speed as O(K).