Your implementations should be efficient, and you should be able to demonstrate that your data structures achieve their expected asymptotic bounds using your instrumentation for measurement (and hopefully by timing them as well; if not, explain why timing doesn't work). Moreover, you should be able to intelligently compare your implementations using your measurements (time is easy to compare; can you compare your instrumented measurements?).
For example, you might measure the number of nodes accessed in an AVL tree for various sizes and insertion sequences to check its performance. This is easily compared against the number of accesses for another type of search tree or the number of probes in a hash table (but how would the hash function fit in?).
You should have one "reasonable" application (something like word counting, for instance) and several dummy applications designed specifically to show off one data structure or another (e.g., counting frequencies of random numbers might show off hash tables). Gather results for running each data structure on each application and discuss the results.
You may be able to exceed our expectations on this project by implementing more data structures than we mention above; however, more likely to truly impress us would be solid, reusable, and clean implementations, and really interesting and profound test results and applications.
Please verify your choices with us before you start the project. We may recommend against some combinations (like Treap plus Red-Black plus top-down splay tree which does not really represent a wide variety). Most of these are covered in your book; we can supply you with further material and references on the rest.
Many graph algorithms require priority queues (and some require decreaseKey and increaseKey or complex structures like Fibonacci Heaps). Also, there's an application called n-body simulation that uses priority queues. Finally, Huffman encoding, a compression technique, uses priority queues.
Up-trees as well as many graph algorithms assume a simple numbering of nodes which can be used to access values quickly, but in truth this requires a good dictionary. These might make good "reasonable" application for dictionaries!