Award Date


Degree Type


Degree Name

Master of Science in Computer Science


Computer Science

First Committee Member

Ajoy K. Datta

Second Committee Member

Lawrence Larmore

Third Committee Member

Yoohwan Kim

Fourth Committee Member

Emma Regentova

Number of Pages



We present a partial blocking implementation of concurrent binary search tree data structure that is contention friendly, fast and scales well. It uses a technique, called lazy splaying to move frequently accessed items close to the root without making the root of the tree a sequential bottleneck. Most of the self adjusting binary search trees are constrained to guarantee the height of a tree even in the presence of concurrency. But, this methodology roughly guarantees the height of a tree only in the absence of contention and limits the contention during concurrent accesses.

The main idea is to divide the update operation into two operations:an eager abstract modification with lazy splayingthat completes quickly and makes at most one local rotation of the tree on each access as a function of historical access frequencies; anda lazy structural adaptation with long/semi splayingwhich implements top down recursive splaying of the tree that may be postponed to diminish contention and re-balance the tree during less contention. This way, the frequently accessed items perform full splaying but after few accesses only and always appear near the root of the tree. Whereas, the infrequently accessed items will not get enough pushes up the tree and stay in the bottom part of the tree.

As in sequential counting based splay tree, the amortized time bound of each operation isO(log N), whereNis the number of items in the tree.


Binary Search Tree; Computer multitasking; Data structures (Computer science); Database searching; Search theory


Computer Sciences

File Format


Degree Grantor

University of Nevada, Las Vegas




IN COPYRIGHT. For more information about this rights statement, please visit