Concurrent Trees

When working with more complex data structures, we need to ensure synchronized access to them, while also considering the overall implementation efficiency. To illustrate this with a concrete example, let's assume we have a binary tree. When inserting an element into such a tree, we first check if the node where we want to insert has a left child. If it doesn't, the new child node will be inserted on the left; otherwise, it will be inserted on the right:

if (node.left == null)
    node.left = child;
else
    node.right = child;

When multiple threads act upon a binary tree, concurrency issues can arise during insertion. Such a scenario can occur when two threads simultaneously try to insert different values into the same node in the tree:

T0	T1
Check if there is a left child	Check if there is a left child
The condition is true, enters the first branch	The condition is true, enters the first branch
Insert the node on the left
	Insert the node on the left → overwrites T0's value

In this case, it would be correct for one thread to insert on the left, and the other to insert on the right. One solution is to use a lock for the node insertion operation. If we use a global lock (for the entire tree), two threads cannot insert child nodes at the same time for two different parent nodes. For this reason, it would be more efficient to have a lock for each node.