Concurrent manipulation of binary search trees
To implement a concurrent binary search tree system (CBSC) that can
support any number of concurrent processes which perform searching, insertion,
deletion, and rotation on the tree, but allow any process to lock only a
constant number of nodes at any time. Also, in the systems, searches are
essentially never blocked.
H.T. Kung and Philip L. Lehman.
Concurrent manipulation of binary search trees.
ACM Transactions on Database Systems, 5(3):354-382, 1980.
Additional reading material
R. Bayer and M. Schkolnick.
Concurrency of operations on B-trees.
Acta Informatica, 9(1):1-21, 1977.
Starving philosophers: experimentation with monitor synchronization.
In Proceedings of the 32st SIGCSE Technical Symposium on Computer
pages 317-321, 2001.
Stephen J. Hartley.
Concurrent programming: the Java programming language.
Oxford University Press. 1998.
Michael T. Goodrich and Roberto Tamassia.
Data structures and algorithms in Java.
Object-oriented software design and construction with Java.
CBSC system analysis and design;
CBSC SEARCH-INSERTION System Implementation in Java;
CBSC SEARCH-INSERTION-ROTATION system Implementation in Java;
CBSC SEARCH-INSERTION-ROTATION-DELETION system Implementation in Java;
CBSC simulation program using JAVA Applets.