COSC 1030: Assignment #4

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:
 

Name	Returns	Purpose
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 methods:
 

Name	Returns	Purpose
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
Commands are:
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
q        quit

? l
0
? i ORY
? i ZRH
? i JFK
? i MEX
? i BRU
? l
5
? p
1-BRU
2-JFK
3-MEX
4-ORY
5-ZRH
? t
        1-BRU-1
    2-JFK-2
        3-MEX-1
4-ORY-4
    5-ZRH-1
? f MEX
3
? f MAA
-1
? k 5
ZRH
? q
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.