Deletion Without Rebalancing in Non-Blocking Self-Balancing Binary Search Trees

Abstract

We present a provably linearizable and lock-free relaxed AVL tree called the non- blocking ravl tree. At any time, the height of a non-blocking ravl tree is bounded by logφ(2m) + c, where φ is the golden ratio, m is the total number of successful INSERT operations performed so far and c is the number of active concurrent processes performing INSERT operations at this time. The most signi cant feature of the non-blocking ravl tree is that it does not rebalance itself after DELETE operations. Compared to other self-balancing Binary Search Trees (BSTs), which typically intro- duce a large number of rebalancing cases after DELETE operations, the non-blocking ravl tree has much fewer rebalancing cases, which makes it much simpler to imple- ment in practice. Our experimental studies show that our solution is potentially the best candidate for many real-world applications.