2. Trie basic API #

Created Saturday 07 March 2020

In the tree system, we have a start node(root) which stores the value of zero. Why is this required?

1. We need some starting point. From which everything emanates.

• As we are writing a tree, we will be using recursion. For this we will require a change in root. But user will give only the word.
• All functions check the children corresponding to word[0], this is because we have used a origin node, which does the same for the first letter. Checking the root for word[0], therefore, is wrong.
• We can also implement a trieSize() function which returns the number of nodes in the trie(except the root node).

1. insertWord()

pseudocode Traverse the trie for the word until possible. (This can be done in any part of the function) If the word is present(i.e word.size() becomes 0), make the last letter node as terminal. Else make newnodes with each of the remaining letters. Make the last letter as terminal.

Code void insertWord(TrieNode* root, string word) { if(word.size()==0) //got the last letter { root->isTerminal = true; return; } if(root->children.[word[0]-‘a’]==NULL) root->children.[word[0]-‘a’] = new TrieNode(word[0]); // if the word is absent // we have the word[0] in the system now // make the root->children as the next root and pass the remaining string. insert(root->children.[word[0]-‘a’], word.substr(1)); }

2. searchWord()

pseudocode Traverse the trie for the word until possible. (This can be done in any part of the function) If the last letter is reached, i.e word.size() becomes zero, return root->isTerminal.

If a letter is not found return false. Else return search for the remaining string.

Code void insertWord(TrieNode* root, string word) { if(word.size()==0) //got the last letter return root->isTerminal = true;

if(root->children.[word[0]-‘a’]==NULL) return false; // letter is absent // we have the word[0] in the system now // make the root->children as the next root and pass the remaining string. return search(root->children.[word[0]-‘a’], word.substr(1)); }

3. removeWord() - note that a node can only partially delete itself(i.e isTreminal = false), otherwise the parent has a dangling pointer.

pseudocode Traverse the trie for the word until you can. If we reach the last letter: root->isTerminal = false; // as we enter here only if the root->data was last letter

if(root->children[word[0]-‘a’]==NULL) abort; // letter is absent; // remove the remaining string removeWord(root->children[word[0]-‘a’], word.substr(1));

// Marked the next node as non // If the next node has no other children, We can delete it

1. If the next node has no other children, We can delete it. If we do so.
2. Else do nothing.

// This node can be deleted partially. root->isTerminal = false; // we do it in the base case too, because “”-‘a’ is not a valid integer.

Code If we reach word.size()==0 root->isTerminal = false; // this word is not “present” now

if(root->children[word[0]-‘a’]==NULL) return; // letter not present

// letter is present, remove the letter remaining part of the string first remove(root->children[0]-‘a’], word.substr(1));

// if any other node is present with the root int i = 0; while(root->children[word[0]-‘a’]->children[i]==NULL) i++; if(i==26) delete root; // delete itself root->children[word[0]-‘a’]=false;

// end of function