/* * HW1. 2: * * Let A[1...n] be an array of real numbers. Design algorithms to perform any sequence of the following two operations: * Add(i,y): Add the value of y to the ith number. * Partial_sum(i): return the sum of the first i numbers A[1]+A[2]+...+A[i]. * Each operation should take O(logn) steps. You can use one more array of size n as work space. * Extend the above to support insertion and deletion. Each element now has a key and a value. An element is accessed by its key. * The addition operation applies to the values (but the elements are accessed by their keys). The Partial_sum operation is different * Partial_sum(y): return the sum of all the elements currently in the set whose value is less than y. * The worst-case running time should still be O(nlogn) for any sequence of O(n) operations. * */ Initialization step: We call the procedure Init(T,A,1,n,tmp) to construct a binary tree T, by recursion, with the given array A of numbers as the keys stored in T's leaves. For each inner node of T, the key stored is the sum of the keys stored in its left and right children. Algorithm for the procedure Init(T,A,p,q,tmp): step 1: If there is more than one number in the array A, goto step2. Otherwise, we need to build up a tree with a root, whose left child is A[1], and the key stored in the root is the number A[1]. Then we finish initialization and return. step 2: If there are more than 1 number in the array A[p...q], goto step3. Otherwise, there is only one number and it is unpaired. We keep record of this number by using a temporary pointer tmp to the element. step 3: Get an new empty node for T. step 4: If there are more than two numbers in the array A[p...q], goto step5. Otherwise, we build up a binary tree. Its root records the sum of this two numbers, and its left child has the key A[p] and its right child has the key A[q]. step 5: Get the index to the middle of the array A[p...q], calculated as (p+q)/2. Then use Init(left[T],A,p,(p+q)/2) to get the left child of subtree T. Similarly, use Init(right[T],A,(p+q)/2+1,q) to get the right child of subtree T. step 6: After we get the left and right children of subtree T, we can get the key for the root of the subtree by add the keys in the left and right children. But there is an exception. If n is not a power of 2, then there may be an unpaired node in some level. In this case, the right child of the tree is not constructed and hence is empty. And the unpaired node is recorded in a temporary pointer. So we get the unpaired node and use its key in place of the key of the right child to calculate the key in the root. And then the unpaired node becomes the right child of the tree. The procedure is given below: /* * Init(T,A,p,q,tmp): * This procedure builds up a binary tree from the numbers A[p...q], whose root contains the sum of these numbers. The keys of * the inner nodes contain the sum of the keys stored in its left and right children. * T: the tree to be built from A in this stage * A: the set of numbers to be operated on * p: the start index of the part of array to be concerned * q: the end index of the part of array to be concerned * tmp: a pointer to keep record of the unpaired number for next use, initially assigned to Null. Consider the case that n * is not a power of 2. * */ Init(T,A,p,q,tmp) { if(p==q) { if(p==1) //step1 { T.key=A[p]; T.left=&A[p]; } else tmp=&A[p]; //step2 else { NewNode(T); //step3 if(q==p+1) //step4 { T.key=A[p]+A[q]; T.left=&A[p]; T.right=&A[q]; } else { //step5 Init(left[T],A,p,(p+q)/2,tmp); Init(right[T],A,(p+q)/2+1,q,tmp); if(right[T]==Null) //step6 { T.key=T.left.key+tmp.key; T.right=tmp; } else T.key=T.left.key+T.right.key; } } } The time complexity for the algorithm has the recursive relation: T(n)=2T(n/2)+O(1). And so we get T(n)=O(n). As to the space complexity, the number of inner nodes in a binary tree is n-1, where n is the number of leaves. Also we use an temporary pointer to record the unpaired node. So totally an array of size n is used as work space. /******************************************************************************/ Addition operation: We should update the inner nodes so that we can keep the partial-sum correct after addition. The nodes that should be updated are those in the path from the root to the ith number in the array A. So we search for the ith number in the binary tree and in each step during searching, update the node in the path. We call the procedure Add(i,y,T,A,1,n) to implement the addition operation, by recursion, using the binary tree constructed in the initialization step. Algorithm for the procedure Add(i,y,T,A,p,q): step 1: If we haven't found the ith number yet, goto step2. Otherwise, update the node by adding y to the key. step 2: Update the root of this subtree. step 3: compare i with the index of the middle of the array A[p...q] to decide which subtree should be concerned. If i is less than the middle index, then search the ith number in the left subtree. Otherwise search it in the right subtree. The procedure is given below: /* * Add(i,y,T,A,p,q): * This procedure adds the value y to the ith number. * i: the index of the number to be operated on * y: the value to be added to the ith number in the array A * T: the subtree to be concerned for searching for the ith number * A: the set of numbers to be operated on * p: the start index of the part of array to be concerned * q: the end index of the part of array to be concerned * */ Add(i,y,T,A,p,q) { if(p==q) A[p]=A[p]+y; //step1 else { T.key=T.key+y; //step2 mid=(p+q)/2; //step3 if(i<=mid) Add(i,y,left[T],A,p,half); else Add(i,y,right[T],A,half+1,q); } } As to the time complexity, since it is similar to binary search, it takes O(logn) operations. /***********************************************************************************/ Partial_sum operation: To get the partial_sum of the first i numbers, we do a binary search for the ith number and consider the path from the root to the ith number, as what we have done in addition operation. The left siblings to each nodes in the path from the root to the ith number record the sums of several numbers before the ith number. If we add all the keys in these nodes, we get the partial_sum of the first (i-1) numbers. And then add the ith number and we get the the partial sum of the first i numbers. We call the procedure Partial_sum(i,y,T,A,1,n,sum) to implement the Partial_sum operation, by recursion, using the binary tree constructed in the initialization step. Algorithm for the procedure Partial_sum(i,T,A,p,q,sum): step 1: If we haven't found the ith number yet, goto step2. Otherwise, add the ith number to the sum. step 2: Compare i with the index of the middle of the array A[p...q] to decide which subtree should be concerned. If i is less than the middle index, goto step3; otherwise, goto step4. step 3: Search the ith number in the left subtree. step 4: Add the key in the root of the left child to the sum, since the leaves in this subtree are all among the first (i-1) numbers. Then search the ith number in the right subtree. The procedure is given below: /* * Partial_sum(i,T,A,p,q,sum): * This procedure gets the sum of the first i numbers in array A. * i: the end index for partial sum * T: the subtree to be concerned for searching for the ith number * A: the set of numbers to be operated on * p: the start index of the part of array to be concerned * q: the end index of the part of array to be concerned * sum: the sum for the first i numbers * */ Partial_sum(i,T,A,p,q,sum) { if(p==q) sum=sum+A[p]; //step1 else { mid=(p+q)/2; //step2 if(i<=mid) Partial_sum(i,left[T],A,p,half,sum); //step3 else //step4 { sum=sum+T.left.key; Partial_sum(i,right[T],A,half+1,q,sum); } } } Since it is similar to binary search, the time complexity for the algorithm is O(logn). /*******************************************************************/ For the extended part In the initialization step, we build up a binary tree, a special case of a 2-3 tree. So we treat it as a 2-3 tree while inserting and deleting so that we can keep it almost balanced, and make some changes in the structure. (1) Sort the numbers according to their values instead of indices before we constructure the binary tree. (2) In each inner node, besides the sum of its left and right chilren, we also record the information of the values in the leaves so that we can search for given value in the tree as what we do in a 2-3 tree. There are at most two keys in each node. Take the key in the root of its leftmost child as its first key and take the key in the root of the middle (if it has three children) or the rightmost (if it has two children) child as its second key. (3) We use anothe array index[1...n] of size n to record the order of the indices of numbers in the sorted array. Therefore, we can do insertion and deletion on the tree just as what we do on a 2-3 tree, except that the sum information should also be maintained. And also, the addition and deletion operation can be implemented. /******************************************************************/ Insertion operation: This procedure inserts a value into the array A. We can implement it by using the binary tree as a 2-3 tree constructed in the initialization step. We should also update the inner nodes so that we can keep the partial-sum correct after addition. The nodes that should be updated are those in the path from the root to the number to be inserted. While we are looking for the proper position for the number to be inserted, we update the sum stored in each node in the path. Algorithm for the procedure Insert(i,value,T): step 1: Split the root of the tree if it has three children. step 2: Call the procedure Insert-Nonfull(i,value, T) Algorithm for the procedure Insert-Nonfull(i,value,T) step 1: If T is a leaf node, insert value into the proper position of T. Keep record of its index in the array index[1...n]. Otherwise, goto step2. step 2: Update the root of the subtree by adding value into the sum stored in the root. Determine the child of T to which the recursion descends. If the recursion descends to a full child, split the child into two nonfull child and then determine which of the two children is now the correct one to descend to. Then recurse to insert the value into the appropriate subtree. Therefore, we finally insert the value into the appropriate leaf node in the subtree roote at the internal node T, update the sum along the path and keep record of its index in the array index[1...n]. Since it is similar to insertion in a 2-3 tree, the time complexity for the algorithm is O(logn). /******************************************************************/ Deletion operation: This procedure deletes a value from the array A. We can implement it by using the binary tree as a 2-3 tree constructed in the initialization step. We should also update the inner nodes so that we can keep the partial-sum correct after addition. The nodes that should be updated are those in the path from the root to the number to be inserted. While we are looking for the proper position for the number to be inserted, we update the sum stored in each node in the path. Algorithm for the procedure Delete(i,value,T) case 1: If the value is in node T and T is a leaf, delete the value from T. Meanwhile, update the record of index in the array index[1...n]. case 2: If value is in the leaf of the internal node T, then update the root of the subtree by substracting value from the sum stored in the root. Determine the root r of the appropriate subtree that must contain value. If r has only one values, execute step 3a or 3b as necessary to guarantee that we descend to a node containing at least two values. Then finish by recursing on the appropriate child of T. a. If r has only one value but has a sibling with two values, give r an extra value by moving a value from T down into r, moving a value from r's immediate left or right sibling up into T, and moving the appropriate child from the sibling into r. Also update the index array. b. Of r amd all of r's siblings have one value, merge r with one sibling, which involves moving a value from T down into the new merged node to become the median value for that node. Also update the index array. Since it is similar to deletion in a 2-3 tree, the time complexity for the algorithm is O(logn). /*****************************************************************/ Addition operation: This procedure adds the value y to the ith number. Algorithm for Addition: step 1: Look up in the index array and get the value for the ith number. step 2: Delete(i,value,T) step 3: Insert(i,value+y,T) Since insertion and deletion update the information in the tree and thus keep the partial_sum correct, Addition operation will also keep partial_sum correct. And it takes O(logn). /***************************************************************/ Partial_sum(y) operation: This procedure gets the sum of those numbers less than y. It is similar to Partial_sum(i) that have been implemented in the first part,except that we search for the value instead of index in the tree, whose leaves are sorted according to their values instead of indices. Replacing index by value in the original algorithm for partial_sum, we can get the algorithm for the restated partial_sum operation. And it takes O(logn) as before.