Next: Important Notes about the Up: Part 2: Sorted Map Previous: Part 2: Sorted Map
In Part 2, you will be asked to consider replacing the treemap of city names which is used as an index to the city objects with some other structure.
A treap is a binary search tree where each node is assigned a random numeric priority, and the nodes are in heap order with respect to those priorities. Two properties are guaranteed:
These rules ARE mandatory, meaning that no credit will be given for the Treap if these rules are not observed. Since grading by merely diff-ing is impossible, we will grade your Treap by checking that the structure you produce satisfies the above rules.
Since we're using Java and a fundamental feature of Java is its interfaces, your code will be required not only to properly implement the Treap specifications, but also to implement Java's SortedMap interface. This will allow you to fully replace the TreeMap with your SortedMap as you desire. Your Treap should be generic just like the TreeMap, and it should eventually implement every one of the SortedMap methods except headMap(), tailMap(), keySet() and values(). However, we will not test remove() until Part3. So, you can choose to delay it until after you've finished Part2.
But, since you don't implement remove in Part 2, this prevents you from properly implementing subMap().clear() and related functions. Therefore, your behavior for subMap().clear() won't be tested--but we advise that at this point you forward to Treap.this.clear(). If that sounded confusing to you, don't worry about it for now, but come back to it later. If you would like guidance on how to begin implementing SortedMap, there are two resources to which you can turn: we provide you with an example, SortedMapExample.jar, which shows a SkipList that has been used to implement SortedMap. You can find SortedMapExample.jar in the top level directory of the course files. Similarly, you can easily find the source code for Java's TreeMap online; Josh Bloch's implementation strategies may prove useful and relevant to your code. As always, if you take inspiration or structure from either of these sources please cite that in your README file.
Any portion of the TreeMap that uses the red-black tree explicitly (or the skiplist version) must be modified to use the Treap instead. Failure to do this will result in a deduction of the points that you tricked the submit server into giving you. It will not be treated as an honor code violation since the red-black tree is not the most intuitive creature that you will ever meet.
Although this probably won't be a problem for the Treap as much as some of the structures in the past, we expressly forbid you from actually using a skiplist or other complex data type inside your Treap code. That is, although you may be inspired (or more) by the code you see in TreeMap or SkipList, you may not actually use a TreeMap or SkipList in your implementation. The same goes for TreeSet (which, interestingly, is just a wrapper around a TreeMap--cool trivia!), HashSet or HashMap; basically, if you're using a structure that you feel probably duplicates the functionality of your SortedMap, you should not be using it.