a letter tree in C

Question

I'd like to store some data associated to words composed of simple ascii letters (a-Z) The goal is to retrieve very quickly the data associated to a word in a future parsing.

I though about the following structure:

struct Foo {
  Foo *letter[26];
  void *data;
};

Thus, it is possible to go down through the "letter tree" while parsing a word in a string and get the associated data.

"foo" => ['f' node] -> ['o' node] -> ['o' node]

The problem is the size of the entire tree if I got many words.

Is there a way to reduce the size of the tree without losing performances?

Answer 1

What you're describeing is called trie. A compact radix tree is more compact.

Answer 2

Is there a reason you're using a tree instead of storing words in a hash table? These will tend to use a bit more memory, but will give you near constant time performance for table lookups.