'

Using c++

Prefix Data Structure To store the words in this assignment, you will be creating dictionary using a data structure called a prefix tree. This data structure allows for the quick lookup of whether or not a word is valid. It will also allow you to find all words with a specific prefix. Rather than store each word individually, we instead store the words using a tree: root Node Node Word flag false false false false Node Node Word flag true true false Node Node NULL false true false Word flag The example above shows two how the words "aa" (abbreviation for administrative assistant) and "axe" are represented using a tree. Each node holds 26 pointers to other nodes; each of these nodes corresponds to a specific letter. Each node also holds an array of 26 boolean flags. Essentially, each word is represented by a path down the tree. If the path ends with a "false", then the path does not represent a valid word. For example, the root node has a path from the first Node pointer (i e. the pointer representing 'a')to another Node. Notice that this second level node has a "true flag for the first index. This indicates that "aa" is a valid word. If we examine the pointer for the second level 'x' position, we find that a path exists fo "ax" to another node. When we examine this third level node, we find that the pointer for the 'a' position is NULL This indicates that "aaa" is not a valid word. If we examine the pointer for the 'e' position, we find that the flag for this position is true; this make sense since "axe" is a valid word. Prefixes A prefix is a valid path that may or may not be a valid word. For example, "a" and Max are valid prefixes since there are words starting with these letters. However, Naaa" s not a valid prefix. Prefix Data Structure To store the words in this assignment, you will be creating dictionary using a data structure called a prefix tree. This data structure allows for the quick lookup of whether or not a word is valid. It will also allow you to find all words with a specific prefix. Rather than store each word individually, we instead store the words using a tree: root Node Node Word flag false false false false Node Node Word flag true true false Node Node NULL false true false Word flag The example above shows two how the words "aa" (abbreviation for administrative assistant) and "axe" are represented using a tree. Each node holds 26 pointers to other nodes; each of these nodes corresponds to a specific letter. Each node also holds an array of 26 boolean flags. Essentially, each word is represented by a path down the tree. If the path ends with a "false", then the path does not represent a valid word. For example, the root node has a path from the first Node pointer (i e. the pointer representing 'a')to another Node. Notice that this second level node has a "true flag for the first index. This indicates that "aa" is a valid word. If we examine the pointer for the second level 'x' position, we find that a path exists fo "ax" to another node. When we examine this third level node, we find that the pointer for the 'a' position is NULL This indicates that "aaa" is not a valid word. If we examine the pointer for the 'e' position, we find that the flag for this position is true; this make sense since "axe" is a valid word. Prefixes A prefix is a valid path that may or may not be a valid word. For example, "a" and Max are valid prefixes since there are words starting with these letters. However, Naaa" s not a valid prefix