Requirements:

In this sub-project, you will implement the Trie node class Trie_node.

A trie node is a node within trie. Please read up on the characteristics of a trie.

You will be using the class std::string and you may use other functionality in the string and cctype libraries.

Note: this is only a recommended implementation. You may change everything about the internal structure you want so long as the child member functions works as expected according to the implementation using this specification.

Runtime:

The run time of each member function is specified in parentheses at the end of the description where n refers to the number of letters in the word.

Class Specifications:

---

Trie_node

Description

A class which implements a trie node.

This class has a helper structure std::pair<Type, bool> which will be used to return two pieces of information: an object and a Boolean flag. If the Boolean flag is set to true, the object is considered to be a valid result; otherwise, the object is to be ignored. If return_value is an instance of such a returned pair, the two members may be accessed with return_value.first and return_value.second, respectively.

Member Variables

This class two member variables:

• A pointer to an array of pointers to Trie nodes,
• A Boolean flag indicating whether a node represents a terminal node for a word.

There is also a constant static member variable CHARACTERS that is assigned the value 26.

Member Functions

Constructor

The constructor sets the pointer to children to null and sets the Boolean flag to false.

Accessors

This class has two accessors which must be implemented:

Trie_node *child( int n ) const

Return a pointer to the nth child. If the children array is empty, return nullptr; otherwise, just return children[i]. This member function will never be called with a value outside 0 to 25. (O(1))

bool member( std::string const &str, int depth ) const

The string being searched for is being passed recursively; however, as we go deeper into the tree, we must have access to the character corresponding to the depth. You can assume that the characters are all alphabetical, as the Trie class should have checked for invalid characters. The trie is case insensitive, so you must map letters to the range 0 to 25. If we are at the end of the word, the is_terminal member variable will determine the appropriate return value; otherwise, we need to call member recursively or return false, as appropriate. You must return the appropriate values in all cases, including: when children is null, when the appropriate child pointer is assigned null, and otherwise. (O(n))

Mutators

This class has three mutators must be implemented:

bool insert( std::string const &str, int depth )

Like member, we need to recurse into the tree. If we reach a node and we are at the end of the word we are attempting to insert, we need only check and possibly modify the member variable is_terminal to determine the appropriate return value. If we are not yet at the end of the word, we must recurse through the appropriate sub-tree. This may require first assigning an array of 26 pointers to Trie nodes to children in some cases, and it may require assigning a new Trie node to the k^th sub-tree of this array. (O(n))

bool erase( std::string const &, int depth, B, Trie_node *&ptr_to_this )

Like member and insert, we need to recurse into the tree. If we reach the end of branch of the tree before we get to the end of the word, it is clear the word is not stored in this tree and thus cannot be erased. If we get to a node when we are the end of the word, we must choose the appropriate course of action and the appropriate return value based on the value of is_terminal. If this node is a leaf node (children is assigned null), we should delete this node. While we are recursing back, if the children array became entirely unassigned as a result of our erase, the current node must also be erased. For example, in the example given in Figure 1 of the description of a trie, if the word "thoughts" was erased, then the nodes containing "o", "u", "g", "h", "t", and "s" must be deleted and the appropriate sub-child of the node containing "h" must be set to null. (O(n))

void clear()

Calls clear on all sub-trees and deletes this node.