Data structure trie

spank · 05-20-2006, 10:51 AM

I have to implement a trie and I don't know how to search an element there. I have to reach to say the 4th character and I don't know how to do that. I've googled enugh but i don't seem to find anything relevant. Thank you!

exvor · 05-20-2006, 01:09 PM

Things to include in your post that would be helpfull.
1. programming language.
2. what is a trie ? you might mean tree
3. is this homework? if so looking in your text book might be of help.
4. is this a binary tree? if so searching though one is quite extensive.

spank · 05-20-2006, 01:20 PM

ok... sorry. A trie is a tree, but not binary

http://en.wikipedia.org/wiki/Trie

I want this in plain C, yes... this is a homework (i'm not asking for someone to solve it for me, just for help)

thank you!

exvor · 05-20-2006, 01:28 PM

AHH deep magic.

Sorry not famillar with this type of data structure. thats why I dident know what trie was. Sorry for the mix up thought you were doing a spelling foobar.

graemef · 05-20-2006, 01:51 PM

How much have you managed to implement?
What does your data structure currently look like?

BSchindler · 05-20-2006, 06:04 PM

The tree nodes and method to implement tries vary considerably. Have you been provided with a node structure or are you implementing this completely?

There is a lot of code already "out there" to help you, but you must be a bit more specific about the parameters.

spank · 05-21-2006, 02:57 AM

well i'm tring to do somthing like this:

search(a,k);
search the trie a for the element number k
and the trie contains only numbers and the order is considered the lexicografic order not the sort one.

spank · 05-21-2006, 07:21 AM

How i have to implement a scapegoat tree... this i really can't find any good information on the web. Any ideea ?