A Relaxed Balanced Non-Blocking Binary Search Tree
Manish Singh

Lindsay Groves

Alex Potanin

manish.singh@weltec.ac.nz
Wellington Institute of Technology
Lower Hutt, New Zealandlindsay.groves@ecs.vuw.ac.nz
Victoria University of Wellington
Wellington, New Zealandalex.potanin@ecs.vuw.ac.nz
Victoria University of Wellington
Wellington, New Zealand

ABSTRACT
We present a new relaxed balanced concurrent binary searchtree 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 singleword CAS supported by most modern CPUs.

CCS CONCEPTS• Computing methodologies → Concurrent algorithms.

KEYWORDS
Non-blocking,lock-free, Concurrent Binary Search Tree

1INTRODUCTION

To counter Intel’s single socket 28-core processor, AMD announced a 32 core processor with 64 threads for desktops
recently. This trend in embedding more and more cores in
multi-core processors has necessitated the design of scalable
and efficient concurrent data structures. Due to the asynchronous model of computation in multi-core systems designing ofdata structures which can efficiently synchronise concurrent
access are considered to be hard. A considerable amount ofresearch has been done towards making both blocking andnon-blocking concurrent versions of sequential data structures. Unlike blocking, a concurrent algorithm is non-blocking
if it ensures that no thread accessing the data structure is
postponed indefinitely while waiting for other threads that
operate on the data structure. Performance has been always
an important factor that will drive the design of these datastructures.
The Binary Search Tree (BST) is a fundamental datastructure. In recent years, many of concurrent BST (bothblocking and non-blocking versions) have been proposed [1–7].
However, only few designs include self-balancing operations.
Table 1 summaries some of the state of art concurrent BSTs.
Most of the published work try to emulate the sequential
specification of the data structure in their concurrent version.
This results in performance compromise as strict invariants
must be maintained in each operation execution. In a concurrent environment effects of some operations might cancel out
effects of other operations. In case of a self-balancing BST
each insert or delete operation requires a balancing operation
to be performed immediately to maintain the height of theICPP ’19, August 05–08, 2019, Kyoto, Japan2019. ACM ISBN 978-x-xxxx-xxxx-x/YY/MM. . . $15.00
https://doi.org/10.1145/nnnnnnn.nnnnnnn

Figure 1: Right Rotation example. T1: a thread carrying out asearch operation oblivious of ongoing concurrent rotation.

tree. In such scenarios a balancing operation might cancelout effect of other balancing operations on the same node.
This has led to the idea of relaxing some of the invariants ofthe data structure while designing their concurrent versions.
Relaxing some of the structural properties of a sequential
data structure in concurrent environment is not completely
a new idea. Lazy deletion is an example of relaxing the requirement that nodes are immediately removed from theconcurrent linked list. In a concurrent self-balancing trees
such as AVL or chromatic tree rotation operations are performed separately from insertion and deletion operations.
However, most previously published designs which includes
balancing operation are blocking or lock-based and therefore,
not immune to the problems associated with locks. We design a non-blocking relaxed balanced BST in which balancing
operations are done separately from the regular insert anddelete operations.

2

ALGORITHM DESCRIPTION

We implement a set in which the underlying data structure
is a BST. Our implementation supports search(k): to checkif the key is in set or not, insert(k): to add the key into theabstraction, delete(k): to remove the membership of key ifit is present in the dataset. A BST could behave similar toa linked-list where traversal could take O(n) time especiallywhen the input are in increasing or decreasing order. Inorder to prevent that our algorithm also supports rotation
operation and a abstract update operation. This design closely
tries to mirror the sequential version of BST except for thedelete operation, where key is first flagged as deleted andthen physically removed later by a dedicated separate threadwhich also carries the rotation operation. The aforementioned
dedicated thread traverses the tree in pre-order, carries out
first physical removal of deleted nodes, adjusts local heightsof the node and starts the rotation operation if the balance
condition is found to be violated.

ICPP ’19, August 05–08, 2019, Kyoto, Japan

Manish Singh, et al.

BSTType

BalOpnSyncTech

Add Info

Howley[5]Natrajan[1]Chaterjee[2]Bronshon[4]Crain[6]Drachsler[3]Our treeInternal
External
Internal
Partially External
Partially ExternalInternal
Partially Internalnonono
yes
yes
yes
yes

non-blocking
non-blocking
non-blocking
blocking
blocking
blocking
non-blocking

Descriptor basedEdge marking
threadedlock coupling
Eager abstract n lazy structural modification
logical ordering of updates, threaded
AVL based relaxed and delete operation

