This is a read-write lock version of the BinarySearchTree class. This solution increases the possible concurrency, by splitting the operations on the tree into two classes: those that only read the tree (isEmpty and search); and those that change the tree (insert and delete). There is a single read-write lock which allows either multiple searching threads to access the tree at the same time or a single insertion or deletion thread to access the tree. The implementation of the methods is otherwise identical to the fully-synchronized version.

ReadWrite locks were covered in lecture 12, Synchronisation in Java II. Note that, for consistency with the problem specification (and the fully synchronized version) the methods ignore interrupts during lock acquisition. (The lock() and unlock() methods of the Lock interface implemented by the read and write locks provided by the ReentrantReadWriteLock class ignore interrupts during lock acquisition.) This ensures that methods on the BinarySearchTree, once invoked, are guaranteed to complete. If a thread is interrupted while performing an operation on the tree, it returns normally with the interrupted status set to true.

Last modified: 11:06, 18-Mar-2008