Intruction Implement a Hash Table using a Tree. This data structure is similar to the linked list hash dictionary described in the book. However, instead of storing the values in each “bucket” as a...

Intruction Implement a Hash Table using a Tree. This data structure is similar to the linked list hash dictionary described in the book. However, instead of storing the values in each “bucket” as a linked list, you will store the values in a binary tree. Part 1: DictTree The dictionary tree class stores key/value pairs using a binary tree where the order is based on the value of the key. The implementation is essentially the same as a standard binary tree except the tree order is based on the key. The following is a representation of the data structure followed by the header file.

key item left right * *

key item left right * *

key item left right * *

key item left right * *

key item left right * *

template class DictTree { private: TreeNode* root; // any other functions you find useful

int numNodes; public: DictTree(); ~DictTree(); void add(KeyType newKey, ItemType newItem); bool remove(KeyType newKeys); bool contains(KeyType key); ItemType lookupItem(KeyType key); int size(); void traverse(void visit(ItemType&)) const; }; Your job is to implement each of the methods in the header class. You also need to define the Node as a class or struct. The implementation should be very similar to a standard binary tree. The following is the output if your dictionary tree is implemented correctly:

Part 2: HashTable Once the tree dictionary is implemented, completing the HashTable implementation requires little additional code. The HashTable is implemented using an array of buckets where each of these buckets is a DictTree pointer: buckets 0 * 1 * 2 * … * n *

When adding an item to the hash table using a key for the lookup, use of a hash function is required. This hash function takes the key value as input and returns the bucket the item should be associated with. The hash function is called as follows: int b = getHashIndex(key); b now stores the bucket index that the item associated with key is located. Refer to the notes given in the started code. The following is the output if the hash table is implemented correctly:

DictTree