Editing Red–black tree (section)

== Set operations and bulk operations ==
In addition to the single-element insert, delete and lookup operations, several set operations have been defined on {{nowrap|red–black trees:}} [[Union (set theory)|union]], [[Intersection (set theory)|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.<ref name="join-based">{{cite book
 | last1=Blelloch | first1=Guy E. | author-link1=Guy Blelloch
 | last2=Ferizovic | first2=Daniel
 | last3=Sun | first3=Yihan | author-link3=Yihan Sun
 | doi=10.1145/2935764.2935768
 | isbn=978-1-4503-4210-0
 | pages=253–264
 | publisher=ACM
 | title=Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures
 | chapter=Just Join for Parallel Ordered Sets | year=2016 | arxiv=1602.02120
 | s2cid=2897793 | contribution-url=http://www.cs.cmu.edu/~yihans/papers/join.pdf
 }}.</ref> 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'''.

* ''Join'': The function ''Join'' is on two red–black trees {{math|''t''<sub>1</sub>}} and {{math|''t''<sub>2</sub>}} and a key {{mvar|k}}, where {{math|''t''<sub>1</sub> < ''k'' < ''t''<sub>2</sub>}}, i.e. all keys in {{math|''t''<sub>1</sub>}} are less than {{mvar|k}}, and all keys in {{math|''t''<sub>2</sub>}} are greater than {{mvar|k}}. It returns a tree containing all elements in {{math|''t''<sub>1</sub>}}, {{math|''t''<sub>2</sub>}} also as {{mvar|k}}.
: If the two trees have the same black height, ''Join'' simply creates a new node with left subtree {{math|''t''<sub>1</sub>}}, root {{mvar|k}} and right subtree {{math|''t''<sub>2</sub>}}. If both {{math|''t''<sub>1</sub>}} and {{math|''t''<sub>2</sub>}} have black root, set {{mvar|k}} to be red. Otherwise {{mvar|k}} is set black. 
: If the black heights are unequal, suppose that {{math|''t''<sub>1</sub>}} has larger black height than {{math|''t''<sub>2</sub>}} (the other case is symmetric). ''Join'' follows the right spine of {{math|''t''<sub>1</sub>}} until a black node {{mvar|c}}, which is balanced with {{math|''t''<sub>2</sub>}}. At this point a new node with left child {{mvar|c}}, root {{mvar|k}} (set to be red) and right child {{math|''t''<sub>2</sub>}} is created to replace c. The new node may invalidate the red–black invariant because at most three red nodes can appear in a row. This can be fixed with a double rotation. If double red issue propagates to the root, the root is then set to be black, restoring the properties. The cost of this function is the difference of the black heights between the two input trees.

* ''Split'': To split a red–black tree into two smaller trees, those smaller than key {{mvar|x}}, and those larger than key {{mvar|x}}, first draw a path from the root by inserting {{mvar|x}} into the red–black tree. After this insertion, all values less than {{mvar|x}} will be found on the left of the path, and all values greater than {{mvar|x}} will be found on the right. By applying ''Join'', all the subtrees on the left side are merged bottom-up using keys on the path as intermediate nodes from bottom to top to form the left tree, and the right part is symmetric.
: For some applications, ''Split'' also returns a boolean value denoting if {{mvar|x}} appears in the tree. The cost of ''Split'' is <math>O(\log n) ,</math> order of the height of the tree. This algorithm actually has nothing to do with any special properties of a red–black tree, and may be used on any tree with a ''join'' operation, such as an [[AVL tree]].

The join algorithm is as follows:

 '''function''' joinRightRB(T<sub>L</sub>, k, T<sub>R</sub>):
     '''if''' (T<sub>L</sub>.color=black) and (T<sub>L</sub>.blackHeight=T<sub>R</sub>.blackHeight):
         '''return''' Node(T<sub>L</sub>,⟨k,red⟩,T<sub>R</sub>)
     T'=Node(T<sub>L</sub>.left,⟨T<sub>L</sub>.key,T<sub>L</sub>.color⟩,joinRightRB(T<sub>L</sub>.right,k,T<sub>R</sub>))
     '''if''' (T<sub>L</sub>.color=black) and (T'.right.color=T'.right.right.color=red):
         T'.right.right.color=black;
         '''return''' rotateLeft(T')
     '''return''' T' /* T{{single+single}}[recte T'] */
 
 '''function''' joinLeftRB(T<sub>L</sub>, k, T<sub>R</sub>):
   /* symmetric to joinRightRB */
 
 '''function''' join(T<sub>L</sub>, k, T<sub>R</sub>):
     '''if''' T<sub>L</sub>.blackHeight>T<sub>R</sub>.blackHeight:
         T'=joinRightRB(T<sub>L</sub>,k,T<sub>R</sub>)
         '''if''' (T'.color=red) and (T'.right.color=red):
             T'.color=black
         '''return''' T'
     '''if''' T<sub>R</sub>.blackHeight>T<sub>L</sub>.blackHeight:
         /* symmetric */
     '''if''' (T<sub>L</sub>.color=black) and (T<sub>R</sub>.color=black):
         '''return''' Node(T<sub>L</sub>,⟨k,red⟩,T<sub>R</sub>)
     '''return''' Node(T<sub>L</sub>,⟨k,black⟩,T<sub>R</sub>)

The split algorithm is as follows:

 '''function''' split(T, k):
     '''if''' (T = NULL) '''return''' (NULL, false, NULL)
     '''if''' (k = T.key) '''return''' (T.left, true, T.right)
     '''if''' (k < T.key):
         (L',b,R') = split(T.left, k)
         '''return''' (L',b,join(R',T.key,T.right))
     (L',b,R') = split(T.right, k)
     '''return''' (join(T.left,T.key,L'),b,T.right)

The union of two red–black trees {{math|''t''<sub>1</sub>}} and {{math|''t''<sub>2</sub>}} representing sets {{mvar|A}} and {{mvar|B}}, is a red–black tree {{mvar|t}} that represents {{math|''A'' ∪ ''B''}}. The following recursive function computes this union:

 '''function''' union(t<sub>1</sub>, t<sub>2</sub>):
     '''if''' t<sub>1</sub> = NULL '''return''' t<sub>2</sub>
     '''if''' t<sub>2</sub> = NULL '''return''' t<sub>1</sub>
     (L<sub>1</sub>,b,R<sub>1</sub>)=split(t<sub>1</sub>,t<sub>2</sub>.key)
     proc1='''start''':
         T<sub>L</sub>=union(L<sub>1</sub>,t<sub>2</sub>.left)
     proc2='''start''':
         T<sub>R</sub>=union(R<sub>1</sub>,t<sub>2</sub>.right)
     '''wait all''' proc1,proc2
     '''return''' join(T<sub>L</sub>, t<sub>2</sub>.key, T<sub>R</sub>)

Here, ''split'' is presumed to return two trees: one holding the keys less its input key, one holding the greater keys. (The algorithm is [[persistent data structure|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 tree algorithms|"join-based" implementation]].

The complexity of each of union, intersection and difference is <math>O\left(m \log \left({n\over m}+1\right)\right)</math> for two red–black trees of sizes <math>m</math> and <math>n(\ge m)</math>. 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 [[parallel programming|in parallel]] with a [[Analysis of parallel algorithms|parallel depth]] <math>O(\log m \log n)</math>.<ref name="join-based"/> When <math>m=1</math>, 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.