5,323
edits
Parallel Algorithms: Difference between revisions
→Parallel Rake
| Line 530: | Line 530: | ||
;Step 2: | ;Step 2: | ||
*Let <math>S_1</math> be nodes in <math>S</math> whose parents are not in <math>S</math>. | * Let <math>S_1</math> be nodes in <math>S</math> whose parents are not in <math>S</math>. | ||
* Let <math>L_1</math> be leaves in <math>L</math> whose parents are in <math>S_1</math>. | |||
* Apply parallel rakes to leaves in <math>L_1</math>, unless the parent is the root. | |||
* Apply parallel rakes to leaves in <math>L - L_1</math>, unless the parent is the root. | |||
*Apply parallel rakes to leaves in <math>L_1</math>, unless the parent is the root. | * Repeat Step 2 until the tree is a 3-node binary tree | ||
*Apply parallel rakes to leaves in <math>L - L_1</math>, unless the parent is the root. | |||
*Repeat Step 2 until the tree is a 3-node binary tree | |||
===Complexity=== | ===Complexity=== | ||