Editing Red–black tree (section)

==== Join-based ====
This approach can be applied to every sorted sequence data structure that supports efficient join- and split-operations.<ref>{{cite book
 | last=Sanders
 | first=Peter
 | editor1-last=Mehlhorn
 | editor1-first=Kurt
 | editor2-last=Dietzfelbinger
 | editor2-first=Martin
 | editor3-last=Dementiev
 | editor3-first=Roman
 | year=2019
 | title=Sequential and Parallel Algorithms and Data Structures : The Basic Toolbox
 | series=Springer eBooks
 | location=Cham
 | publisher=Springer
 | pages=252–253
 | isbn=9783030252090
| doi=10.1007/978-3-030-25209-0
 | s2cid=201692657
 }}</ref>
The general idea is to split {{mvar|I}} and {{mvar|T}} in multiple parts and perform the insertions on these parts in parallel.

# First the bulk {{mvar|I}} of elements to insert must be sorted.
# After that, the algorithm splits {{mvar|I}} into <math>k \in \mathbb{N}^+</math> parts <math>\langle I_1, \cdots, I_k \rangle</math> of about equal sizes.
# Next the tree {{mvar|T}} must be split into {{mvar|k}} parts <math>\langle T_1, \cdots, T_k \rangle</math> in a way, so that for every <math>j \in \mathbb{N}^+ | \, 1 \leq j < k</math> following constraints hold:
##<math>\text{last}(I_j) < \text{first}(T_{j + 1})</math>
## <math>\text{last}(T_j) < \text{first}(I_{j + 1})</math>
# Now the algorithm inserts each element of <math>I_j</math> into <math>T_j</math> sequentially. This step must be performed for every {{mvar|j}}, which can be done by up to {{mvar|k}} processors in parallel.
# Finally, the resulting trees will be joined to form the final result of the entire operation.

Note that in Step 3 the constraints for splitting {{mvar|I}} assure that in Step 5 the trees can be joined again and the resulting sequence is sorted.
<gallery widths="400px" heights="250px" perrow="2">
BulkInsert JoinBased InitialTree.svg|initial tree
BulkInsert JoinBased SplitTree.svg|split I and T
BulkInsert JoinBased SplitTreeInserted.svg|insert into the split T
BulkInsert JoinBased JoinedTree.svg|join T
</gallery>

The pseudo code shows a simple divide-and-conquer implementation of the join-based algorithm for bulk-insert.
Both recursive calls can be executed in parallel.
The join operation used here differs from the version explained in this article, instead [[Join-based tree algorithms#Join2|join2]] is used, which misses the second parameter k.

 '''bulkInsert'''(T, I, k):
     I.sort()
     bulklInsertRec(T, I, k)
 
 '''bulkInsertRec'''(T, I, k):
     '''if''' k = 1:
         '''forall''' e '''in''' I: T.insert(e)
     '''else'''
         m := ⌊size(I) / 2⌋
         (T<sub>1</sub>, _, T<sub>2</sub>) := split(T, I[m])
         bulkInsertRec(T<sub>1</sub>, I[0 .. m], ⌈k / 2⌉)
             || bulkInsertRec(T<sub>2</sub>, I[m + 1 .. size(I) - 1], ⌊k / 2⌋)
         T ← join2(T<sub>1</sub>, T<sub>2</sub>)

===== Execution time =====
Sorting {{mvar|I}} is not considered in this analysis.
:{| 
|-
| #recursion levels || <math>\in O(\log k)</math>
|-
| T(split) + T(join) || <math>\in O(\log |T|)</math>
|-
| insertions per thread || <math>\in O\left(\frac{|I|}{k}\right)</math>
|-
| T(insert) || <math>\in O(\log |T|)</math>
|-
| {{nowrap|1='''T(bulkInsert) with {{mvar|k}} = #processors'''}} || <math>\in O\left(\log k \log |T| + \frac{|I|}{k} \log |T|\right)</math>
|}
This can be improved by using parallel algorithms for splitting and joining.
In this case the execution time is <math>\in O\left(\log |T| + \frac{|I|}{k} \log |T|\right)</math>.<ref>{{cite book
 | last1=Akhremtsev | first1=Yaroslav
 | last2=Sanders | first2=Peter
 | title=2016 IEEE 23rd International Conference on High Performance Computing (HiPC)
 | chapter=Fast Parallel Operations on Search Trees
 | pages=291–300
 | year=2016
 | isbn=978-1-5090-5411-4
 | arxiv=1510.05433
 | doi=10.1109/HiPC.2016.042
 }}</ref>

===== Work =====
:{| 
|-
| #splits, #joins || <math>\in O(k)</math>
|-
| W(split) + W(join) || <math>\in O(\log |T|)</math>
|-
| #insertions || <math>\in O(|I|)</math>
|-
| W(insert) || <math>\in O(\log |T|)</math>
|-
| '''W(bulkInsert)''' || <math>\in O(k \log |T| + |I| \log |T|)</math>
|}