Homework 7

CMP 338: Data Structures & Algorithms
Lehman College, City University of New York
Spring 2022

This Homework Is Due By 11:59 PM on Wednesday April 27, 2021

Overview

In this assignment you will be adding functionality to the BinarySearchTree class that we worked on in class.

You will also be using the TestTimes class with the expanded functionality from Homework 4 .

You will also be writing a driver to test the BinarySearchTree.

Finally, you will be analyzing the performance of the test cases.

Details

1. TestTimes zyLab

   You will copy the TestTimes class that you enhanced with added functionality in Homework 4 to the project you are using for this assignment. This TestTimes class implements the expanded TestTimes Interface . Please note that you will also have to re-submit TestTimes.java to zyBooks in the TestTimes zyLab.

2. BinarySearchTree zyLab

   You will write the BinarySearchTree class which implements the BinarySearchTreeInterface . The interface may be downloaded from here .

3. TreeNode zyLab

   You will write the TreeNode class. Please see the TreeNode documentation for all the methods you will need.

4. TreeElementIterator zyLab

   You will write the TreeElementIterator class which will implement the Iterator Interface and provide the additional functionality shown in the TreeElementIterator documentation.

5. BinarySearchTreeDriver zyLab

   You will write the BinarySearchTreeDriver class which will implement the BinarySearchTreeDriver Interface. The interface may be downloaded from here .

Required Tests

Definitions:

The BinarySearchTreeDriverInterface includes an enum defining all the tests that you must run:

1. BinarySearchTreeDriverInterface.TestType

   All the elements being added and removed from the lists must be instances of the Person class, you can dowload it from here .

   BinarySearchTreeDriverInterface.Insert:

   1. Initialization: Create an empty BinarySearchTree.
   2. Test: You will use the insert(E element) method to insert 131,071 Person objects .

   BinarySearchTreeDriverInterface.Find:

   1. Initialization: Create a BinarySearchTree and populate it with 131,071 Person objects.
   2. Test: You will use the Find(K key) method to find all the Person objects that were inserted during the initialization.

   BinarySearchTreeDriverInterface.Delete:

   1. Initialization: Create a BinarySearchTree and populate it with 131,071 Person objects.
   2. Test: You will use the delete(K key) method to remove the Person objects that were inserted during the initialization, one at a time.

   BinarySearchTreeDriverInterface.Balance:

   1. Initialization: Create a BinarySearchTree and populate it with 131,071 Person objects.
   2. Test: You will use the balance() method to balance the BinarySearchTree.

   BinarySearchTreeDriverInterface.FindBalanced:

   1. Initialization: Create a BinarySearchTree and populate it with 131,071 Person objects, you will also have to balance the BinarySearchTree.
   2. Test: You will use the Find(K key) method to find all the Person objects that were inserted during the initialization.

   BinarySearchTreeDriverInterface.DeletBalanced:

   1. Initialization: Create a BinarySearchTree and populate it with 131,071 Person objects, you will also have to balance the BinarySearchTree.
   2. Test: You will use the delete(K key) method to remove the Person objects that were inserted during the initialization, one at a time.

Output From Driver Main Method

Please note that, in addition to implementing the BinarySearchTreeDriverInterface, you are also required to write your own public static main(String[] args) method in BinarySearchTreeDriver.java.

Your main() method will have to call the runTestCase() method for each of test cases listed above a total of ten times for each test case:

For each call to the runTestCase() method your main() method will print out a table with the following output:

BinarySearchTree Test Times
          	     Run 1       Run 2 	     Run 3       Run 4 	     Run 5      Run 6 	     Run 7      Run 8 	     Run 9      Run 10      Average
          	     Micro       Micro 	     Micro       Micro 	     Micro      Micro 	     Micro      Micro 	     Micro       Micro       Micro 
          	    Seconds     Seconds	    Seconds     Seconds	    Seconds    Seconds	    Seconds     Seconds	    Seconds     Seconds     Seconds
          	----------- -----------	----------- -----------	----------- -----------	----------- -----------	----------- ----------- -----------
        Insert
          Find
        Delete
       Balance
  FindBalanced
DeleteBalanced


BinarySearchTree Memory Usages
          	     Run 1       Run 2 	     Run 3       Run 4 	     Run 5       Run 6 	     Run 7       Run 8 	     Run 9      Run 10      Average
          	     Kilo        Kilo  	     Kilo        Kilo  	     Kilo        Kilo  	     Kilo        Kilo  	     Kilo        Kilo         Kilo 
          	     Bytes       Bytes 	     Bytes       Bytes 	     Bytes       Bytes 	     Bytes       Bytes 	     Bytes       Bytes       Bytes 
          	----------- -----------	----------- -----------	----------- -----------	----------- -----------	----------- ----------- -----------
        Insert
          Find
        Delete
       Balance
  FindBalanced
