Search code examples
ctreeletters

a letter tree in C

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?

Solution

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