Skip to main content

Homework 08: Zipcodes - AVLTrees

Due: 2024-05-09 23:59:00EDT

Overview

Rewrite your HW04 to use an AVL tree as your main data structure, instead of a sorted ArrayList. Recall that the zipcodes in uszipcodes.csv are already listed in lexicographic order and thus using an unbalanced binary search tree (i.e. LinkedBinaryTree) will guarantee to result in a linear tree (when you insert in sorted order) and thus will have worst-case O(n) complexity on all operations. This is why an AVL-tree is a good choice. Note that the AVL-tree’s advantage over a sorted ArrayList is not on lookup - both binary search on sorted array and AVL have O(logn) lookup, however, an AVL supports O(logn) insertion and deletion but an ArrayList only has O(n) insertion and deletion because of shifting.

Requirements:

Ensure your lab is working correctly before moving on.

  1. Download the BinaryTree.java interface using: wget https://raw.githubusercontent.com/BMC-CS-151/BMC-CS-151.github.io/main/hws/hw08/BinaryTree.java Now, copy over DriverHW04.java, PopulatedPlace.java, Place.java, LookupZip.java, LocatedPlace.java and the .csv files from HW04. Change the name of DriverHW04 to DriverHW08. Next copy over your LinkedBinaryTree.java and AVLTree.java from Lab10.

  2. Compile your Lab LinkedBinaryTree.java with the new BinaryTree interface file. You should see an error requiring you to implement a get method. Implement the method accordingly.

  3. Once your AVLTree is functional, modify your hw4 files to use an AVL instead of an ExpandableArray. Think about what methods to use your AVLTree for storage and lookup. For example, think about what methods to use instead of set. Remove any old code related to sorting or BinarySearch since that doesn’t make sense for an search tree data structure.

  4. The rest of the restrictions and correctness requirements for HWs 01 and 04 remain:

zipcode: 19010
Bryn Mawr, PA 40.02 -75.31 21103

zipcode: 99400
No such zipcode

zipcode: 91729
Rancho Cucamonga, CA 34.09 -117.56

zipcode: 97252
Portland, OR

zipcode: 00000
Good Bye!

More sample input/outputs are available here:
wget https://raw.githubusercontent.com/BMC-CS-151/BMC-CS-151.github.io/main/hws/hw04/in.txt
wget https://raw.githubusercontent.com/BMC-CS-151/BMC-CS-151.github.io/main/hws/hw04/out.txt

Runtime Analysis

Time your new implementation using commandline redirection of in.txt test file from HW04. That is, issue the following command at the prompt: time java DriverHW08 uszipcodes.csv ziplocs.csv < in.txt > myout.txt

Compare the result with your HW04 implementation. Is there a speedup? Report your findings in your README.

Command Line Input

Add support for the following flag:

  1. -d indicates that you should print additional debugging information on your AVL tree, in the following format: height of your AVL tree, as an integer on its own line, followed by the toString of your tree. For example, if there are only the following three zipcodes in the input (19010, 91729 and 97252), your output should be:
1
19010(1) 91729(2) 97252(1)

Modify the toString of your place classes to only print the zip. Print this additional debugging output before taking query input interactively, as usual. If -d is not given, program should behave/output exactly the same HW01 or HW04.

Submitting

Submit the following files to the assignment called HW08 on Gradescope

  1. README: The usual plain text file README
    • Your name
    • Discussion: Everything listed above
    • How much time you spent on the assignment
    • What did you learn?
    • (Optional): Any feedback or comments
  2. Source files:
    • AVLTree.java
    • DriverHW08.java
    • LinkedBinaryTree.java
    • LocatedPlace.java
    • LookupZip.java
    • Place.java
    • PopulatedPlace.java

Make sure to name these files exactly what we specify here. Otherwise, our autograders might not work and we might have to take points off.
DO NOT submit a .docx or .pdf file.
DO NOT submit any .class files or any of the csv files.
DO NOT submit BinaryTree.java

Copying the files

You will likely want to submit the files from your own laptop/computer. To copy the files from goldengate to your own machine, open up a terminal on your own computer. If you have a mac or linux, you can use the Terminal application, if you have a windows you can use the Powershell app.

Run the following command:

$ scp <username>@goldengate.cs.brynmawr.edu/home/<username>/cs151/homeworks/hw00/*

Make sure to replace <username> with your username. scp is a command to secure-copy files from one server to another. In this case, from goldengate to your own machine.