Concurrent Localized Wait-Free Operations on a Red Black Tree

A red-black tree is a type of self-balancing binary search tree. Some wait-free algorithms have been proposed for concurrently accessing and modifying a red-black tree from multiple threads in shared memory systems. Most algorithms presented utilize the concept of a window , and are entirely top-down implementations. Top-down algorithms like these have to operate on large portions of the tree, and operations on nodes that would otherwise not overlap at all still have to compete with and help one another. A wait-free framework is proposed for obtaining ownership of small portions of the tree at a time in a bottom-up manner. This approach allows operations interested in completely disparate portions of the tree to execute entirely uninhibited. Insert and search operations on a red-black tree are shown, and the different use cases explained