Concurrent Implementation of Red Black Trees

Abstract

We offer Red Black Tree concurrent algorithms that logical ordering information is clearly maintained in the data structure, allowing clear separation from its physical tree architecture. With the property that an item only belongs to the tree if and only if it is an endpoint of an interval, we represent logical ordering using intervals. Thus, we are able to design lookup operations that are quick, simple, and devoid of synchronization. In this paper we implemented our Red Black Tree using Logical Ordering and evaluated the running time for insertion, Deletion and Contains Operations.