Master of Science in Computer Science
First Committee Member
Ajoy K. Datta
Second Committee Member
Third Committee Member
Fourth Committee Member
Emma E. Regentova
Fifth Committee Member
Number of Pages
A binary search tree (BST) is a fundamental data structure for maintaining data in a way to allow fast search. As multi-core processors are widely used nowadays, such data structures require the ability to handle concurrent accesses to exploit the concurrent hardware. There are several algorithms on lock-based as well as lock-free BST with and without self-balancing. On the other hand, only a few reports can be found on lock-based self-adjusting BST. To the best of our knowledge, there are no algorithms for lock-free self-adjusting BST. Lock-free guarantees overall progress even if some processes fail, whereas lock-based algorithms fail to progress in the case of a faulty process. In this study, a lock-free self-adjusting binary search tree is proposed using compare-and-swap (CAS) operations. The algorithm is based on lazy splaying which moves frequently accessed items near the root in a contention friendly manner. The algorithm will include search, delete, insert, and restructuring operations.
BST; CAS; Lazy Splay; Non-blocking; Splay Tree
Sueki, Sachiko, "Lock-free Self-adjusting Binary Search Tree" (2017). UNLV Theses, Dissertations, Professional Papers, and Capstones. 3174.