Table 1: Existing concurrent BST’s.

To achieve lock-freedom 1 any thread before carrying out
the actual operation which modifies the tree either the content
or structure first announces its intention. To do so the thread
first collects needed information into a structure known as
operation-descriptor and tries to insert a pointer to operationdescriptor into the operation field of that node using a CAS.
Once the pointer is inserted, the operation would not fail as
we have designed helping methods which ensure any otherconflicting thread will carry out the announced operation
before it carrying out its own. The idea is that the operation
owns the nodes or locations to be updated not a particularthread which makes it possible for other threads to finish
contending operations .
Updating multiple locations using a single word CAS whilepersevering atomicity of updated locations is a challenging
task. Especially, in case of rotation operation three locations
are needed to be updated automatically, we achieve thisby careful design of our rotation operation. Whenever abalance condition is found to be violated, the dedicated thread
prepares a operation descriptor then it tries to grab the nodeby inserting a pointer to the descriptor in the operation-fieldof parent of the node. If it is successful then it tries to do thesame for all the nodes involved in that particular rotation
operation using CAS. Failing to insert the pointer in any of
the nodes means that there is another operation on progress
and it should help the ongoing operation first then retry.
Once the first node is grabbed any other thread can finish theannounced rotation operation by first, grabbing the remaining
nodes then carrying out the rest of the operation. As shownin figure 1, first a newnode having same key as the node wherebalance violation have been occurred is created. After that
Right and left pointers of the newnode are allocated to thosechild which it would get after notation figure 1 (b). Next
step is to insert the newnode to its position after rotation,
as shown in figure 1 (c). In this case of right rotation thenewnode would be the right-child of node 𝐶. The third andlast step is swing pointer to connect 𝐶 to the parent 𝑃
directly effectively removing node 𝑁 from the tree.
A notable feature of our algorithm is that the rotation
operations are invisible to search operations, as a result, thelater simply traverses the tree and never restarts. A thread
carrying out delete operation simply marks the node to be
1

Both non-blocking, lock-free and thereby lock-freedom are synonymously used in literaturedeleted which is considered to be logically removed. The
deleted node then is physically removed by the dedicatedthread if it has no child or have only one child. Nodes withtwo child are not removed until it becomes one child nodeor both of its child are deleted. A Thread carrying out insert operation upon finding the insert location prepares anoperation-descriptor and tries to insert a pointer to the to beparent of the newnode. Similar to the rotation operation, oncethe operation-descriptor is successfully inserted the operation
is guaranteed to be completed. Otherwise it goes to help theongoing operation and restarts. While doing insert if thethread finds key present in the tree and the node is flaggedas deleted it simply sets off the deleted flag.

3SUMMARYIn our design, all the operations are non-blocking. The search
operation is free of any additional synchronization. We areevaluating performance of our algorithm on x86 _ 64 and
SPARC multi-core machines against the concurrent BSTs
shown in table 1. A mechanized proof outline has been doneusing the linearisability as correctness criteria. To the bestof our knowledge, this is the first design which utilises decoupling of operations as well as rotations to balance the tree ina non-blocking concurrent set-up.

REFERENCES[1] N. Mittal A. Natarajan. 2014. Fast concurrent lock-free binary
search trees. In Proceedings of the 19th ACM SIGPLAN Symposium on Principles and Prac- tice of Parallel Programming(PPoPP) (2014).
[2] Bapi Chatterjee, Nhan Nguyen, and Philippas Tsigas. 2014. Efficient Lock-free Binary Search Trees. In Proceedings of the2014 ACM Symposium on Principles of Distributed Computing (PODC ’14). ACM, New York, NY, USA, 322–331. https://doi.org/10.1145/2611462.2611500[3] Dana Drachsler, Martin Vechev, and Eran Yahav. 2014. PracticalConcurrent Binary Search Trees via Logical Ordering. SIGPLAN
Not. 49, 8 (Feb. 2014), 343–356. https://doi.org/10.1145/2692916.
2555269[4] Hassan Cha Nathan G. Bronson, Jared Casper and Kunle Olukotun.
2010. A practical concurrent binary search tree. ACM SIGPLAN
Symposium on Principals and Practice of Parallel Programming(2010).
[5] Jeremy Jones Shane V. Howley. 2012. A non blocking internalbinary tree. SPAA (June 2012).
[6] M. Raynal T. Crain, V. Gramoli. 2013. contention-friendly binary
search tree. In In Euro-Par. 229–249.
[7] YehudaAfek. 2012. A practical concurrent self-adjusting searchtree. Tel Aviv University (2012).