### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# ANALYSIS OF ALGORITHMS CPSC 629

Texas A&M

GPA 3.58

### View Full Document

## 9

## 0

## Popular in Course

## Popular in ComputerScienence

This 25 page Class Notes was uploaded by Mozell Lind on Wednesday October 21, 2015. The Class Notes belongs to CPSC 629 at Texas A&M University taught by Staff in Fall. Since its upload, it has received 9 views. For similar materials see /class/226087/cpsc-629-texas-a-m-university in ComputerScienence at Texas A&M University.

## Popular in ComputerScienence

## Reviews for ANALYSIS OF ALGORITHMS

### What is Karma?

#### Karma is the currency of StudySoup.

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 10/21/15

CPSC629 Analysis of Algorithms Spring 2003 Instructor Dr Jianer Chen Of ce HRBB 416 Phone 845 4259 Email chen c5tamuedu Of ce Hours TTR 230pm 3z55pm Teaching Assistant Xiuzhen Huang Of ce HRBB 41913 tel 862 6611 email xzhuang cstamuedu Of ce Hours MiVV i TR 130pm 2z30pm Course Notes 7 2 Why Is Binary Search Optimal It is well known that Binary Search takes time 0log on searching in a sorted array of n elements In this notes we show that any searching algorithm must spend at least time Qflog on searching an element in a set of n elements no matter how the set is organized In consequence this result shows that Binary Search algorithm is optimal We need to make some restrictions on the class of searching algorithms in our discussion We say that a searching algorithm A is by comparisons if the algorithm searches an input element 2 in a given set L by comparing the element 2 with the elements in L Theorem 1 Any searching algorithm by comparisons has time complexity Qflog on a set ofn elements no matter how the set is organized PROOF Let A be any searching algorithm by comparisons The input to the algorithm A consists of a set L of n elements and another element 23 The algorithm returns YES if and only if the element 2 is in the set L We show that there is an input set L such that no matter how the set L is organized for some element 23 the algorithm A must spend time at least Qflog on the set L and the element 2 to make a correct decision Let L a1 an be a set of n integers such that the difference of any two elements ai and aj in L is larger than n For example Lnl2n2n2n For this xed set L and a variety of input elements 23 the algorithm A can be represented as a binary tree T as follows The root of the binary tree T stands for the rst comparison of the element 2 with a set element a by the algorithm A The comparison may take the form 1 lt a 1 gt a or 2 a The algorithm A branches into two paths depending on the result of the comparison Each path will branch into two paths based on a second comparison of the input element 2 and a set element and so on This gives the binary tree T Each internal node in the tree T is a comparison of the input element 2 and a set element ai and each leaf represents a decision made by the algorithm A either yes or no depending on the input element Therefore on each input element 23 the algorithm A will follow a particular path in the tree T from the root to a leaf and make a correct decision How many leaves labeled yes in the tree T can there be Let a be a set element in the set L Then the input element 2 a will lead to a yes leaf in the tree T Let a and aj be two different set elements in the set L We claim that the two input elements 5221 a and 5232 aj must lead to two different yes leaves in the tree T Suppose this is not true Then the two input elements 5231 a and 5232 aj would lead to the same yes leaf in the tree T Without loss of generality suppose 5231 lt 5232 Since the difference of 521 and 32 is at least 72 there must be an element 5230 such that 5231 lt 5230 lt 5232 such that 5230 is not in the set L However since 5231 and 5232 take the same result on every internal node on the path from the root to that yes leaf in the tree T the input element 5230 should also take the same result on every internal node on that path For example if both 5231 lt ak and 5232 lt ak are true then 5230 lt ak must be true Therefore the input element 5230 would also lead to the same yes leaf in the tree T But this would mean that the algorithm A on input element 5230 which is not in the set L incorrectly reports yes This contradicts our assumption that the algorithm A always reports correctly This contradiction shows that on every two input elements 521 a and 332 aj where a and aj are set elements the algorithm A must go to two different yes leaves Since there are n different set elements in the set L the above analysis shows that the tree T has at least n yes leaves In consequence the binary tree T has at least n leaves It is well known that a binary tree of n leaves has depth at least log n Therefore the path from the root of T to some leaf of T must have length at least log n This implies that on some input element 23 before making a correct decision the algorithm A makes at least logn comparisons of the input element 2 and set elements in L Thus on this input the algorithm A takes time at least Qflog In the language of worst case analysis the above proves that the algo rithm A takes time Qflog on sets of n elements Since the algorithm A is arbitrary the lemma is proved 1 CPSC629 Analysis of Algorithms Summer 2003 Instructor Dr Jianer Chen Of ce HRBB 416 Phone 845 4259 Email Chen cstamuedu Of ce Hours MTVVTF 335pm 4z30pm Teaching Assistant Xiuzhen Huang Of ce HRBB 41913 tel 862 6611 email xzhuang cstamuedu Of ce Hours TThF 1230pm 200pm Course Notes 1 2 3 Trees A set is a collection of elements All elements of a set are different which means no set can contain two copies of the same element We shall sometimes assume that elements of a set are linearly ordered by a relation usually denoted lt and read less than or precedes For example we can order a set of points in the 2 dimensional Euclidean space by their m coordinates Let S be a set and let u be an arbitrary element of a universal set of which S is a subset The fundamental operations occurring in set manipulation are a MEMBERW S Is u E S o INSERTW S Add the element u to the set S o DELETEu S Remove the element u from the set S When the universal set is linearly ordered the following operations are very important I MINIMUMS Report the minimum element of the set S I SPLITu S Partition the set S into two sets S1 and S2 so that S contains all the elements of S which are less than or equal to u and S2 contains all the elements of S which are larger than u I SPLICES 3152 Assuming that all elements in the set S are less than any element in the set 32 form the ordered set S S U 32 We will introduce a special data structure 2 3 trees which represent sets of elements and support the above set operations e iciently De nition 01 A 23 tree is a tree such that each nonleaf node has two or three children and every path from the mat to a leaf is of the same length The proof of the following theorem is straightforward and left to the reader Theorem 1 A 23 tree of n leaves has height Olog n A linearly ordered set of elements can be represented by a 2 3 tree by assigning the elements to the leaves of the tree in such a way that for any non leaf node of the tree all elements stored in its rst child are less than any elements stored in its second child and all elements stored in its second child are less than any elements stored in its third child if it has a third child Each non leaf node 2 of a 2 3 tree keeps three pieces of information for the corresponding subtree I Lv the largest element stored in the subtree rooted at its rst child I Mv the largest element stored in the subtree rooted at its second child I H 2 the largest element stored in the subtree rooted at its third child if it has one 1 Member The algorithm for deciding the membership of an element in a 2 3 tree is given as follows where T is a 2 3 tree 1 is the root of T and u is the element to be searched in the tree Algorithm MEMBERT u BEGIN IF T is a leaf node then report properly ELSE IF Lt gt 11 then MEMBERltchild1T u ELSE IF Mt gt 11 then MEMBERltchild2T u ELSE IF t has a third child THEN MEMBERltchild3T u ELSE report failure END Since the height of the tree is Olog n and the algorithm simply follows a path in the tree from the root to a leaf the time complexity of the algorithm MEMBER is Olog n 2 Insert To insert a new elment a into a 2 3 tree we proceed at rst as if we were testing membership of a in the set However at the level just above the leaves we shall be at a node 2 that should be the parent of 3 If 2 has only two children we simply make a the third child of 2 placing the children in the proper order We then adjust the information contained by the node 2 to re ect the new situation Suppose however that a is the fourth child of the node 2 We cannot have a node with four children in a 2 3 tree so we split the node 2 into two nodes which we call 2 and 2 The two smallest elements among the four children of 2 stay with 2 while the two larger elements become children of node 2 Now we must inset 2 among the children of p the parent of 2 The problem now is solved recursively One special case occurs when we wind up splitting the root In that case we create a new root whose two children are the two nodes into which the old root was split This is how the number of levels in a 2 3 tree increases The above discussion is implemented as the following algorithms where T is a 2 3 tree and a is the element to be inserted Algorithm INSERTT X BEGIN 1 Find the proper node v in the tree T such that v is going to be the parent of x 2 Create a leaf node d for the element x 3 ADDSDNV d END Where the procedure ADDSON is implemented by the following recursive algorithm which adds a child d to a non leaf node 2 in a 2 3 tree Algorithm ADDSDNV d BEGIN 1 IF v is the root of the tree add the node d properly Dtherwise do the following 2 IF v has two children add d directly 3 ELSE 31 Suppose v has three children c1 c2 and c3 Partition c1 c2 c3 and d properly into two groups g1 g2 and g3 g4 Let v be the parent of g1 g2 and create a new node v and let v be the parent of g3 g4 32 Recursively call ADDSDNltfatherv v END Analysis The algorithm INSERT can nd the proper place in the tree for the element a in Olog n time since all it needs to do is to follow a path from the root to a leaf Step 2 in the algorithm INSERT can be done in constant time The call to the procedure ADDSON in Step 3 can result in at most Olog n recursive calls to the procedure ADDSON since each call will jump at least one level up in the 2 3 tree and each recursive call takes constant time to perform Steps 1 2 and 31 in the algorithm ADDSON So Step 3 in the algorithm INSERT takes also Olog n time Therefore the overall time complexity of the algorithm INSERT is Olog n 3 Minimum Given a 2 3 tree T we want to nd out the minimum element stored in the tree Recall that in a 2 3 tree the numbers are stored in leaf nodes in ascending order from left to right Therefore the problem is reduced to going down the tree always selecting the left most link until a leaf node is reached This leaf node should contain the minimum element stored in the tree Evidently the time complexity of this algorithm is Olog n for a 2 3 tree with n leaves Algorithm MINIMUMltT min BEGIN IF T is a leaf THEN min ELSE call MINIMUMltchild1T min END 4 Delete When we delete a leaf from a 2 3 tree we may leave its parent 2 with only one child If 2 is the root delete 2 and let its lone child be the new root Otherwise let p be the parent of 2 If 13 has another child adjacent to 2 on either the right or the left and that child of 13 has three children we can transfer the proper one of those three to 2 Then 2 has two children and we are done If the children of 13 adjacent to 2 have only two children transfer the lone child of 2 to an adjacent sibling of 2 and delete 2 Should 13 now have only one child repeat all the above recursively with p in place of 2 Summarizing these discussions together we get the algorithm DELETE as shown below Where procedure DELETE is merely a driver for sub procedure DEL in which the actual work is done The variables done and 1801 in DEL are boolean ags used to indicate successful deletion and to detect the case when a node in the tree has only one child respectively In the worst case we need to traverse a path in the tree from root to a leaf to locate the node to be deleted then from that leaf node to the root in case that every non leaf node on the path has only two children in the original 2 3 tree T Thus the time complexity of DELETE algorithm for a tree with n nodes is Olog n Algorithm DELETET X BEGIN Call DELT x done 1son IF done is true THEN IF 1son is true THEN T child1T ELSE x was not found in T handle properly Algorithm DELT x done 1son BEGIN 1 IF children of T are leaves THEN process properly ie if x is found delete it update the variables done and 1son 2 ELSE IN CASE JF x lt LT son child1T LT lt x lt MT son child2T MT lt x lt HT son child3T Call DELson x done 1son1 IF 1son1 is true THEN 1 IF the node T has another child 390 that has three children THEN reorganize the grandchildren among the nodes son and b to make both have two children and set 1son false 555 42 ELSE make the only child of the node son a child of a sibling of it and delete the node son from T If T has only one child then set 1son true END 5 Splice Splicing two trees into one big tree is a special case of the more general operation of merging two trees Splice assumes that all the keys in one of the trees are larger than all those in the other tree This assumption effectively reduces the problem of merging the trees into pasting the smaller tree into a proper position in the larger tree Pasting the smaller tree is actually no more than performing an ADDSON operation to a proper node in the larger tree To be more speci c let T and T2 be 2 3 trees which we wish to splice into the 2 3 tree T where all keys in T1 are smaller than those in T2 Fur thermore assume that the height of T1 is less than or equal to that of T2 so that T is pasted to T2 as a left child of a leftmost node at the proper level in T2 In the case where the heights are equal both T and T2 are made children of the common root T otherwise the proper level in T2 is given by heightT2 heightT1 1 It is clear that the algorithm SPLICE runs in time Olog n In fact the running time is proportional to the height difference heightT2 height T1 1 The implementation of the algorithm SPLICE is given below Algorithm SPLICET T1 T2 Suppose that all elements in T1 are less than any elements in T2 and that the height of T1 is at most that of T2 Dther cases can be dealt with similarly BEGIN IF heightT1 heightT2 THEN make T a parent of T1 and T2 ELSE WHILE heightT21 gt heightT1 DD T2 child1T2 Call ADDSDNltT2 T1 END 6 Split By splitting a given 2 3 tree T into two 2 3 trees T1 and T2 at a given element 3 we mean to split the tree T in such a way that all elements in T that are less than or equal to a go to T1 while the remaining elements in T go to T2 The idea is as follows as the tree is searched for 3 we store the subtrees to the left and right of the traversed path split path For this purpose two stacks are used one for each side of the split path As we go deeper into T subtrees are pushed into the proper stack Finally the subtrees in each stack are spliced together to form the desired trees T1 and T2 respectively The algorithm is given as follows Algorithm SPLITT X T1 T2 Split T into T1 and T2 such that all elements in T1 are less than or equal to x and all elements in T2 are greater than x The stacks Si and S2 are used to store the subtrees to the left and right of the path in the 23 tree T from the root to the leaf K respectively 1 BEGIN 1 WHILE T is not leaf DD IF X lt LT THEN 82 lt child3T child2T T child1T IF LT lt X lt MT THEN 81 lt child1T 82 lt child3T T child2T IF MT lt X lt HT THEN 81 lt child1T child2T T child3T Reconstruct T1 2 T1 lt 81 3 WHILE Si is not empty DD t lt S Call SPLICEltT1 t T1 Reconstruct T2 5 WHILE 82 is not empty DD t lt S Call SPLICEltT2 T2 t END It is easy to that the WHILE loop in Step 1 takes time Olog n The analysis for the rest of the algorithm is a bit more complicated Note that the use of the stacks SI and S2 to store the subtrees guarantees that the height of a subtree closer to a stack top is less than or equal to the height of the subtree immediately deeper in the stack A crucial obserVation is that since we splice shorter trees rst which are on the top part of the stacks the difference between the heights of two trees to be spliced is always very small In fact the total time spent on splicing all these subtrees is bounded by Olog n We give a formal proof as follows Assume that the subtrees stored in stack 81 are tlyt2z tr 1 in the order from the stack top to stack bottom Let Mt be the height of the 2 3 tree 1 According to the algorithm SPLIT we have Mn 3 Mtg 3 3 Mt and no three consecutive subtrees in the stack have the same height Thus we can partition sequence 1 into segments which contains the subtrees of the same height in the sequence 5152 zsq Each 5139 either is a single subtree or consists of two consecutive subtrees of the same height in sequence Moreover q s logn Let May be the height of the subtrees contained in the segment 5139 We have M51 lt M52 lt lt M5 The WHILE loop in Step 3 rst splices the subtrees in segment 51 into a single 2 3 tree T10 then recursively splices the 2 3 tree Tfiill and the subtrees in segment 5139 into a 2 3 tree T1 for 2 2 q We have the following lemma Lemma 2 For all 2 2 q we have WM hT1H g msi lt MSW lt lt msq PROOF That Man 3 hT1 is fairly clear since T1 is obtained by splicing subtrees in the segment 51 For 2 gt 2 since Tfiill is obtained by splicing the tree Ty and the subtrees in 51 and the subtrees in 51 have height h51 Thus the height of the 2 3 tree Ty is at least Msiq Now we prove the rest inequalities Since the 2 3 tree T1 is obtained by splicing the subtrees in the segment 51 and segment 51 contains at most two subtrees both of height hs1 Thus the height of the 2 3 tree T1 is at most M51 1 which is not larger than h52 Thus the lemma is true for the case 2 2 Now assume that the lemma is true for the case 2 1 MTIH g msi lt MSW lt lt msq We consider the height of the 2 3 tree T1 If the segment 5139 is a single subtree ll of height hsi then splicing the tree Tfiill of height at most M541 and the tree ti of height M541 results in a 2 3 tree T1 of height at most hsi 1 which is not larger than hsi1 Now suppose that the segment 5139 consists of two subtrees t and t of height Msi Since the height of the tree T1017 is at most Msi by the inductive hypothesis splicing the trees T1071 and 1 results in a 2 3 tree T of height at most hsi 1 Moreover according the algorithm SPLICE if the height of T is hsi 1 then the root of Iquot has only two children Now splice the trees T and t239 into the 2 3 tree T10 If the height of the tree T is smaller than hsi 1 then splicing T and the subtree 112 of height hsi results in a tree T1 of height at most hsi 1 which is not larger than hsi1 On the other hand if the height of the tree T is hsi 1 then the root of T has only two children thus splicing T and 112 will not create a new root and the resulting tree If has height hsi 1 again not larger than hsi1 This concludes that we always have hTi g hsi1 lt hsi2 lt lt qu This completes the induction proof and shows the correctness of the lemma El Now we are ready for the following theorem Theorem 3 The WHILE loop in Step 3 of the algorithm SPLIT takes time Olog n PROOF First we study the complexity of constructing the 2 3 tree T1 from the 2 3 tree Tfiin and the trees in the segment 5139 According to Lemma 2 we have I WW 3 Ms Thus if 5139 is a single subtree ti then according the analysis of the time complexity of the algorithm SPLICE the time of splicing Tfiill and ti is bounded by a constant times hsi hT1i On the other hand if 5139 consists of two subtrees t and t2 then the time for splicing Tfiill and t is again bounded by a constant times hsi hT1171 Moreover note that the height of the resulting tree T from splicing Tfiill and t is either hsi or hsi 1 and that the height of the subtree 11239 is hsi Thus splicing T and t239 takes only constant time 10 Therefore in this case the total time to construct T1 from ail and 5139 is bounded by a constant times M5 MTl i 1 Therefore to construct the nal 2 3 tree T1 the total time of the WHILE loop in Step 3 is bounded by a constant times I Ems hltT1 gt 1 i By Lemma 2 we have M54141 3 MYTH Thus the time complexity of the WHILE loop in Step 3 is bounded by a constant times I Zhsi M54171 1 i2 which is equal to M5 M51 1 Since all quantities qu M51 and q are bounded by log n we conclude that the WHILE loop in Step 3 takes time Olog n D The same proof shows that the WHILE loop in Step 5 also takes time Olog n In conclusion the algorithm SPLIT takes time Olog n CPSC629 Analysis of Algorithms Spring 2003 Instructor Dr Jianer Chen Of ce HRBB 416 Phone 845 4259 Email chen c5tamuedu Of ce Hours TTR 230pm 3z55pm Teaching Assistant Xiuzhen Huang Of ce HRBB 41913 tel 862 6611 email x0h8507 cstamuedu Of ce Hours MlVV i TR 130pm 2z30pm Course Notes 7 1 23 Trees A set is a collection of elements All elements of a set are different which means no set can contain two copies of the same element We shall sometimes assume that elements of a set are linearly ordered by a relation usually denoted lt and read less than or precedes For example we can order a set of points in the 2 dimensional Euclidean space by their c coordinates Let S be a set and let u be an arbitrary element of a universal set of which 5 is a subset The fundamental operations occurring in set manipulation are MEMBERuS Is u E S INSERTu 5 Add the element u to the set S DELETEu 5 Remove the element u from the set 5 When the universal set is linearly ordered the following operations are very important MINIMUMS Report the minimum element of the set S SPLITu 5 Partition the set S into two sets 51 and 52 so that 51 contains all the elements of S which are less than or equal to u and 52 contains all the elements of S which are larger than u SPLICES 51 52 Assuming that all elements in the set 51 are less than any element in the set 52 form the ordered set S 51 U 52 We will introduce a special data structure 2 3 trees which represent sets of elements and support the above set operations ef ciently De nition 01 A 23 tree is a tree such that each nonleaf node has two or three children and every path from the root to a leaf is of the same length The proof of the following theorem is straightforward and left to the reader Theorem 1 A 23 tree cfn leaves has height 0log A linearly ordered set of elements can be represented by a 2 3 tree by assigning the elements to the leaves of the tree in such a way that for any non leaf node of the tree all elements stored in its rst child are less than any elements stored in its second child and all elements stored in its second child are less than any elements stored in its third child if it has a third child Each non leaf node v of a 2 3 tree keeps three pieces of information for the corresponding subtree Llju the largest element stored in the subtree rooted at its rst child VI the largest element stored in the subtree rooted at its second child H the largest element stored in the subtree rooted at its third child if it has one 1 Member The algorithm for deciding the membership of an element in a 2 3 tree is given as follows where T is a 2 3 tree 15 is the root of T and u is the element to be searched in the tree Algorithm MEMBER u BEGIN IF 39I39 is a leaf node then report properly ELSE IF Lt gt u then MEMBERltchild1T u ELSE IF Mt gt u then MEMBERltchild2T u ELSE IF t has a third child THEN MEMBERltchild3T u ELSE report failure END Since the height of the tree is 0 log n and the algorithm simply follows a path in the tree from the root to a leaf the time complexity of the algorithm MEMBER is 0logn 2 Insert To insert a new elment 2 into a 2 3 tree we proceed at rst as if we were testing membership of 2 in the set However at the level just above the leaves we shall be at a node 1 that should be the parent of 23 If v has only two children we simply make 2 the third child of v placing the children in the proper order We then adjust the information contained by the node v to re ect the new situation Suppose however that 2 is the fourth child of the node 1 We cannot have a node with four children in a 2 3 tree so we split the node 1 into two nodes which we call 1 and v The two smallest elements among the four children of 1 stay with 1 while the two larger elements become children of node 0 Now we must inset 0 among the children of p the parent of v The problem now is solved recursively One special case occurs when we wind up splitting the root In that case we create a new root whose two children are the two nodes into which the old root was split This is how the number of levels in a 2 3 tree increases The above discussion is implemented as the following algorithms where T is a 2 3 tree and 2 is the element to be inserted Algorithm INSEBTT 1 BEGIN 1 Find the proper node v in the tree 39I39 such that v is going to be the parent of x 2 Create a leaf node d for the element x 3 ADDSOMV d END Where the procedure ADDSON is implemented by the following recursive algorithm which adds a child d to a non leaf node v in a 2 3 tree Algorithm ADDSONW d BEGIN 1 IF v is the root of the tree add the node d properly Otherwise do the following 2 IF v has two children add d directly 3 ELSE 31 Suppose v has three children c1 c2 and c3 Partition c1 c2 c3 and d properly into two groups g1 g2 and g3 g4 Let v be the parent of g1 g2 and create a new node v and let v be the parent of g3 g4 32 Becursively call ADDSONltfatherv v END Analysis The algorithm INSERT can nd the proper place in the tree for the element 2 in 0log n time since all it needs to do is to follow a path from the root to a leaf Step 2 in the algorithm INSERT can be done in constant time The call to the procedure ADDSON in Step 3 can result in at most 0log n recursive calls to the procedure ADDSON since each call will jump at least one level up in the 2 3 tree and each recursive call takes constant time to perform Steps 1 2 and 31 in the algorithm ADDSON So Step 3 in the algorithm INSERT takes also 0logn time Therefore the overall time complexity of the algorithm INSERT is 0log 3 Minimum Given a 2 3 tree T we want to nd out the minimum element stored in the tree Recall that in a 2 3 tree the numbers are stored in leaf nodes in ascending order from left to right Therefore the problem is reduced to going down the tree always selecting the left most link until a leaf node is reached This leaf node should contain the minimum element stored in the tree Evidently the time complexity of this algorithm is Oflogn for a 2 3 tree with n leaves Algorithm MINIMUM39I39 min BEGIN IF 39I39 is a leaf THEN min 39139 ELSE cell MINIMUMltchild1T min END 4 Delete When we delete a leaf from a 2 3 tree we may leave its parent 1 with only one child If v is the root delete v and let its lone child be the new root Otherwise let p be the parent of 1 Kg has another child adjacent to v on either the right or the left and that child of 11 has three children we can transfer the proper one of those three to 1 Then 1 has two children and we are done If the children of 11 adjacent to 1 have only two children transfer the lone child of v to an adjacent sibling of v and delete 1 Should I now have only one child repeat all the above recursively with p in place of v Summarizing these discussions together we get the algorithm DELETE as shown below Where procedure DELETED is merely a driver for sub procedure DELO in which the actual work is done The variables done and 13cm in DELO are boolean ags used to indicate successful deletion and to detect the case when a node in the tree has only one child respectively In the worst case we need to traverse a path in the tree from root to a leaf to locate the node to be deleted then from that leaf node to the root in case that every non leaf node on the path has only two children in the original 2 3 tree T Thus the time complexity of DELETE algorithm for a tree with n nodes is 0log Algorithm DELEIET 1 BEGIN Cell DELT it done ison IF done is true THEN IF ison is true THEN 39I39 child1T ELSE x was not found in 39I39 handle properly Algorithm DELT it done ison BEGIN 1 IF children of T are leaves THEN process properly ie if x is found delete it update the variables done and ison 2 ELSE IN CASE 0F 1 lt LT son child1T LT lt 1 lt INT son child2T HT lt 1 lt HT son child3T 3 Call DELson it done isoni 4 IF isoni is true THEN 41 IF the node T has another child b that has three children THEN reorganize the grandchildren among the nodes son and b to make both have two children and set ison false 42 ELSE make the only child of the node son a child of a sibling of it and delete the node son from T If T has only one child then set ison true END 5 Splice Splicing two trees into one big tree is a special case of the more general operation of merging two trees Splice assumes that all the keys in one of the trees are larger than all those in the other tree This assumption effectively reduces the problem of merging the trees into pasting the smaller tree into a proper position in the larger tree Pasting the smaller tree is actually no more than performing an ADDSON operation to a proper node in the larger tree To be more speci c let T1 and T2 be 2 3 trees which we wish to splice into the 2 3 tree T where all keys in T1 are smaller than those in T2 Fur thermore assume that the height of T1 is less than or equal to that of T2 so that T1 is pasted to T2 as a left child of a leftmost node at the proper level in T2 In the case where the heights are equal both T1 and T2 are made children of the common root T otherwise the proper level in T2 is given by heightltT2 heighth 1 It is clear that the algorithm SPLICE runs in time 0log In fact the running time is proportional to the height difference heightT2 heightT1 1 The implementation of the algorithm SPLICE is given below Algorithm SPLICEKT T1 T2 Suppose that all elements in T1 are less than any elements in T2 and that the height of T1 is at most that of T2 Other cases can be dealt with similarly BEGIN IF heightT1 heightT2 THEN make T a parent of T1 and T2 ELSE WHILE heightT21 gt heightT1 D0 T2 child1T2 Call ADDSONltT2 T1 END 6 Split By splitting a given 2 3 tree T into two 2 3 trees T1 and T2 at a given element 23 we mean to split the tree T in such a way that all elements in T that are less than or equal to 2 go to T1 while the remaining elements in T go to T2 The idea is as follows as the tree is searched for 23 we store the subtrees to the left and right of the traversed path split path For this purpose two stacks are used one for each side of the split path As we go deeper into T subtrees are pushed into the proper stack Finally the subtrees in each stack are spliced together to form the desired trees T1 and T2 respectively The algorithm is given as follows Algorithm SPLITT X T1 T2 Split T into T1 and T2 such that all elements in T1 are less than or equal to x and all elements in T2 are greater than 1 The stacks Si and S2 are used to store the subtrees to the left and right of the path in the 23 tree T from the root to the leaf 1 respectively 1 BEGIN i WHILE 39I39 is not leaf D0 IF x lt LT THEN S2 lt child3T child2T 39I39 childi39139 IF LT lt x lt MT THEN Si lt childiT S2 lt child3T 39I39 child239139 IF MT lt x lt HT THEN Si lt childiT child2T 39I39 child339139 Reconstruct Ti 2 Ti lt Si 3 WHILE Si is not empty D0 t lt Si Call SPLICETi t Ti Reconstruct T2 4 T2 lt S2 5 WHILE S2 is not empty D0 5 Cell SPLICET2 T2 t END It is easy to see that the WHILE loop in Step 1 takes time 0log The analysis for the rest of the algorithm is a bit more complicated Note that the use of the stacks SI and 32 to store the subtrees guarantees that the height of a subtree closer to a stack top is less than or equal to the height of the subtree immediately deeper in the stack A crucial obserVation is that since we splice shorter trees rst which are on the top part of the stacks the difference between the heights of two trees to be spliced is always very small In fact the total time spent on splicing all these subtrees is bounded by 0log We give a formal proof as follows Assume that the subtrees stored in stack 31 are tlt2 tr l in the order from the stack top to stack bottom Let Mt be the height of the 2 3 tree 15 According to the algorithm SPLIT we have Mn 3 Mtg g g ht and no three consecutive subtrees in the stack have the same height Thus we can partition sequence 1 into segments which contains the subtrees of the same height in the sequence 5152 5q Each 5 either is a single subtree or consists of two consecutive subtrees of the same height in sequence Moreover q 3 logn Let Mai be the height of the subtrees contained in the segment 5139 We have h51lt Mag lt lt hsq The WHILE loop in Step 3 rst splices the subtrees in segment 51 into I 1 and the subtrees in segment 5 into a 2 3 tree Tim for i 2 q We have the following lemma a single 2 3 tree T1l then recursively splices the 2 3 tree T117 Lemma 2 For all i 2 q we have Imunsm hsmmlthw koltmm PROOF That Mal g hTll is fairly clear since 11 splicing subtrees in the segment 51 For i gt 2 since T1071 is obtained by is obtained by splicing the tree T1072 and the subtrees in 571 and the subtrees in 571 have height M5141 Thus the height of the 2 3 tree T1071 is at least hlfsiil Now we prove the rest inequalities Since the 2 3 tree T10 is obtained by splicing the subtrees in the segment 51 and segment 51 contains at most two subtrees both of height Mal Thus the height of the 2 3 tree T10 is at most Mal 1 which is not larger than Mag Thus the lemma is true for the case i 2 Now assume that the lemma is true for the case i l hafdhshenltheunltlthea We consider the height of the 2 3 tree T1 If the segment 5139 is a single subtree t of height Mai then splicing the tree T1071 of height at most Mai and the tree 15 of height Mai results in a 2 3 tree T1 of height at most hlfsi l which is not larger than Mai Now suppose that the segment 5139 consists of two subtrees t and 152 of height Mai Since the height of the tree T107 is at most hlfsi by the inductive hypothesis splicing the trees T107 and It results in a 2 3 tree T of height at most Moi 1 Moreover according the algorithm SPLICE if the height of T is hlfsi 1 then the root of T has only two children Now splice the trees T and 152 into the 2 3 tree Tim If the height of the tree T is smaller than hlfsi 1 then splicing T and the subtree 152 of height Mai results in a tree T1 of height at most Moi 1 which is not larger than hlt5il On the other hand if the height of the tree T39 is Moi 1 then the root of T has only two children thus splicing T and 152 will not create a new root and the resulting tree T1 has height hlfsi 1 again not larger than Moi This concludes that we always have MTV 3 Wm lt hism lt lt him This completes the induction proof and shows the correctness of the lemma 1 Now we are ready for the following theorem Theorem 3 The WHILE loop in Step 3 of the algorithm SPLIT takes time 0log PROOF First we study the complexity of constructing the 2 3 tree T1 from the 2 3 tree T1071 and the trees in the segment 5139 According to Lemma 2 we have 1 WW 3 he Thus if 5139 is a single subtree 15 then according the analysis of the time complexity of the algorithm SPLICE the time of splicing T1071 and 15 is bounded by a constant times he htTfi On the other hand if 5139 consists of two subtrees t and 152 then the time for splicing T1071 and t is again bounded by a constant times Mai hT1171 Moreover note that the height of the resulting tree T from splicing T1071 and t is either M5 or hlfsi l and that the height of the subtree 152 is Moi Thus splicing T and 152 takes only constant time 10 Therefore in this case the total time to construct T1 from T1071 and 5139 is bounded by a constant times my 1593 1 Therefore to construct the nal 2 3 tree T101 the total time of the WHILE loop in Step 3 is bounded by a constant times 1 2045 hT1171 1 2 By Lemma 2 we have hitsiil g hf TlU U Thus the time complexity of the WHILE loop in Step 3 is bounded by a constant times q 2045 h5 71 1 2 which is equal to hsq Mal q Since all quantities hsq Mal and q are bounded by logn we conclude that the WHILE loop in Step 3 takes time 0logn D The same proof shows that the WHILE loop in Step 5 also takes time 0log In conclusion the algorithm SPLIT takes time 0log

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

#### "There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

#### "I made $350 in just two days after posting my first study guide."

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

#### "Their 'Elite Notetakers' are making over $1,200/month in sales by creating high quality content that helps their classmates in a time of need."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.