5,337
edits
Parallel Algorithms: Difference between revisions
→2-3 trees; Technique: Pipelining
| Line 232: | Line 232: | ||
* ''insert(a)'' | * ''insert(a)'' | ||
* ''delete(a)'' | * ''delete(a)'' | ||
Assume concurrent read model | |||
* Insert: Suppose you want to insert sorted elements <math>c_1,...,c_k</math> into a tree with n elements. | |||
** Insert element <math>c_{k/2}</math>. | |||
** Then insert in parallel <math>(c_1,...,c_{k/2-1}</math> and <math>(c_{k/2+1},...,c_k)</math> | |||
** Time is <math>O(\log k \log n)</math> using <math>k</math> processors. | |||
==Resources== | ==Resources== | ||