DeleteBalanced
  

Please note that the test times and the average are in Micro Seconds and the memory usage is in Kilo Bytes. You will need to make the necessary conversions.

Sample Output

BinarySearchTree Test Times
          	     Run 1       Run 2 	     Run 3       Run 4 	     Run 5       Run 6 	     Run 7       Run 8 	     Run 9      Run 10      Average
          	     Micro       Micro 	     Micro       Micro 	     Micro       Micro 	     Micro       Micro 	     Micro      Micro       Micro 
          	    Seconds     Seconds	    Seconds     Seconds	    Seconds     Seconds	    Seconds     Seconds	    Seconds     Seconds     Seconds
          	----------- -----------	----------- -----------	----------- -----------	----------- -----------	----------- ----------- -----------
        Insert	  22289.473   10401.357	   9226.934    9571.146	   9855.370    7783.710	  17285.624   10398.651	   8818.641    8648.762   11427.967
          Find	  17384.680    6919.186	   8158.453    9332.485	   8396.683    8501.915	   6338.461    8605.784	  17932.845   15747.986   10731.848
        Delete	  25917.302   11200.751	  10562.891    6279.695	   7044.151    8492.105	   6926.862    8279.499	   5658.933    9746.044   10010.823
       Balance	  43955.041   40091.547	  28241.756   18721.375	  37972.587   28740.559	  32867.534   24678.109	  35751.709   23887.884   31490.810
  FindBalanced	   5797.849    8762.715	  13826.884    7994.664	   8423.927    7503.467	   9511.452    8302.276	   8679.280    7031.385    8583.390
DeleteBalanced	   5120.916    5105.849	   5691.481    5651.009	   5492.936    5867.571	   6727.116    7124.879	   4622.184    5158.656    5656.260


BinarySearchTree Memory Usages
          	     Run 1       Run 2 	     Run 3       Run 4 	     Run 5       Run 6 	     Run 7       Run 8 	     Run 9      Run 10      Average
          	     Kilo        Kilo  	     Kilo        Kilo  	     Kilo        Kilo  	     Kilo        Kilo  	     Kilo        Kilo         Kilo 
          	     Bytes       Bytes 	     Bytes       Bytes 	     Bytes       Bytes 	     Bytes       Bytes 	     Bytes       Bytes       Bytes 
          	----------- -----------	----------- -----------	----------- -----------	----------- -----------	----------- ----------- -----------
        Insert	   6553.758    9175.219	  11796.734   14418.234	  17039.727   19661.227	  20971.984   23593.484	  26214.977   28836.492   17826.184
          Find	  36700.977   40633.242	  45876.242   49808.484	  53740.750   58983.750	  62915.992   32593.688	  37784.195   41677.078   46071.440
        Delete	  49462.805   52058.063	  54653.313   57248.555	  59843.820   62439.063	  65034.328   67629.570	  68927.203   71522.445   60881.916
       Balance	  79308.219   84498.719	  89689.211   94879.719	  48332.445   53541.219	  58750.000   66563.164	  71771.953   76980.734   72431.538
  FindBalanced	  84793.914   90002.688	  95211.469  100420.242	 105629.023  110837.797	 116046.578  121255.352	 126464.133  131672.906  108233.410
DeleteBalanced	 142090.445  144694.828	 147299.227  149903.617	 155112.391  157716.789	 160321.180  165529.922	 168134.320  170738.711  156154.143

  

Analysis:

Using the tables you created by running BinarySearchTreeDriver.main(), copy your results and your graphs into a Microsoft Word document and answer the following questions using 1-3 complete sentences for each question:

1. Create graphs from the test times you measured.
2. Discuss the difference in test times between the different test cases. Explain the reason(s) why the test times are different between the test cases. Did the results match your expectations? Why or why not? Be as specific as possible.
3. Discuss the difference in memory usage between the different test cases. Explain the reason(s) why the memory usage are different between the implementations. Did the results match your expectations? Why or why not? Be as specific as possible.

Please submit the completed assignment in your zyBooks , in the Homework 7 Chapter.

Please submit your analysis on Blackboard as a typed Microsoft Word file (.docx). No other forms of submission will be accepted. Please include your graphs in the same file as your analysis.