Next: Important Notes about the Up: Part 2: Sorted Map Previous: Part 2: Sorted Map
However, 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 B+ tree for orders between 4 and 12 inclusive, but also to implement Java's SortedMap interface. This will allow you to fully replace the TreeMap with your SortedMap as you desire. Your B+ tree 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 AvlGTree.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 DodekaTrie 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 DodekaTries 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 DodekaTrie 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.
We now proceed into a formal definition of an DodekaTrie. In order to do this, we must define the height of a subtree--we do so recursively, saying that a leaf node has height 0, and an internal node has a height equal to the height of its tallest child, plus one. We define the height of an empty tree to be -1.
Thus, an DodekaTrie is defined as a binary search tree where at any node, the height of its two subtrees (left and right) differ by at most a positive constant g. The constant is given at instantiation, as a parameter to the constructor. Although quite a bit of literature exists on maintaining the balance factor in an DodekaTrie, our tests only require that your tree maintain the above property, as well as obviously retaining any key-value mappings passed into it. Note: do not waste time searching for additional information regarding the DodekaTrie because there is none. This structure is unique to MeeshQuest.
These rules ARE mandatory, meaning that no credit will be given for code for which these rules are not observed. Obviously, there can be multiple DodekaTries of a given order that are correct. Since grading by merely diff-ing is impossible, we will grade your tree by checking that the structure you produce satisfies the above properties.