Part 3: Sorted Map, AvlGTree, PM quadtrees, and True Delete

In part 2, you were asked to consider replacing your TreeMaps with AVL-g trees (modified AVL trees that allow their subtree heights to vary by at most $g$). For more on the AVL-g, see the description in part 2: www.cs.umd.edu/users/meesh/cmsc420/ProjectBook/part2. It's been cut for brevity.

In part 3, you'll be asked to implement a (immediate) delete for your AVL-g. Unlike lazy deletion, immediate deletion deletes a node as soon as delete is called and rebalances immediately.

Now that delete()'s on the table, so's all of SortedMap. Notably, map.remove() and all of the remove()s from the various views (entrySet(), etc.) must work. See the Java API for all the gory details. This semester, you do not need to implement keySet(), values(), headMap(), tailMap(). You could, theoretically, now expunge any lingering TreeMaps from your code. I'd recommend you keep your guarded structure around, however: you need a working dictionary for much of the project, and there's really nothing we can do if yours mysteriously leaks cities.

One last comment on the AVL-g: the tricky parts of entrySet() (and all other views) become much more important here. Insertion wasn't supported in all of those views, as you recall, so the need to reflect changes was really only one-way. Deletion is supported from the objects returned by entrySet() and subMap() which makes this relation two-way. (You hopefully already know how to do this, though: it was always two-way for subMap().)

Part 3 will also require you to implement PM1 insert() and PM delete(). You may want to refer to the part 2 spec for the piece on validators and code reuse. There's even pseudocode for delete(). Because the spatial structure now incorporates zooming and metropoles, you'll need a way to accommodate metropole coordinates. One such way is a PR Quadtree from part 1, since you will only be storing coordinates (see below).