Li, Mengdu2016-05-042016-05-042016-05-04http://hdl.handle.net/10222/71623We 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.enconcurrent data structurenon-blockingself-balancing binary search treerelaxed AVL treeamortized complexity