use C++ please

Main objective: We are going to design a fast data structure to perform insertions and range queries on text. Basically, your input file will have a (long) list of words to insert, interspersed with range queries. The latter determines the number of words seen so far in a given range. For example, if the range is "ab and bc", you have to find the number of words that are lexicographically between "ab" and "bc". What makes this assignment particularly challenging is that your data struc- ture will need to handle a million inserts and up to two million range queries. So you will have to build a data structure that is really efficient. You cannot use any built in data structures for storing the words and an- swering range queries. You can use libraries for I/0 and string processing. Data structure instructions: You cannot use inbuilt data structures in C++. (Actually, there probably isn't an inbuilt data structure that solves this assignment.) For half credit, simply store the words in a standard BST. For full credit, you need to build a self-balancing tree that stores the words. Since that's what I taught in class, we will use the AVL tree for this assignment. Note that you do not need to implement deletions, just insert, find, and range queries. How to do range queries? (I'm glad you asked.) A naive method would be to simply traverse the tree and find all keys in the given range. This would be a O(n) algorithm, where n is the number of nodes in the tree. For half credit, this is enough. For full credit, you need to process a million such queries (and n is at least a few hundred thousand), this is not feasible