Zip Trees: A New Approach to Concurrent Binary Search Trees

Abstract

One of the most fundamental tasks in computing is the storage and retrieval of data. For this reason, binary search trees are one of the most fundamental algorithms in computer science. In the last few years, the ever-present need for data access has been accompanied by a need for multiple processors to access data concurrently. Concurrent programming is a deeply theoretical field of study focused on developing algorithms and techniques for managing this increased interest in parallel processing. Binary search trees typically present three main difficulties in a concurrent environment: their reliance on global information and balance, their use of read and write operations which traverse the tree in different directions, and the amplified cost of changing pointers near the root (where many threads must traverese). We develop a new algorithm known as a Zip Tree which overcomes all three challenges by maintaining balance based solely on locally stored random values, updating the tree structure from the top down, and inserting at a height constant in expectation within the tree.