Tries (25 points) Consider a trie implemented using a dynamic-child-pointer-array structure: struct trie node struct { char letter; int is_word; Struct trie node struct *parent; struct trie node struct **children; unsigned int nchildren; }; typedef struct trie node struct trie node; Write a function to delete a word from this trie, using the following prototype: void delete _word(trie node *trie, char *word); Note the following: e Make sure you deal with the case when the word is a prefix

Tries (25 points)

Consider a trie implemented using a dynamic-child-pointer-array structure:

struct trie node struct {

char letter;

int is_word;

Struct trie node struct *parent;

struct trie node struct **children;

unsigned int nchildren;

};

typedef struct trie node struct trie node;

Write a function to delete a word from this trie, using the following prototype:

void delete _word(trie node *trie, char *word);

Note the following:

e Make sure you deal with the case when the word is a prefix.

e You must gracefully fail (i.e., do nothing and return) when the word is not in the trie.

Question 2

Hashes (25)

Considering the following actual monster structure, implicit linked list structure, and list functions pre-

defined for you:

struct monster_struct {

chase name[64];

cha type[64];

i eer eae ed (= 24 0)

Wg lpove short sot monsteriness;

iz

eee ee ee 1 1( 0) 0 =] a ok Oe] 0 1a

monster_linked_ list *mll_new();

voi mll_add(monster_linked list *1, monster *m);

voit mll_remove(monster_linked_list *1, monster *m);

monster *mll_find(monster_ linked list *1, .-. *name);

..implement an open-hashed hashtable by defining an mhash structure, and implementing the following

functions:

mhash *mhash_new();

UN SP ee 1a - 12 0 aT FJ 0 2-0 ea 1 =

‘cla mhash_add(mhash *h, monster *m);

voi mhash_remove(mhash *h, monster *m);

monster *mhash_find(mhash *h, -l1:; *name);

Notes:

e You may assume an unsigned short int is 16 bits.

e Your hashing function should return the product of the ASCII value of the first and last character

of the name.

e Your mhash table should be large enough to hold the entire range of the hashing function.

e For this question don’t worry about disposal.

Reflection (5)

What are the worst-case big-O times of your add, remove and find functions? When are those times reflective of real-world performance, and when is real-world performance better?

Question 3

Trees (25 points)

Coding (16 points)

Using the following leftmost-child-right-sibling tree structure:

struct tree_node_ struct {

int payload;

struct tree node struct *child;

struct tree node struct *sibling;

unsisned int nehildren;

iz

And with new nodes created by the following function:

tree_node *new_tree_node(irit p) {

tree_node *t = malloc(sic=:1(tree_node));

t->payload = p;

pepe sp ee me

t->sibling = NLL;

t->nchildren = Q;

return t;

Write a function to add a child to a parent, but maintain the property that the children of any given

parent are sorted by payload value in decreasing order (highest to lowest).

Analysis (9 points)

1. In big-O terms, how long will your function take to run?

2. How could result (1) be improved?

3. What change to the tree data structure would (2) require?