A Relaxed Balanced Non-Blocking Binary Search Tree

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.