Question

. (4 points-Completeness) Implementing Multiway Trie Below is C++ node class defined as class MultiwayTrie f class Node public: public: bool word false; Node children [26]; Node ) Node* root new Node ) bool find(string word); void insert (string word); void remove (string word) Node: :Node (void) for (int i0 i 26: ++i) children [1] NULL; = (a)(e points-Completeness) Write the implementation of the insert of the MultiwayTrie class method below /Insert word into MultiwayTrie (return nothing) / void MultiwayTrie::insert (string word) t

Answer 1

(a)

void insert(string word)

{

    struct Node *crawl = root;

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

    {

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

        if (!Crawl->children[index]) { // If not present inserts word into trie

struct Node *t = new Node;   

crawl->children[index] = t;

}

        crawl = crawl->children[index];

    }

crawl->word = true;    //mark leaf node as end

}

(b)

bool find(string word)

{

    struct Node *crawl = root;   

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

    {

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

        if (!crawl->children[index])

            return false;

        crawl = crawl->children[index];

    }

  

    return (crawl != NULL && crawl->word);

}