0

In the week 6, Tries data structure is explained. The concept is clear but it is not clear and infact not explained in the lecture as well that how a string can be searched?

Suppose "Dave" is stored. Now to search it back, only mechanism I can think of is assuming D will be at 3rd index in node1, A will be at 0th index in node2 and so on... But what sense does it make? Suppose I am using Tries for storing names, then how would I loop?

Also, it was said that end the end mark 'e' in "Dave" as checked to indicate end of string, but since same Tries instance of data structure will be used for storing many data, and I want to store "Daves" then how it would happen, because I have already checked 'e' as end of string. Could somebody please explain?

1

In a Trie every letter and the occasional apostrophe has a unique index to the Trie. As a result every word starting with " a " starts in the same place. For the word "about" we use the length of the word to know it's end and check that "word" is true when using the structure below.

typedef struct node
{
    bool word;
    struct node* children[27];
}
node;

node->children[a] = node->children[b] = node->children[o] = node->children[u] = node->children[t] & node->word = true;

4
  • How length of the word can be used to know its end, how about a word starting with 'a' and length as 5, like "asides"?
    – hagrawal
    Aug 1 '15 at 19:37
  • see the additional
    – ebobtron
    Aug 1 '15 at 19:40
  • the last node in the chain is lastnode->children[s] lastnode-> word = true; we test for the word when we reach the end of the word. It become a continuous test for is this element NULL or not. if ever null the word is not in the dictionary. if we put in "about" and test for "abo" when we reach " o " the word will be false.
    – ebobtron
    Aug 1 '15 at 19:41
  • Ok, thanks, let me check ..
    – hagrawal
    Aug 2 '15 at 18:38

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .