Part 2: Sorted Map Insert, the AVL-G tree, Polygonal Maps, and Road Adjacency Lists

For the remainder of the semester, you will have the pleasure of implementing the data dictionary with both the TreeMap from part1⁴ an AVL-G tree to implement the SortedMap interface. In part 2, you will be required to insert a key into the data dictionary and do single-item queries. In part 3, you will be required to support both insert and delete, and may choose to implement range queries for the data dictionary.

The new spatial structure for part 2 and part 3 is the PM quadtree (PM1 or PM3). Part 2 requires you to implement only insert for the PM3. Of course, there will be spatial range searches, and the usual annoying input and output formats.

Plus, we're building on the last part. You're probably insanely bored of TreeMaps and Comparators by now, but now that you've had some practice with them in the minors, it's time to use your mastery of modifying pre-existing data structures to your advantage. In addition, all you mathphobes will finally get over your fear, since part of this project might involve the derivation of some formulas.

The individual commands for part 2 appear in Section 7.3, after detailed discussions of the structures involved and implementation requirements and hints. In general, part 2 requires you to implement insert and find_key operations for the dictionary and spatial structures, while part 3 adds in the delete operations. Please don't be scared-remember how far away college (and graduation!) once seemed. It gets worse out there; so, at least try to kick up your performance rate now while it's safe.

*** Adopting any source code or pseudocode of a PM quadtree from Internet search, that is, any code that is not provided or linked as resources of this course, is explicitly prohibited. You have to build your own.