A Relaxed Balanced Non-Blocking Binary Search Tree
conference contributionposted on 2020-11-10, 01:37 authored by Manish SinghManish Singh, lindsay Groves, Alex Potanin
We 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.