5,350
edits
Parallel Algorithms: Difference between revisions
→2-3 tree
| Line 236: | Line 236: | ||
* ''delete(a)'' | * ''delete(a)'' | ||
====Serial Algorithms==== | |||
* Deletion: discard(a) | |||
** Delete connection between a and parent of a | |||
** If parent has 1 child | |||
*** If parent's sibling has 2 children, move child to sibling and discard(parent) | |||
*** If parent's sibling has 3 children, take one child from sibling | |||
====Parallel Algorithm==== | |||
Assume concurrent read model | 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: 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>. | ** 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> | ** 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. | ** Time is <math>O(\log k \log n)</math> using <math>k</math> processors. | ||