In this assignment, you must implement a sorted list abstract data type that maintains a sorted list of keys of type ComparisonKey. Your implementation must use a binary search tree to represent the list.
Implement the ADT by defining a class SortedList that provides
the following public methods:
|SortedList()||SortedList||A constructor; returns an empty sorted list.|
|empty()||boolean||Determines whether the sorted list is empty.|
|length()||int||Returns the length of the list, i.e. how many keys it contains.|
|insert(ComparisonKey k)||void||Inserts the key k in the list; the key must not already be in the list.|
|remove(ComparisonKey k)||void||Removes the key k from the list; the key must be in the list.|
|findKey(ComparisonKey k)||int||Searches the list to see if the given key k is in it. If it is, it returns its index, otherwise it returns -1.|
|keyAt(int n)||ComparisonKey||Returns the key that is at index n in the sorted list. It must be the case that 1 <= n <= length().|
|print()||void||Prints the sorted list. Each key is on a separate line with its index.|
The index of a sorted list item is assigned as follows: index 1 to the first item, index 2 to the second item, and so on, up to index length() for the last item. For example, if we have inserted the keys ORY, JFK, and ZRH in the sorted list, then assuming that the string keys are compared in the normal way, the sorted list will be (JFK, ORY, ZRH), and the index of JFK is 1, the index of ORY is 2, and the index of ZHR is 3.
By using a binary search tree to implement the ADT, it is possible to perform insertion, deletion, and search in O(log n) in the average case. Make sure your implementation achieves this. You may implement your SortedList class my modifying the binary search tree implementation discussed in class; it is available in the a4 subdirectory of the course directory.
Note that the findKey method required is different from the one in the binary search tree implementation discussed in class; it must return the index of the key (or -1 if it is not found). The keyAt method can be used to retrieve the key at a given index position in the sorted list. Both methods have to search the binary search tree. You can implement them efficiently by adding a new attribute to tree nodes that contains 1 + the number of nodes in the left subtree of the node.
For debugging purposes, your class should also provide the following
|printTree()||void||Prints the binary search tree in infix order. It indents 4 spaces for every level past the root. For each node, it prints the key, its index, and the count of nodes in its left subtree plus 1.|
|main()||void||A test driver for the class.|
Here is an example of a run of the test driver:
tiger 78 % java SortedList
e check whether the list is empty
l print the length
i key insert the given key
r key remove the given key
f key search for key & return index
k index return the key at the given index
p print as a list
t print as a tree
? i ORY
? i ZRH
? i JFK
? i MEX
? i BRU
? f MEX
? f MAA
? k 5
tiger 79 %
Note that assignments are supposed to represent your own individual work. Do not misrepresent another's work as your own; it will be considered academic dishonesty if you do. If you have any questions about this please ask your course instructor.
Remember to include a copy of the marking sheet supplied as the cover
page of your report.