Design Document

typedef struct trie_t trie_t;

trie_t {

char current; // The first node_t will be ‘/0.’

trie_t *children[ALPHABET_SIZE];

int EOW; // if EOW is 1, reached end of a word

}

ALPHABET_SIZE = 256;

“We should be able to take in any string” -Mark

Worry about optimizing later

new_trie_t();

Creates new trie_t

Sets current to be ‘/0’

All children are initialized to NULL

EOW set to 0

add_node(char current, trie_t *t);

Creates new node in t

Set t->children[current] to be current

All other children are set to NULL

EOW set to 0?

int insert_string(char *word, trie_t *t);

Inserts word into trie

For each trie

Check if entry of the next character exists in the children array

If so, move into that node in the array

If not, add a new node

Then move on to the next character in string

Set the EOW of the last node to 1

int delete_string(char *word, trie_t *t );

Delete word in trie

This one is more complicated