G52CON Coursework: Binary Search Tree

A binary search tree is to be used by a multi-threaded Java program to store data.  Design and implement a Java BinarySearchTree class which provides the following public methods:

• BinarySearchTree(): constructs an empty binary search tree.
• boolean isEmpty(): returns true if the tree contains no data items; otherwise returns false.
  
• boolean insert(Object x): adds a node containing the data item x to the tree and returns true.  If the tree already contains a node whose contents  equals() x, does nothing and returns false.
• boolean search(Object x): returns true if the data item x is present in the tree; otherwise returns false.
  
• boolean delete(Object x): removes the node containing the data item x from the tree if it is present and returns true, otherwise does nothing and returns false.

Note that the methods do not throw checked exceptions. Your implementation should allow safe concurrent access to instances of the BinarySearchTree class by multiple threads.  You may assume that the data items to be  stored implement the Comparable interface and their natural ordering is consistent with equals().

Notes

Your solution should include a BinarySearchTree class which has the public interface given above. However you can implement additional classes and methods as part of your solution.

The tree stores Objects (which you know to be Comparable), and you can rely on this when you need to do comparisons in your code. It is therefore safe to cast Objects to Comparable, e.g., given an object you are searching for, a, and an object in the tree, b, you can do something like:

((Comparable)a).compareTo((Comparable)b)

The whole point of the coursework is to gain experience in writing concurrent programs. Solutions which make use of Java collections such as TreeSet or use the Collections framework synchronization wrappers, e.g., Collections.synchronizedSortedSet(), are therefore not acceptable. You should write your own binary search tree and synchronize it yourself. However using Java's built in synchronization and/or the concurrency classes (in java.util.concurrent) to implement the synchronization is ok.

Conversely, there is no need to 'improve' on the binary tree, e.g., no extra credit will be given for implementing the specified ADT using a Map or keeping the tree balanced.

Lastly, please don't include a user interface in the code you submit: any  code which attempts to open a window or which requires user input will fail the automated tests. If you develop test cases or a test harness, keep this separate from the code you submit and don't include it in your submission. You may find the G52CON coursework basic tests and/or the JUnit testing framework and its multi-threaded extensions useful while developing your code.

If you have any questions about what constitutes an acceptable solution, email me.

Submission

The submission consists of two parts:

1. the code implementing the BinarySearchTree class (in a single file called BinarySearchTree.java or in several files one of which is called BinarySearchTree.java); and
2. an essay explaining your solution and why it is correct (in pdf format: submissions in other formats will not be marked).

Submissions are due at 3:30pm on Friday the 14th of March and should be made electronically using the coursework submission system. The ID for the G52CON coursework is 90. You will be notified by email when your submission has been successfully collected.

Assessment

Marking will be based on the correctness and clarity of your solution, the degree of concurrent access it allows, and the correctness and clarity of the your explanation of the code. A correct solution will pass, but for a higher mark you solution should also maximise concurrency. There will be a (small) prize for the best solution.

You are reminded of the School's Policy on Plagiarism. For the purposes of this coursework, the policy shall be interpreted as follows.

Your code should be written entirely by you. You may discuss algorithms and source material, but you should write your own code independently. Do not under any circumstances show your code to another student, look at another student's code, or allow through negligence another student to see your code.

You may make use of material from other sources (e.g. textbooks or class libraries) so long as this is properly cited. Any material not written by you and included in your submission without due reference to the source is a case of plagiarism. To give due reference in text you should place the quotation in italics and surround it by quotation marks and provide full reference details to the source. To give due reference to source code you should place comments at the start and end of the code fragment that you have copied. These comments should give a clear reference to the source of the code, and the extent of the code which you have not written yourself. The only code that you may use without reference is that provided in the module lectures or the module website, and the standard Java libraries.