Num #8 In class, we saw Tries and how to insert and look up words in them. Here,

Question

Num #8

In class, we saw Tries and how to insert and look up words in them. Here, you will implement deletion from a trie. We will assume that our strings only consist of lower-case letters A friend has already written the following piece of code. She is only sharing the header file with you, but since she's a Trojan, you're sure that it's all correctly implemented struct TrieNode 1 // true if there is a word ending at this node bool isInSet; TrieNode *parent; 1/ the parent in the trie, NULL if the node is the root. TrieNode *child [26]; // the (up to) 26 children for the letters. NULL if there is no such child int convert (char letter) // turns a letter into its index in the child array 1 return (int) (letter - 'a'); bool isLeaf ) t// returns whether the node is a leaf for (int i =0; ?

Explanation / Answer

// C++ implementation of search and insert

// operations on Trie

#include <bits/stdc++.h>

using namespace std;

const int ALPHABET_SIZE = 26;

// trie node

struct TrieNode

{

struct TrieNode *children[ALPHABET_SIZE];

// isEndOfWord is true if the node represents

// end of a word

bool isEndOfWord;

};

// Returns new trie node (initialized to NULLs)

struct TrieNode *getNode(void)

{

struct TrieNode *pNode = new TrieNode;

pNode->isEndOfWord = false;

for (int i = 0; i < ALPHABET_SIZE; i++)

pNode->children[i] = NULL;

return pNode;

}

// If not present, inserts key into trie

// If the key is prefix of trie node, just

// marks leaf node

void insert(struct TrieNode *root, string key)

{

struct TrieNode *pCrawl = root;

for (int i = 0; i < key.length(); i++)

{

int index = key[i] - 'a';

if (!pCrawl->children[index])

pCrawl->children[index] = getNode();

pCrawl = pCrawl->children[index];

}

// mark last node as leaf

pCrawl->isEndOfWord = true;

}

// Returns true if key presents in trie, else

// false

bool search(struct TrieNode *root, string key)

{

struct TrieNode *pCrawl = root;

for (int i = 0; i < key.length(); i++)

{

int index = key[i] - 'a';

if (!pCrawl->children[index])

return false;

pCrawl = pCrawl->children[index];

}

return (pCrawl != NULL && pCrawl->isEndOfWord);

}

// Driver

int main()

{

// Input keys (use only 'a' through 'z'

// and lower case)

string keys[] = {"the", "a", "there",

"answer", "any", "by",

"bye", "their" };

int n = sizeof(keys)/sizeof(keys[0]);

struct TrieNode *root = getNode();

// Construct trie

for (int i = 0; i < n; i++)

insert(root, keys[i]);

// Search for different keys

search(root, "the")? cout << "Yes " :

cout << "No ";

search(root, "these")? cout << "Yes " :

cout << "No ";

return 0;

}

Output :

the --- Present in trie

these --- Not present in trie

their --- Present in trie

thaw --- Not present in trie

Related Questions

Navigate

• Browse (All)
• Browse N
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.