ICPPManish.pdf (332 kB)
Download fileA Relaxed Balanced Non-Blocking Binary Search Tree
conference contribution
posted on 2020-11-10, 01:37 authored by Manish SinghManish Singh, lindsay Groves, Alex PotaninWe present a new relaxed balanced concurrent binary search
tree in which all operations are non-blocking. We utilise
the notion of separating balancing operation and update
operations in a concurrent environment and design a nonblocking balancing operation in addition to the regular insert,
search, and relaxed delete operations. Our design uses a single-word CAS supported by most modern CPUs.