RB Tree

The Red-Black tree is a self-balancing binary tree data structure. Each node, aside from the key and value, are also parameterized by a colour, red or black, hence the name of the data structure. The colours of a Red-Black tree node usually must follow the following rules:

• The root of the tree must be black.
• The colour of leaves (null children) is black.
• The children of a red node must be black (no 2 directly connected red node possible).
• The path from the root to any leaf must have the same number of black nodes / black height.

The above properties are maintained by changing colours and rotating the tree recursively for each insertion. The rebalancing algorithm itself works by treating various cases exhaustively. Any freshly inserted node is red, and recolouring occurs when rebalancing.

Time complexity for sequential operations

• Insertion: amortized O(log n), worst case O(log n).
• Search: amortized O(log n), worst case O(log n).

Sequential operations

Provided are the sequential operations to create a new tree, insert elements, and search for elements.

Batch parallel implementation

To implement a batch parallel version of the Red-Black tree, we need a join and a split function:

• join lt n rt: this function joins a left Red-Black tree lt, a node n with some key k, and a right Red-Black tree rt. The end result should be a balanced Red-Black tree. This function assumes all keys in lt are strictly less than k, and all keys in rt are strictly greater than k. Under these constraints, join has O(log n) complexity (where n is the combined number of nodes of both trees).
• split t k: this function splits an Red-Black tree t at key k into 2 Red-Black trees, one with all keys less than k and the other with all keys greater than k. If there is a node present with that same key k, that node is returned detached from either tree. The complexity of split is also O(log n).

The proofs for the complexity of these functions are detailed in this paper: https://arxiv.org/abs/1602.02120. Unit tests for these two functions are also provided and can be run with dune runtest.

To make these functions possible, we also need to make some modifications to the classical sequential Red-Black tree structure, namely:

• Each node must store its own black height. This requires updating with each rebalancing of the tree.
• The root can be red, to facilitate splitting and joining without potentially resorting to recolouring the tree extensively.

Nonetheless, these changes do not (probably) impact the logarithmic time complexity of sequential tree operations.