Lab 7: Binary Search Tree and Benchmarking

Overview

This week you will add a binary search tree implementation to your collection of AutoCompleter implementations. You will replace your GUI application with a benchmarking program and analyze the runtime performance of your implementations.

Assignment

Binary Search Tree Implementation

Implement the AutoCompleter interface using a binary search tree. Your class must have one private attribute: private final TreeSet<String> items that is assigned via a one-argument constructor. Note: the constructor should remove any strings in the tree passed to the constructor.

AutoCompleter interface

Add a static method, getString(int length), that returns a String with length randomly selected lowercase letters in it. This method will be used to generate word lists to be used in your benchmarking activities.

O() Analysis

Create a Word document and provide O() anaylsis for the add(), exactMatch(), and allMatches() methods defined in the AutoCompleter interface for your unsorted collection, sorted list, and binary search tree implementations. Be sure to clearly explain your reasoning.

Benchmarking Program

Create a benchmarking program that benchmarks the time it takes to complete the add(), exactMatch(), and allMatches() methods defined in the AutoCompleter interface. Generate data and plot the results for all of your implementations of the interface. Place the graphs in your report. In your report, explain how you decided on the number of strings in your auto completer objects. Suggest improvements for how your data gathering process could be improved, if you had more time.

Just For Fun

Ambitious students may wish to:

• Benchmark the allNonPrefixMatches(String substring) method that was added to the interface.

Acknowledgment

This laboratory assignment, developed by Dr. Chris Taylor.