linguistic:paraphrasing, linguistic:translation, structural:reformatting, linguistic:voice_change
Set operations and bulk operations

In addition to the single-element insert, delete and lookup operations, several set operations have been defined on red–black trees: union, intersection and set difference. Then fast bulk operations on insertions or deletions can be implemented based on these set functions. These set operations rely on two helper operations, Split and Join. With the new operations, the implementation of red–black trees can be more efficient and highly-parallelizable. In order to achieve its time complexities this implementation requires that the root is allowed to be either red or black, and that every node stores its own black height.

The join algorithm is as follows:

The split algorithm is as follows:

The union of two red–black trees t and t representing sets A and B, is a red–black tree t that represents A ∪ B. The following recursive function computes this union:

Here, split is presumed to return two trees: one holding the keys less its input key, one holding the greater keys. (The algorithm is non-destructive, but an in-place destructive version exists also.)

The algorithm for intersection or difference is similar, but requires the Join2 helper routine that is the same as Join but without the middle key. Based on the new functions for union, intersection or difference, either one key or multiple keys can be inserted to or deleted from the red–black tree. Since Split calls Join but does not deal with the balancing criteria of red–black trees directly, such an implementation is usually called the "join-based" implementation.

The complexity of each of union, intersection and difference is O (m log (n m + 1)) {\displaystyle O\left(m\log \left({n \over m}+1\right)\right)} for two red–black trees of sizes m {\displaystyle m} and n (≥ m) {\displaystyle n(\geq m)}. This complexity is optimal in terms of the number of comparisons. More importantly, since the recursive calls to union, intersection or difference are independent of each other, they can be executed in parallel with a parallel depth O (log m log n) {\displaystyle O(\log m\log n)}. When m = 1 {\displaystyle m=1}, the join-based implementation has the same computational directed acyclic graph (DAG) as single-element insertion and deletion if the root of the larger tree is used to split the smaller tree.