This chapter provides knowledge of sets. Data structures and algorithms in java provides an introduction to data structures and algorithms, including their design, analysis, and implementation. | Sets and Multimaps 3/19/14 Presentation for use with the textbook Data Structures and Algorithms in Java, 6th edition, by M. T. Goodrich, R. Tamassia, and M. H. Goldwasser, Wiley, 2014 Sets and Multimaps © 2014 Goodrich, Tamassia, Goldwasser Sets and Multimaps 1 Definitions ! A set is an unordered collection of elements, without duplicates that typically supports efficient membership tests. n Elements of a set are like keys of a map, but without any auxiliary values. ! A multiset (also known as a bag) is a set-like container that allows duplicates. ! A multimap is similar to a traditional map, in that it associates values with keys; however, in a multimap the same key can be mapped to multiple values. n For example, the index of a book maps a given term to one or more locations at which the term occurs. © 2014 Goodrich, Tamassia, Goldwasser Sets and Multimaps 2 1 Sets and Multimaps 3/19/14 Set ADT © 2014 Goodrich, Tamassia, Goldwasser Sets and Multimaps 3 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) Nodes storing set elements in order List ∅ Set elements © 2014 Goodrich, Tamassia, Goldwasser Sets and Multimaps 4 2 Sets and Multimaps 3/19/14 Generic Merging ! Generalized merge Algorithm genericMerge(A, B) ! ! of two sorted lists A and B Template method genericMerge Auxiliary methods n n n aIsLess bIsLess bothAreEqual ! Runs in O(nA + nB) time provided the auxiliary methods run in O(1) time © 2014 Goodrich, Tamassia, Goldwasser S ← empty sequence while ¬() ∧ ¬() a ← ().element(); b ← ().element() if a < b aIsLess(a, S); (()) else if b < a bIsLess(b, S); (()) else { b = a } bothAreEqual(a, b, S) (()); (()) while ¬() aIsLess(a, S); (()) while ¬() bIsLess(b, S); (()) return .
