c++ program

Implement the following data structure: The structure implements a combined BST and hash table. The data structure works as follows: 1. We will start as a Binary Search Tree (BST) that has 4 levels. 2. Level 0,1,2,3 consist of normal BST nodes. 3. At level 4, notice that we have 16 leaf nodes. Those nodes will be implemented as hash tables. So, there will be 16 hash tables. The methods that need to be supported are 1. initialize 2. insert element 3. delete element 4. find next element 5. find smallest 6. find largest 7. find all elements in given range 8. trace element: print the tree path to element + (if element in hash table then print contents of the specific row of the hash table) Input: The input is a file. The file will consist of multiple lines of words, each line containing one word. Output: If output is needed then print all the elements in "INORDER" and at a leaf node, say "Hashtable:" and print the element of the hash tables and then print "End". Example: Hashtable: A,B End, CA, D COMPULSORY: JUST USE "CIN" AND "COUT" FOR INPUT AND OUTPUT. You can use "program > [login to view URL]" to redirect your output to a file.  The hash table is defined as follows: 1. It has size of 64. The total data structure has size 64*16+15=1039. 2. It uses separate chaining. 3. The hash function uses the multiplication method. Take the word and convert it to an number which is the sum of their individual ascii values; e.g. CA will be 132, as Ascii of C is 67 and that of A is 65; so 67+65=132. Then multiply the number with a constant. Choose the lower order bits and shift right to obtain 6 bits as the hash value.