Editing Red–black tree (section)

==== Pipelining ====
Another method of parallelizing bulk operations is to use a [[Pipeline (computing)|pipelining]] approach.<ref>{{cite book
 | title=An introduction to parallel algorithms
 | last=Jájá
 | first=Joseph
 | location=Reading, Mass. [u.a.]
 | publisher=Addison-Wesley
 | year=1992
 | isbn=0201548569
 | url=http://zbmath.org/?q=an:0781.68009
 | pages=65–70
| zbl=0781.68009
 }}</ref>
This can be done by breaking the task of processing a basic operation up into a sequence of subtasks.
For multiple basic operations the subtasks can be processed in parallel by assigning each subtask to a separate processor.

# First the bulk {{mvar|I}} of elements to insert must be sorted.
# For each element in {{mvar|I}} the algorithm locates the according insertion position in {{mvar|T}}. This can be done in parallel for each element <math>\in I</math> since {{mvar|T}} won't be mutated in this process. Now {{mvar|I}} must be divided into subsequences {{mvar|S}} according to the insertion position of each element. For example <math>s_{n, \mathit{left}}</math> is the subsequence of {{mvar|I}} that contains the elements whose insertion position would be to the left of node {{mvar|n}}.
# The middle element <math>m_{n, \mathit{dir}}</math> of every subsequence <math>s_{n, \mathit{dir}}</math> will be inserted into {{mvar|T}} as a new node <math>n'</math>. This can be done in parallel for each <math>m_{n, \mathit{dir}}</math> since by definition the insertion position of each <math>m_{n, \mathit{dir}}</math> is unique. If <math>s_{n, \mathit{dir}}</math> contains elements to the left or to the right of <math>m_{n, \mathit{dir}}</math>, those will be contained in a new set of subsequences {{mvar|S}} as <math>s_{n', \mathit{left}}</math> or <math>s_{n', \mathit{right}}</math>.
# Now {{mvar|T}} possibly contains up to two consecutive red nodes at the end of the paths form the root to the leaves, which needs to be repaired. Note that, while repairing, the insertion position of elements <math>\in S</math> have to be updated, if the corresponding nodes are affected by rotations.
#* If two nodes have different nearest black ancestors, they can be repaired in parallel. Since at most four nodes can have the same nearest black ancestor, the nodes at the lowest level can be repaired in a constant number of parallel steps.
#* This step will be applied successively to the black levels above until {{mvar|T}} is fully repaired.
# The steps 3 to 5 will be repeated on the new subsequences until {{mvar|S}} is empty. At this point every element <math>\in I</math> has been inserted. Each application of these steps is called a ''stage''. Since the length of the subsequences in {{mvar|S}} is <math>\in O(|I|)</math> and in every stage the subsequences are being cut in half, the number of stages is <math>\in O(\log |I|)</math>.
#* Since all stages move up the black levels of the tree, they can be parallelised in a pipeline. Once a stage has finished processing one black level, the next stage is able to move up and continue at that level.
<gallery perrow="3" widths="250px" heights="180px">
BulkInsert Pipelining InitialTree.svg|Initial tree
BulkInsert Pipelining InsertPositions.svg|Find insert positions
BulkInsert Pipelining Stage1Insert.svg|Stage 1 inserts elements
BulkInsert Pipelining Stage1Repair.svg|Stage 1 begins to repair nodes
BulkInsert Pipelining Stage2Insert.svg|Stage 2 inserts elements
BulkInsert Pipelining Stage2Repair.svg|Stage 2 begins to repair nodes
BulkInsert Pipelining Stage3Insert.svg|Stage 3 inserts elements
BulkInsert Pipelining Stage3Repair1.svg|Stage 3 begins to repair nodes
BulkInsert Pipelining Stage3Repair2.svg|Stage 3 continues to repair nodes
</gallery>

===== Execution time =====
Sorting {{mvar|I}} is not considered in this analysis.
Also, <math>|I|</math> is assumed to be smaller than <math>|T|</math>, otherwise it would be more efficient to construct the resulting tree from scratch.
:{|
|-
| T(find insert position) || <math>\in O(\log |T|)</math>
|-
| #stages || <math>\in O(\log |I|)</math>
|-
| T(insert) + T(repair) || <math>\in O(\log |T|)</math>
|- style="vertical-align:top"
| '''T(bulkInsert) with <math>|I|</math> ~ #processors''' || <math>\in O(\log |I| + 2 \cdot \log |T|)</math><br/><math> = O(\log |T|)</math>
|}

===== Work =====
:{|
|-
| W(find insert positions) || <math>\in O(|I| \log |T|)</math>
|-
| #insertions, #repairs || <math>\in O(|I|)</math>
|-
| W(insert) + W(repair) || <math>\in O(\log |T|)</math>
|- style="vertical-align:top"
| '''W(bulkInsert)''' || <math>\in O(2 \cdot |I| \log |T|)</math><br/><math>= O(|I| \log |T|)</math>
|}