1. ## trie algorithm question..

Trie - Wikipedia, the free encyclopedia

i know that the use of trie takes less time then BST
i cant understand how the coding goes into a tree??
the example shows some letters with arrows
and i dont know what they are trying to encode
and how they retrieve the data
??

2. From the sounds of a quick read, though I could be wrong since I've never used this type of tree myself, sounds like items along the tree are being organized based on string characters starting from the beginning of the character array, and spread out based on the first few characters (thus if you look at the diagram it almost looks like they were trying to organize elements found commonly in a dictionary).

What they are trying to describe is that the tree itself does not store all of the strings, rather a "look-up" tree where I'm sure pointers reference to the actual elements for accessing them once you use the tree to locate what you need.

You would have to read the document in detail to I'm sure get the full scope of the algorithm. Hopefully this was of more help.

3. Obviously, what you use a trie for and what is stored in it are connected.

The principle of a trie is that you index with a character (or a character minus an offset, more commonly).

I didn't know what it was called, but I implemented something like this to decode variable length telephone numbers - based on the starting digits, at some point it will know the length of the number [although I think Germany has a different system - where a number can end with a 0 or a longer extension number with PBX solutions]. So my trie would store a pointer to the next elements until such a point that the number could be identified to number of digits - a flag in the structure told me whether it was "know" or "need to follow the tree".

When using T9 texting system on mobile phones, a trie is used to identify what letters are available to follow what has been typed so far. The index here is the digit on the keypad. I've not thought through the entire structure needed for this, but it's basically a trie that tells the SMS application which letters go together to form words - the words are sorted by frequency [in some large text], so the most commonly used word made up from the possible letters is presented as the first one if there are multiple words available.

--
Mats

4. i cant understand this line in the article
"Unlike a binary search tree, no node in the tree stores the key associated with that node; instead, its position in the tree shows what key it is associated with."

5. To find the "key" for each node, you start at the node and trace back to the root assembling each value along the way. The picture in the wiki page is misleading since each node shows the assembled key.

Here's an example trie for the words "cat", "car", and "chi". Notice how the "key" is constructed using the path from the root to the node.
Code:
```     c
/  \
a    h
/ \    \
t   r    i```
The BST version would look like this.
Code:
```   cat
/  \
car   chi```

6. i see the words in your trie tree
but how the number values are involved
for string aac i got 001
why
??

7. That sounds like something specific to the encoding in your implementation. The number could indicate which child to go to. So in my example, "car" would be 01, and "cat" would be 00. That's just a guess at your encoding though.

If you post some code we may be able to help more.

8. ahh thanks

9. this my the code
Code:
```#define N 3
typedef struct tree {
int value;
struct tree **sons;  // array of pointers
} tree;

tree * what1(){
int i;
tree *temp = (tree *)malloc(sizeof(tree));
if(!temp) exit(1);
temp->value=0;
temp->sons = (tree **)malloc(N * sizeof(tree *));
if(!temp->sons) exit(1);
for(i=0; i<N; i++)
temp->sons[i]=NULL;
return temp;
}

void what2(tree *root, char *text){
if(!(*text)){
root->value++;
return;
}
if(!root->sons[*text-'a'])
root->sons[*text-'a']= what1();
what2(root->sons[*text-'a'],text+1);
}

void what3(tree *root){
int i;
if(!root) return;
printf("%d ",root->value);
for(i=0; i<N; i++)
what3(root->sons[i]);
}

void main(){
tree *root= what1();
int i;
char *text[]={"aac","aa","bbb","aac","aa","aabc","a"},
stack[80]={0};
for(i=0; i<7; i++)
what2(root,text[i]);
what3(root);
putchar('\n');
}```

10. Why don't you just compile that and run it? Seeing as it is the fourth time you have posted this code, and it seems like you want US to figure out what it does...

Or is there a SPECIFIC question you have about the code and it's functionality?

--
Mats

11. Originally Posted by transgalactic2
this my the code
Code:
```#define N 3
typedef struct tree {
int value;
struct tree **sons;  // array of pointers
} tree;

tree * what1(){
int i;
tree *temp = (tree *)malloc(sizeof(tree));
if(!temp) exit(1);
temp->value=0;
temp->sons = (tree **)malloc(N * sizeof(tree *));
if(!temp->sons) exit(1);
for(i=0; i<N; i++)
temp->sons[i]=NULL;
return temp;
}

void what2(tree *root, char *text){
if(!(*text)){
root->value++;
return;
}
if(!root->sons[*text-'a'])
root->sons[*text-'a']= what1();
what2(root->sons[*text-'a'],text+1);
}

void what3(tree *root){
int i;
if(!root) return;
printf("%d ",root->value);
for(i=0; i<N; i++)
what3(root->sons[i]);
}

void main(){
tree *root= what1();
int i;
char *text[]={"aac","aa","bbb","aac","aa","aabc","a"},
stack[80]={0};
for(i=0; i<7; i++)
what2(root,text[i]);
what3(root);
putchar('\n');
}```
void main()??
After posting 1000+ posts on this forum, you should know better.