[Parallel Algo.] 10. Balanced Binary Tree

Parallel Algorithm

10. Balanced Binary Tree

Main idea

      [1] Build a balanced binary tree on the input (or output) elements
           用input以balanced binary tree的方式建起一棵樹

      [2] Traverse the tree forward or backward to and from the root
           從root或往root尋訪整棵樹來找出答案

Example: Summing 

Input: A[1...n] = {3, 7, 8, 3, 9, 2, 3, 7} (n=8) 
Output: A[1] + A[2] + ... + A[n]

[Pseudo code]

for k = m 􏰏 1 step –1 to 0 do
      for i, 1 􏰁 i 􏰁 2k, pardo A[i] = A[2i 􏰏1] + A[2i]