Space efficient trie

Question

I'm trying to implement a space efficient trie in C. This is my struct:

struct node {
char val; //character stored in node
int key; //key value if this character is an end of word
struct node* children[256];
};

When I add a node, it's index is the unsigned char cast of the character. For example, if I want to add "c", then

children[(unsigned char)'c']

is the pointer to the newly added node. However, this implementation requires me to declare a node* array of 256 elements. What I want to do is:

struct node** children;

and then when adding a node, just malloc space for the node and have

children[(unsigned char)'c']

point to the new node. The issue is that if I don't malloc space for children first, then I obviously can't reference any index or else that's a big error.

So my question is: how do I implement a trie such that it only stores the non-null pointers to its children?

Answer 1

You could try using a de la Briandais trie, where you only have one child pointer for each node, and every node also has a pointer to a "sibling", so that all siblings are effectively stored as a linked list rather than directly pointed to by the parent.