Derivation of a 1xiaally Parallel AlgoriLba f.r flalancing liury Search Trees Abha Moitra and * 5. Sitharama Iyengar TR 84-638 September 1984 Department of Computer Science Cornell University Ithaca1 New York 14853 Department of Computer Science. Louisiana State University. Baton Rouge. Louisiana 70803 Derivation of a Maximally Parallel Algorithm for Balancing Binary Search Trees Abha Moitra Department of Computer Science Cornell University Ithaca, NY 14853 S. Sitharama I?ngar Department of Computer Science Louisiana State University Baton Rouge, LA 70803 ABSThACT A recent trend in program methodologies is to derive efficient parallel programs from sequential programs. This paper explores the question of transforming a sequential algorithm into an efficient parallel algorithm by considering the problem of balancing binary search trees. The derivation of the parallel algorithm makes use of stepwise refinement. We first derive a new iterative balancing algorithm that exploits the similarity of pointer restructuring required at all the nodes at the same level. From this we derive a parallel algorithm that has time complexity 0(1) on an N-processor configuration. This achieves the theoretical limit of speed-up possible in a multi-processor configuration. 1. INTRODUCTION In recent years, researchers have sought to transform sequential programs for effi- cient execution on parallel machines. Such a transformation depends on the degree of parallelism sought and the model of parallel computation. The most common model of parallel computation is the shared memory model (SMM), which has the following characteristics 1. There are M processing elements (PEs) or processors. These are indexed 1, 2,.., M and the jtA FE is referenced as Pj. Each FE has the capability of perform- ing all the standard arithmetic and logic operations. Each FE also knows its own index. -2- 2. There is a common memory that is shared among all the PEs. All FE's can read and write into this memory but if two or more FEs attempt to read from (write to) the same memory location, a read (write) conflict occurs. 3. The PEs are synchronized and operate under the control of a single instruction stream. 4. An enable/disable mask can be used to select any arbitrary subset of PEs to perform an instruction; all the other PEs remain idle. All enabled PEs execute the same instruction. A number of parallel algorithms have been developed for this model. For example, various matrix and graph problems have been investigated by Agerwala and Lint [1], Mjomandi and Corneil [2], Csanky [5J and Hirschberg [9], sorting problems have been studied by Hirschberg 110], Muller and Preparata [13,15]. Evaluation of poly- nomials has been considered by Munro and Paterson [14], arithmetic expression evaluation has been studied by Brent [3]. The generation of postfix form of arith- metic expressions and scheduling algorithms have been studied by Dekel and Sahni [7,8]. A useful metric for analyzing parallel algorithms is to compute the effectiveness of processor utilization (EPU). For any problem S with a parallel algorithm T, this is defined as follows: EPU(&, T) = complexityofthefastestsequentialalgorithmfor S number of PEs used by T * complexity of T For any problem 0 < EPU < 1, and EPU = 1 corresponds to the theoretical limit of speed-up possible. Another characteristic of a parallel algorithm is whether it can be effectively .3- "scaled" in terms of the number of processors being utilized. Typically, we would like a parallel algorithm to make effective use of all the available processors instead of being dependent on some particular number of processors that it can handle effi- ciently. In this paper we consider the transformation of a recursive algorithm into an effi- cient parallel algorithm for the SMM model. Fig. 1 gives a general outline of how this can be achieved. iterative algorithm recursive algorithm parallel algorithm unravel recursion and assign computation to the processors Fig. 1. Transformation process. speed up by 1. storing duplicate information 2. reorganising computation In this paper we investigate the problem of balancing binary search trees. This is usually accomplished by recursive algorithms. We illustrate all the steps outlined in Fig. 1 by deriving a parallel balancing algorithm that requires only constant running time on an fl-processor configuration, thus achieving the m?imum speed-up -4- possible. The second goal of this paper is to motivate the derivation of the iterative as well as the parallel algorithms and we do this by following the stepwise refinement tech- nique advocated by Wirth [161. Both the iterative balancing algorithm and the parallel balancing algorithm are developed by successive refinement from one ver- sion to another. This leads to considerable similarity between the algorithms developed. The paper is organized as follows. In Section 2, we introduce a recursive algorithm for balancing a binary search tree. In Section 3, we derive a new iterative algorithm for growing balanced binary search trees. In Section 4, we derive the parallel alg? rithm for balancing binary search trees. In Section 5 we make some general com- ments on the transformation process. 2. BALANCING BINARY SEARCH TREES Binary search trees provide a method of data organization that is both flexible and efficient : records are retrieved from binary search trees in an average time propor- tional to log N (all logarithms in this paper will be to base 2), where N is the number of nodes in the tree. The task of balancing a binary search tree is to adjust the left and right pointers of the nodes in the tree so that the height of the tree is minimized; the search time will approach ?log N 1. AIgorithms that dynamically balance tree structure during insertion or deletion of nodes are described in detail by Knuth [11]. An algorithm due to Martin and Ness [12] r?organizes a tree with n nodes by repetitively dividing n by 2 and using the -5- result as a guideline for stepping through the framework of a perfectly balanced tree, i.e., for each node, the number of nodes in its left subtree and right subtree differ by 1 at most. An Inorder traversal is carried out concurrently to provide rela- tive node positions for the pointer-restructuring procedure which fits them into proper places in the balanced tree structure. In this algorithm, a stack is required to save pointers during traversal. A balancing algorithm that needs no extra storage has been given in Day (61 where the input tree is right-threaded with nega- tive backtrack pointers to allow stackless traversal. Recently Chang and Iyengar (?1 presented an algorithm (hereafter referred to as CI algorithm) to balance binary search trees in 0(N) time. The algorithm can be sum- marized as follows. Phase 1: Traverse the tree in Inorder, storing pointers in a array LINK. Phase 2: Use a procedure GROW(LOW:HIGH) to recursively construct a balanced binary search tree from the nodes LINK(LOW:HIGH). The interesting aspect of the CI algorithm is that the left and right subtrees are grown simultaneously from the root. In particular, if the root is linked by the M'th cell in the array LINK, then, for all K < M, if LINK(K) has LINK(jl) and LINK(j2) as its left and right son, then LINK(K+ M) has LINK(jl+M) and LINK(j2+ M) as its left and right son. This is referred to as `folding' with a fold- ing factor M. Calculation of M and other details can be found in 14]- This algorithm is recursive and, as indicated in Fig. 1, we could either try to first derive an iterative algorithm and then a parallel algorithm from it, or go directly from the recursive algorithm to a parallel algorithm. -6- In fact, we will be able to transform the recursive algorithm corresponding to Phase 1, which we call the Traversing AIgorithm, directly into a parallel algorithm by keeping additional information with the binary search tree. The recursive algorithm corresponding to Phase 2, which we call the Growing AIgorithm, will be transformed into an iterative algorithm and then into a parallel algorithm by reorganising the computation appropriately. To simplify the following presentation we will first con- centrate on deriving a parallel algorithm for Phase 2 and after that we will consider deriving a parallel algorithm for Phase 1. 3. ITERATWE GROWING ALGORITHM Phase 1 of balancing a binary search tree can be achieved by the recursive alg? rithm Al. AIgorithm Al : Recursive Inorder traversal for storing the pointers in the array LINK. procedure MAIN (T) 1/ The tree with root T is to be traversed // declare T, LINK() procedure TRAVERSE (P,N) if P = null then return TRAVERSE (LSON(P),N) 1/ LSON(P) is the pointer to the left son of P /1 N := N + 1 LINK(N) P TRAVERSE (RSON(P),N) 1/ RSON(P) is the pointer to the right son of P II end TRAVERSE TRAVERSE (T,o) end MAIN -7- We will now develop an iterative growing algorithm for Phase 2 of balancing binary search trees. In a recursive growing algorithm for Phase 2, a contiguous section of the array LINK is converted into a balanced binary search tree by identifying the middle element as the root and then the two subproblems corresponding to its left and right subtrees are solved recursively. In order to translate this into an iterative algorithm we should be able to identify the final position (in the balanced binary search tree) for any node/cell in the array LINK. There is no straightforward way of doing this and so in the spirit of stepwise refinement we will first consider a simpler problem. 3.1. Iterative Algorithm ror GrowIng Complete Balanced Binary Trees Let us first restructure a binary tree that has N = 2? - 1 nodes. The resulting bal- anced binary search tree must then be a complete balanced binary search tree and the pointer restructuring required for all the nodes on the same level is similar, as shown by the following two theorems. Definition 1 : In a binary tree T, the 'th node refers to the j'th node from the left on the i `th level, if both exist. 0 Definition 2 : In a complete balanced binary tree T of N nodes let CVALN( < i ,j>) denote the number of nodes with data values less than or equal to the data value of the `th node. 0 Theorem 1 : Consider a complete balanced binary tree T with N = 2? - 1 nodes. -8- If the 'th node exists in T then CVALN() = 2?? + (j-1)*2??+'. Proof: Let us consider a complete balanced balanced binary tree structure T with its nodes labelled by Inorder traversal. The label associated with each node corresponds to the number of nodes with data value less than or equal to its own data value. Thus the 'th node (if it exists) is labelled 2?-' by the Inorder traversal. Further, if node is labelled y then the node on the same level to its immediate right (if it exists) is labelled y + 2?-?+?. It then follows that if the 'th node exists, CVALN() = 2fl-i + (j-1)*2?4+1. 0 Theorem 2: Consider a complete balanced binary tree T with N = - 1 nodes: if the 'th node, i < n, has nodes and as its LSON and RSON respectively then CVALN() = k - 2n-i-1 and CVALN() = k + 2n-i-1 where k = 2?-' + (j-1)*2?4+1 Proof: From Theorem 1 we know that CVALN() = 2?? + (j-1)*2?4+1 We also know that in a complete balanced binary tree the 'th node (i < n) has 'th and 'th nodes as it LSON and RSON respec- tively. So CVALN(< i+ 1,2 *j--H1>) = 2?-('.+ 1) + ((2*j-1)-1)*2??(so++ 1)+ 1 = k - 2n-i-1 CVALN() --H 2n-(i+1) + (2*j?1)*2fl?(i+1)+1 = k + 2n-i-1 0 This means that for balancing a binary search tree with N = - 1 nodes, the node corresponding to the kg th cell in the array LINK will be the node as determined by the equation -9- k = 2?-? + (??1)*2s4+1 (1) Further, if i < n then it will have nodes corresponding to the kl'th and k2'th cell as its LSON and RSON, as determined by the following equations. ki = k --H 2s-i-1 k2 = k + 2n4-1 (2) (3) 3.2. Efficient Sequencing One way of translating this into an algorithm would be to sequence through the array LINK and set up the pointers defined by the above equations. This leads to a slight complication and some inefficiency as it would involve first determining i and j from k in equation (1). This problem can be avoided quite easily by having an algorithm that does not sequence through the array LINK but instead does the necessary computation for all the cells that have corresponding nodes to be posi- tioned on level 1, and then all the cells that have corresponding nodes to be posi- tioned on level 2, and so on. For all the cells with the corresponding nodes to be positioned on level i, the cell with its corresponding node at position will be processed before the node corresponding to the node at position . This would then correspond to determining k, ki and k2 from i and j, which is straightforward. We shall call this efficient sequencing. Based on these observa- tions; a binary search tree with N = - 1 nodes can be balanced as follows. Step 1 Traverse the tree in Inorder, storing the pointers in the array LINK Step 2 : Visit the nodes in increasing level order from left to right, setting up appropriate links to construct a balanced binary search tree. -10 - Step 1 corresponds to AIgorithm Al and Step 2 can be accomplished by Algorithm A2 which is an iterative algorithm. Algorithm A2 : Iterative growing algorithrn where N = 2? 1. Level restructuring is done by visit- ing the nodes from left to right in increasing level order, setting up links to construct a balanced binary tree. procedure C-LEVEL-STRUCT declare I, J, K, DWF, n, N, LINK(1:N), LSON(1:N), RSON(1:N) for I 1 to n do I/for each level // for J 1 to 21-1 do //for all nodes on a level // K := 2n--HI + (J-1) * 2??+ 1 II K = CVALN(), using ec'. (1)/I if odd(K) then //leaves on the highest level // LSON(LINK(K')) := null RsoN(LINK(K')) := null endif if even(K) then I/interior nodes // Ki :--H 2n-I-1 + (2*J - 2) * 2n-I // set up left link, using eq. (2)1/ LsoN(LINK(K)) := LlNK(Ki) K2 :--H 2n-I-1 + (2*J - 1) * 2n-I ?? set up right link, using eq. (3)/I HSON(LINK(K)) := LINK(K2) endif endfor endfor end G?LEVEL-STRUCT The C-I algorithm [4J is based on the folding method in which the similarity of the restructuring for the left and right subtrees of the root was exploited. In Algorithm - 11 - A2 we exploit the similarity of the restructuring for all the nodes on the same level and hence generalize the folding method. A straightforward analysis shows that the time complexity of each of the algorithms Al and A2 is 0(N). 3.3. Iterative Algorithm ror Growing Balanced Binary Trees Algorithm A2 was developed under the assumption that N = 2? - 1. If this condi- tion is not satisfied, then a complete balanced binary search tree cannot be con- structed. For an arbitrary number of nodes there does not exist either a unique route balanced binary search tree (i.e. one in which the length of the longest and the shortest paths from the root to a leaf differs at most by 1) or a unique perfectly bal- anced binary search tree. In the remainder of this paper, a balanced binary tree will correspond to a route balanced binary search tree in which all the leaves of the highest level are located at the leftmost side of the tree, as in Fig. 2 which is ann? tated with VAL value for the corresponding node. Algorithm Al works for any arbitrary binary tree; and we will now show how Algorithm A2 can be modified to construct route balanced binary search trees for an arbitrary number of nodes. 7 2 6 10 14 (b) 15 nodes Fig. 2. Balanced binary trees. (a) 10 nodes - 12 As before, to construct a balanced binary tree, for any arbitrary node in the balanced binary tree we should be able to infer where the node is stored in the array LINK. Definition 3 : Let VALN() denote the number of nodes with data values less than or equal to the data value of the node in a binary tree of size N.(fJ From Definition 2 and 3 it follows that CVAL2.?1() = Consider the balanced binary trees in Fig. 2. Fig. 2a corresponds to a balanced binary tree with 10 nodes and Fig. 2b corresponds to a complete balanced binary tree which is obtained from Fig. 2a by adding 5 nodes. To extend AIgorithi? A2, we must be able to calculate VALN() for arbitrary N. The following theorem relates VALN() and VAL2a?1() where n = ?log(N+ 1)1. Theorem 3: For any balanced tree of N nodes where n = ?log(N+ 1) ? VALN() = min VAL2 1(), [VAL2??1() + N- 5 + 1j/2] where 5 = 2? - 1 - N, which is the minimum number of nodes that can be added to the balanced binary tree to obtain a completely balanced binary tree. Proof: Let L denote the number of leaves that precede the node (in Inorder traversal) in a balanced binary tree of size 2" - 1. Then the following recurrence relation is satisfied L = L + 2*L j > 2 L = 2n-i-1 This recurrence can be solved to obtain - 13 - L = (2*j .1)*2fl4-1 In a completely balanced binary tree of size 2?-1 we know that VAL2n?1() = 2fl-i + (j.1)*2S???I Now in any balanced binary tree of size N we know that 5 leaves at the rightmost side of the tree at the highest level are missing. If some of the leaves that precede the node (in Inorder traversal) in a binary tree of size 2? - 1 are missing in a balanced binary tree of size N then VAL??l() should be adjusted accordingly to obtain VALN( < i ,i>). That is ifS <2??1-L then VALN() = VAL2.4() else VALN() = VAL2??1()- iS + L - 2?-' 1 The above equation can be simplified to VALN() = min [VAL??l(), [VAL2n 1() - 5 - (2*j 1)*2??-' + 2??1 1 = min [VAL2??1(), (VALr4() + N - 5 + 11/2 1 (4) 0 This theorem gives us a method for determining which location in the array corresponds to the `th node in the balanced binary tree. The only remaining thing to be done to develop a general iterative growing algorithm is to be able to determine under what conditions the 'th node has null LSON/RSON pointers. A node has null pointers as specified below. 1. All the leaves on the highest level have null LSON and RSON pointers. 'th node is a leaf on the highest level if CVAL22?1() is an odd value and CVAL214() = VALN(). - 14 - 2. On level fl-i, the rightmost ts/2J nodes have null RSON pointers and the rightmost L(s+ i)/2J nodes have null LSON pointers. If node is on level fl--Hi then both CVAL2. 1() and CVAL2.4() have odd values. Further, if CVAL2??1() $ VAL2.?1() then the 'th node has null LSON pointer; and if CVAL?A() $ VAL2.4() then the 'tli node has null RSON pointer. These observations immediately give rise to AIgorithm A3 which has 0(N) time complexity. Note that AIgorithm A2 can be obtained from AIgorithm A3 as a spe cial case by setting S = 0. 4. DERWATION OF PARALLEL ALGORITlIM We will first consider the development of a parallel algorithm to grow a balanced binary search tree from the array LINK and after that we will consider the problem of a parallel traversal of a binary search tree. The model of parallel computation that we will be using is a simplification of the shared memory model (SMM) and can be characterized as follows 1. There are M processing elements (PEs) or processors. These are indexed 1, 2, M and the jtA PE is referenced as Pj. Each PE has the capability of perform- ing all the standard arithmetic and logic operations. Each PE knows its own index. 2. There is a common memory that is sbared among all the PEs. All PEs can read and write into this memory at any time instance but if two or more PEs attempt to read (write) from (to) the same memory location, a read (write) con- flict occurs. - 15 Algorithm A3 : Iterative growing algorithm. Level restructuring is done by visiting the nodes from left to right in increasing level order setting up links to construct a balanced binary tree. procedure LEVEL-STRUCT declare 5, N, n, I, J, K, K' Ki, Ki', K2, K2', LINK(1:N), LSON(1:N), RSON(1:N) 5 2?- iN for I 1 to n-1 do // for each level // for J := 1 to 2!?i do //for all nodes on a level // K := + (J-1) * (K + N - 5 + 1)/ 2 if K' > K then K? K 1/ K' = VAL?(), using eq. if odd(K) A (K = K') then //leaves on the highest level // LSON(LINK(K')) null RSON(LINK(K')) null endif if even(K) then // not on the highest level // Ki :--H 2?1-1 + (2*J - 2) * 2?? // set up left link // Ki' := (Ki + N - 5 + 1)1 2 if Ki' > Ki then Ki' := Ki // K11 = VAL?) // if odd(Kl) A (K1 # Ki') /1 odd(Ki) --H? K' on level n-1 // then LSON(LINK(K')) := null else LSON(LlNK(K')) := LINK(Ki') K2 := 2?1?1 + (2*J - 1) * 2?' // set up right link // K2' := (K2 + N - 5 + 1)1 2 if K2' > K2 then K2' K2 II K2' = vAL?() II if odd(K2) A (K2 # K2') /1 odd(K2) ? K' on level n-1 // then RSON(LlNK(K')) := null else RSON(LINK(K')) := LINK(K21) endif endfor endfor end LEVEL-STRUCT - 16 - 3. The FEs need not be synchronized. In all the algorithms we will develop, we will ensure that no read or write conflict occurs. The straightforward approach for transforming AIgorithm A3 into a parallel algo- ritbm would be to allocate one processor per cell in the array LINK and to have each processor set up its own links to construct a balanced binary tree. For this, a processor ?k associated with LINK(k) should be able to determine the following Ri. i, j such that VALN() = k; that is its final position in the balanced binary tree R2. if it has a non-null LSON then determine ki such that VALN() R3. if it has a non-null RSON then determine k2 such that VALN() = k2 We are interested in a constant time complexity parallel algorithm and under that restriction we wish to determine all the above information. 4.1. Parallel Algorithm for Growing Complete Balanced Binary Trees Following the stepwise refinement methodology, we first consider the simpler case where a complete balanced binary tree is to be constructed. First, for any processor we should be able to determine in a constant time the indices i, j such that VAL? 1() = k. Consider Fig. 3 where, as before, the nodes are annotated - 17 - with their VAL values. It is obvious that a processor ?k may correspond to dif- ferent indices , M = 1, 2, ... (note j will be constant) depending on the size of the complete balanced binary tree. But what is invariant over the size of the complete balanced binary tree are the indices A, j where A = fl--Hi. So if A, j values are permanently associated with a processor ?k and if the total number of nodes in the tree is passed as an argument/parameter then the processor can deter- mine its indices and hence requirement Ri can be met in constant time. It is this observation, that we can assign computation to the processes in such a way that the indices A and j are kept constant as the size of the array changes, that allows us to derive a constant time complexity parallel algorithm. (If it is not possi- ble to associate the constants A, i permanently with a processor then the indices i, j can be determined for each process ?h, but not in constant time.) (a) node with value 6 has j=2, h=2 (b) node with value 6 has j=2, h=2 Fig. 3. Node identification which is invariant over size of complete balanced binary tree. The requirements R2 and R3 can be satisfied very easily in constant time since from Theorem 3 we know how to calculate VAL2??1() for any arbitrary i and j - 18 The AIgorithm A4 follows immediately. This algorithm has a constant time com- plexity when run on an N-processor configuration; and it involves no possibility of read or write conflicts. Algorithm A4 : Parallel growing algorithm for the construction of a balanced binary tree by sirnu? taneously executing processes ?1,??,?N, one for each cell in the array LINK, where N = procedure PC-LEVEL-STRUOT declare N, LINK(1:N), LSON(1:N), RSON(1:N) for each PE `)K do in parallel declare n, H, J, K constant Ii, J n := ?log(N+ 1)1 I := n - H if odd(K) then /? leaves // LSON(LINK(K)) := null RSON(LINK(K)) := null endif if even(K) then 1/interior nodes // LSON(LINK(K)) := LINK(K-2?4-1) RSON(LINK(K)) := LINK(K+ 2n-I-1) endif endfor end PC-LEVEL-STRUCT 4.2. Parallel Algorithm ror Growing Balanced Binary Trees When considering arbitrary balanced binary trees, a cell LINK(k) may correspond to different indices and , where i $ i' and j $ j', as the size of the tree changes. The calculation of the indices becomes much more complicated (and time consuming) in this case but this can be avoided in the following way. 10 Let process `)k be associated with LINK(k). Instead of allowing a process ?A to determine the indices to set up links for LINK(h), we will allow the possi- bility of some other process `)m, m $ A setting up the links for LINK(h) . The choice of which processor P? to set up links for LINK(h) must be made so that P1' can easily determine the indices required for setting up links for LINK(h). We will allow a process ?K to set up links for LINK(h) where A =min[A',[A' + N-S+ 1]/2] This corresponds to `reorganising the computation' To translate this into an algorithm would require the use of 2'. - 1 processors where n = ? log(N+ 1)1 for a tree of size N nodes, as indicated in AIgorithm A5. The structure of AIgorithm A3 consists of two nested loops. We have derived a parallel algorithm A5 from this by assigning computation to processors in such a way that each processor can determine its own distinct pair of indices corresponding to the two loops in constant time. Once this is possible, the rest of the computation can be accomplished in constant time as it amounts to having each processor execute the body of the inner loop of Algorithm A3 once. In AIgorithm A5, we require at times more processors than the size of the corresponding tree. As an illustration, Fig. 4 shows the details of the computation done for a tree of size 10. To avoid using more processors than the size of the tree, we would like to be able derive a new algorithm A6 that would reorganise the com- putation as shown in the last column of Fig. 4. The translation from A5 to A6 to achieve this is straightforward; a processor ?k that was not setting up any links in A5 is made to take over the responsibility of processor ?k + S Both Aigorithms A5 and A6 run in constant time on an appropriate multiprocessor configuration and no read or write conflicts are possible in their execution. 20 Algorithm A5 : Parallel growing algorithm for the construction of a balanced binary tree by simul- taneously executing processes P1,..,P? where n = Flog(N+ 1)1. procedure P-LEVEL-STRUCT declare N, LINK(1:N), LSON(1:N), RSON(1:N) for each FE PK do in parallel declare n, N, HI, J, S, K, K', Ki, Ki', K2, K2' constant H, J n := ?log(N+ 1)1 I := n -11 S := 2?- 1 - N K := 2?' + (J-1) * (K + N - S + 1)1 2 ifK' > K then K' := K if odd(K) A (K --H K') then LSON(LINK(K')) := null RSON(LlNK(K')) := null endif if even(K) then Ki := 2??1 + (2*J - 2) * K11 (KI + N - S + 1)1 2 if Ki' > Ki then Ki' := Ki if odd(K1) A (Ki # Ki') then LsoN(L!NK(K')) null else LsoN(LlNK(K')) := LINK(Kl') K2 := 2??' + (2*J - 1) * K2' := (K2 + N - S + 1)1 2 if K2' > K2 then K2' := K2 if odd(K2) A (K2 # K2') then RSON(LINK(K')) := null else RsoN(LINK(K')) := LINK(K2') fiK' = YAL?)fl //leaves on the highest level // // not on the highest level // // set up left link // = VAL?)fl /1 odd(K1) K' on level n-1 // // set up right link // = VAL?()// // odd(K2) ? K' on level n-1 // endif end for end P-LEVEL-STRUCT 21- Algorithm A6 : Parallel growing algorithm for the construction of a balanced binary tree by execut- ing simultaneously processes P1,.?,PN- procedure P-LEVEL-STRUCTl declare N, LINK(1:N), LSON(1:N), RSON(1:N) for each PE PK do in parallel declare n, N, H, I, J, S, K, K' Ki, KI', K2, K2' constant H, J n ?log(N+ 1)1 I := n - H S 2? - 1 - N K := + (J.1) * 2?1+1 (K + N - S + 1)1 2 if K' > K then K' := K if odd(K) A (K --H K') then LsoN(L!NK(K')) null HsoN(LINK(K')) null endif ifodd(K)A(K # K')then K := K + S K ` (K + N - S + 1) / 2 if K' >KthenK' :=K endif if even(K) then Ki 2??' + (2*J - 2) * 2fr?1 Kl? (Ki + N - S + 1) / 2 if Ki' > Ki then Ki' Ki if odd(Ki) A (Ki $ Ki') then LSON(LINK(K')) null else LSON(LINK(K')) := LINK(Kl') K2 := 2??1 + (2*J - 1) * 2fr?i (K2 + N - S + 1) / 2 if K2' > K2 then K2' := K2 if odd(K2) A (K2 $ K2') then RsoN(LINK(K')) := null else RSON(LIN?K(K')) := LINK(K2') endif 11K' = VALN?)ll //leaves on the highest level // // compute for PK+s 1/ // set up left link // /1 Ki' = VALN() 1/ 1/ odd(Ki) --H? K' on level n-1 /1 // set up right link /? /1 K2' = vALq) 1/ /1 odd(K2) ? K' on level n-1 // endfor end P-LEVEL-STRUCTl Processor - 22 - Aig. A5 sets up links for Aig. A6 sets up links for PI5 not used Pi4 LINK(1o) not used Pi3 not used Pi2 LINK(9) not used P1I not used plo LINK(S) LINK(S) Pg LINK(1o) PS LINK(7) LINK(7) P7 LINK(9) P6 LINK(6) LINK(6) PS LINK(S) LINK(S) P4 LINK(4) LINK(4) P3 LiNK(3) LINK(3) P2 LINK(2) LINK(2) PI LINK(1) LINK(i) Fig. 4. Reorganising computation. 4.3. Parallel Traversal In this section we derive a parallel traversal algorithm from the recursive algorithm Al. We could first try to rewrite Al as an iterative algorithm and then derive a parallel algorithm from that. Such an iterative algorithm could somehow try to mimic the recursive algorithm Al by explicitly maintaining a stack. Instead, we are going to directly derive a parallel algorithm from algorithm Al by keeping extra -23- information with the binary search tree. Of course, we can always keep a complete copy of the entire binary search tree at each node and then be able to come up with a parallel algorithm for traversal. But such a solution is impractical both in terms of the extra time and space required so that each node has a global view of the entire binary search tree, and also in terms of the time needed to make use of the extra information to do the traversal of the tree. The extra information we would like to keep should be simple and easy to update as values are added and removed from the binary search tree. When considering a binary search tree of size N, if N processors are available then each processor can be associated with a unique node of the binary search tree. The extra information kept at each node should ideally allow the processor associated with that node to infer the cell in the array LINK to which it will be linked. Now a node i will be linked to the cell LINK(k) if there are exactly k nodes in the binary search tree with values less than or equal to the value associated with node i. So, if with each node we kept the information about the number of nodes that have values less than or equal to its value, the traversal of the binary search tree can be accomplished in constant time. We will therefore assume that with every node in the binary search tree an addi- tional field NUM is associated. The value of this field for node i, NUM(i), gives the number of nodes in the binary search tree that have values less than or equal to the value associated with the node i. It is straightforward to see that the value of this new field is altered only when entries are added or removed from the binary search tree and that this field value can be updated as entries are added and deleted from the binary search tree without any increase in the time complexity of perform- ing these operation. - 24 - AIgorithm A7 allows the parallel traversal of a binary search tree under the assump- tion that extra information is stored with each node; it also has a constant time complexity. Algorithm A7 : Parallel traversal algorithm by processes one for each node of the tree exe- cuting simultaneously. procedure P-TRAVERSE declare K, LINK(1:N), NUM(1:N) for each PE ?K do in parallel LINK(NUM(K)) K endfor end P-ThAVERSE 5. CONCLUSIONS In this paper we have shown how the problem of balancing a binary search tree can be solved efficiently on a multiprocessor configuration. The algorithm developed achieves the maximum possible speed-up. The algorithms that we have presented can also be easily scaled so that a tree of size N can be balanced in time constant * FN/k 1 if k processors are available. The various theorems can also be extended to cover any n-ary tree and hence parallel algorithms to balance n-ary trees can be derived. Another straightforward extension is to derive algorithms to obtain perfectly balanced trees. We have also shown how the algorithms are developed by the stepwise refinement methodology of Wirth. The relationship between the various algorithms is shown in Fig. 5. - 25 - Development of Traversing Algorithm ?tbm (`?t recursive traversing algoL ? parallel algorithm Development of Growing Algorithm recursive growing algorithm 0-1141 A7 keep additional information efficient sequencing special case iterative > iterative algorithm algorithm A2 compensate for missing A3 leaves on level n allocate processors so that allocate processors so that the do loop indices can be the do loop indices can be determined in constant time determined in constant time special case parallel > parallel algorithm algorithm A4 compensate for missing leaves on level n and reorganise computation reorganise computation to for efficiency remove the useless processes parallel algorithm A6 Fig. 5. Development of parallel algorithms for balanced binary trees. -26 - ACKNOWLEDGEMENTS We are grateful to Professors J. L. Bentley, M. Joseph and F. B. Schneider for their useful comments on previous versions of this paper. REFERENCES 1. T. Agerwala and B. Lint, "Communication in parallel algorithms for Boolean matrix multiplication," in Proc. lEEE Int. Coni. Parallel Process., 1S78, pp. 116-153. 2. E. Mjomandi and D.G. Corneil, "Parallel computations in graph theory," in Proc. 6th IEEE Symp. Fonnd. Compnt. Sci., Oct. 1?75, pp. 13-18. 3. R.P. Brent, "The parallel evaluation of general arithmetic expressions," j. Ass. Cornput. Mach., vol. 21, pp. 201-206, Apr. 1g74. 4. II. Chang, and 5.5. !yengar, "Efficient algorithms to globally balance binary search trees," Cornrnun. Ass. Cornput. Mach., vol. 27, no. 7, pp. 605-702, July 1084. 5. L. Csanky, "Fast parallel matrix inversion algorithms," in Proc. 6th IEEE Symp. Found. Cornput. Sci., Oct. 1075, pp. 11-12. 6. A.C. Day, "Balancing a binary tree," The Computer Journal vol. 10, pp. 360 361, 1076. 7. E. Dekel and 5. Sahni, "Parallel generation of postfix and tree forms," Ass. Comput. Mach. Trans. on Prog. Lang. and Sys., vol. 5, pp. 300-317, July 1083. - 27 - 8. E. Dekel and S. Sahni, "Binary trees and parallel scheduling algorithms," IEEE Trans. Comput., vol. C-32, pp. 307-315, March 1983. 9. D.S. Hirschberg, "Parallel algorithms for the transitive closure and the con- nected component problems," in Proc. 8th Ass. Cornput. MacA. Symp. Theor. CompuL, May 1976, pp. 5?57. 10. D.S. Hirschberg, "Fast parallel sorting algorithms," Commun. Ass. Cornput. Mach., vol. 21, pp. 657-661, Aug. 1978. 11. D.E. Knuth, The Art of Computer Programming VoL 3: Sorting and Searching. Reading, MA: Addison-Wesley, 1973. 12. W.A. Martin and D.N. Ness, "Optimal binary trees grown with a sorting alg? rithm," Commun. Ass. Cornput. Mach., vol. 15, pp. 8893, Feb. 1972. 13. D.E. Muller and F.P. Preparata, "Bounds to complexities of networks for sort- ing and for switching," J. Ass. Cornput. MacA., vol. 22, pp. 195-201, Apr. 1975. 14. I. Munro and M. Paterson, "Optimal algorithms for parallel polynomial evalua- tion," JCSS, vol. 7, pp. 18()?198, 1973. 15. F.P. Preparata, "New parallel-sorting schemes," IEEE Trans. Cornput., vol. C- 27, pp. 669-673, July 1978. 16. N. Wirth, "Program development by stepwise refinement," Commun. Ass. Cornput. MacA., vol. 14, pp. 221-227, Apr. 1971.