Lab 8🔗

Binary Search Trees! For real, this time.

First, implement a "Spot" record, representing a place on Earth. It should contain a name, a latitude, and a longitude. Both latitude and longitude should be in degrees.

Implement a static "randomSpot" method. It should generate a random name as a string of four random characters, a longitude as a random double from -180 to 180, and a latitude as a number between -90 and 90, generated by taking the inverse sine of a number between -1 and 1.

Make your "Spot" record "Comparable" to other Spots, by implementing a "compareTo" method that returns either -1, 0, or -1, depending on whether the other spot’s longitude is less than, equal to, or greater than the current spot.

Implement a generic binary search tree; it should contain methods for insertion, deletion, and searching.

Create a binary search tree containing a thousand, a hundred thousand, ten million, and fifty million elements. How long does it take to insert a random element into each of these trees? Draw a graph of your result.

Develop the "greatestLowerBound" function, that accepts a binary search tree and a longitude, and returns the spot in the tree that is closest to the given longitude without going over.