processor. First the bulk of elements to insert must be sorted. For each element in the algorithm locates the according insertion position in . This can be done in parallel for each element since won’t be mutated in this process. Now must be divided into subsequences according to the insertion position of each element. For example is the subsequence of that contains the elements whose insertion position would be to the left of node . The middle element of every subsequence will be inserted into as a new node . This can be done in parallel for each since by definition the insertion position of each is unique. If contains elements to the left or to the right of , those will be contained in a new set of subsequences as or . Now 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 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 is fully repaired. The steps 3 to 5 will be repeated on the new subsequences until is empty. At this point every element has been inserted. Each application of these steps is called a stage. Since the length of the subsequences in is and in every stage the subsequences are being cut in half, the number of stages is .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. Execution time Sorting is not considered in this analysis. Also, is assumed to be smaller than , otherwise it would be more efficient to construct the resulting tree from scratch. Work Popular culture A red–black tree was referenced correctly in an episode of Missing as noted by Robert Sedgewick in one of his lectures: See also List of data structures Tree data structure Tree rotation AA tree, a variation