Concurrent Binary Search Trees Supporting Split and Join

We consider the problem of maintaining a forest of Binary Search Trees under Split and Join operations, in a concurrent setting. We propose a lock-based approach, where threads work in a bottom-up fashion, combining different Split operations as they traverse up the tree to ensure good performance. This work stands as an intermediate step for solving the dynamicity problem in trees, where the goal is to maintain a forest of trees under edge insertions and deletions, while answering queries (e.g. node of minimum weight) efficiently.