Page 1 Sets 1 Sets Page 2 Sets 1 Sets Sets 2 Storing a Set in a List We can implement a set with a list Elements are stored sorted according to some canonical ordering The space used is O(n) Ø List Nodes storing set elements in order Set elements Page 3 Sets 1 Sets Sets 2 Storing a Set in a List We can implement a set with a list Elements are stored sorted according to some canonical ordering The space used is O(n) Ø List Nodes storing set elements in order Set elements Sets 3 Generic Merging (§10.2) Generalized merge of two sorted lists A and B Template method genericMerge Auxiliary methods ? aIsLess ? bIsLess ? bothEqual Runs in O(n A + n B ) time provided the auxiliary methods run in O(1) time Algorithm genericMerge(A, B) S ? empty sequence while ¬A.isEmpty() ? ¬B.isEmpty() a ? A.first().element(); b ? B.first().element() if a < b aIsLess(a, S); A.remove(A.first()) else if b < a bIsLess(b, S); B.remove(B.first()) else { b = a } bothEqual(a, b, S) A.remove(A.first()); B.remove(B.first()) while ¬A.isEmpty() aIsLess(a, S); A.remove(A.first()) while ¬B.isEmpty() bIsLess(b, S); B.remove(B.first()) return S Page 4 Sets 1 Sets Sets 2 Storing a Set in a List We can implement a set with a list Elements are stored sorted according to some canonical ordering The space used is O(n) Ø List Nodes storing set elements in order Set elements Sets 3 Generic Merging (§10.2) Generalized merge of two sorted lists A and B Template method genericMerge Auxiliary methods ? aIsLess ? bIsLess ? bothEqual Runs in O(n A + n B ) time provided the auxiliary methods run in O(1) time Algorithm genericMerge(A, B) S ? empty sequence while ¬A.isEmpty() ? ¬B.isEmpty() a ? A.first().element(); b ? B.first().element() if a < b aIsLess(a, S); A.remove(A.first()) else if b < a bIsLess(b, S); B.remove(B.first()) else { b = a } bothEqual(a, b, S) A.remove(A.first()); B.remove(B.first()) while ¬A.isEmpty() aIsLess(a, S); A.remove(A.first()) while ¬B.isEmpty() bIsLess(b, S); B.remove(B.first()) return S Sets 4 Using Generic Merge for Set Operations Any of the set operations can be implemented using a generic merge For example: ? For intersection: only copy elements that are duplicated in both list ? For union: copy every element from both lists except for the duplicates All methods run in linear time. Page 5 Sets 1 Sets Sets 2 Storing a Set in a List We can implement a set with a list Elements are stored sorted according to some canonical ordering The space used is O(n) Ø List Nodes storing set elements in order Set elements Sets 3 Generic Merging (§10.2) Generalized merge of two sorted lists A and B Template method genericMerge Auxiliary methods ? aIsLess ? bIsLess ? bothEqual Runs in O(n A + n B ) time provided the auxiliary methods run in O(1) time Algorithm genericMerge(A, B) S ? empty sequence while ¬A.isEmpty() ? ¬B.isEmpty() a ? A.first().element(); b ? B.first().element() if a < b aIsLess(a, S); A.remove(A.first()) else if b < a bIsLess(b, S); B.remove(B.first()) else { b = a } bothEqual(a, b, S) A.remove(A.first()); B.remove(B.first()) while ¬A.isEmpty() aIsLess(a, S); A.remove(A.first()) while ¬B.isEmpty() bIsLess(b, S); B.remove(B.first()) return S Sets 4 Using Generic Merge for Set Operations Any of the set operations can be implemented using a generic merge For example: ? For intersection: only copy elements that are duplicated in both list ? For union: copy every element from both lists except for the duplicates All methods run in linear time. Sets 5 Set Operations We represent a set by the sorted sequence of its elements By specializing the auxliliary methods he generic merge algorithm can be used to perform basic set operations: ? union ? intersection ? subtraction The running time of an operation on sets A and B should be at most O(n A + n B ) Set union: ? aIsLess(a, S) S.insertFirst(a) ? bIsLess(b, S) S.insertLast(b) ? bothAreEqual(a, b, S) S. insertLast(a) Set intersection: ? aIsLess(a, S) { do nothing } ? bIsLess(b, S) { do nothing } ? bothAreEqual(a, b, S) S. insertLast(a)Read More