ABSTRACT

Sets are a fundamental concept in computer science: the study of algorithms and data structures for maintaining them were among the earliest developments in data structures. Our focus will be on problems that involve maintaining a family https://www.w3.org/1998/Math/MathML"> F https://s3-euw1-ap-pe-df-pch-content-public-u.s3.eu-west-1.amazonaws.com/9781315119335/1d570ce3-c77a-4782-aa80-1792ea169a3f/content/inline-math5_34_1.jpg" xmlns:xlink="https://www.w3.org/1999/xlink"/> of sets, where all sets are drawn from a universe U of elements. We do not assume that there is a particular natural order among the elements of U, and in particular do not focus on data structuring problems on sets where the operations explicitly assume such an order (e.g., priority queues). A base repertoire of actions is as follows: https://www.w3.org/1998/Math/MathML"> create ( ) Create a new empty set, add it to F and return the name of the set. destroy ( A ) If  A = ∅  then remove  A  from  F . If  A ≠ ∅ , flag an error. insert ( x , A ) Set  A ← A ∪ { x } . delete ( x , A ) Set  A ← A − { x } . } https://s3-euw1-ap-pe-df-pch-content-public-u.s3.eu-west-1.amazonaws.com/9781315119335/1d570ce3-c77a-4782-aa80-1792ea169a3f/content/math5_34_1.jpg" xmlns:xlink="https://www.w3.org/1999/xlink"/> The following operation is fundamental for data structuring problems involving sets in general, but plays only an auxiliary role in this chapter: https://www.w3.org/1998/Math/MathML"> member ( x , A ) Returns `true' if  x ∈ A  and `false' otherwise. https://s3-euw1-ap-pe-df-pch-content-public-u.s3.eu-west-1.amazonaws.com/9781315119335/1d570ce3-c77a-4782-aa80-1792ea169a3f/content/math5_34_2.jpg" xmlns:xlink="https://www.w3.org/1999/xlink"/> If we take only insert, delete and member, we get the dictionary problem, covered in Part III. The base repertoire plus member is essentially no more difficult, as it represents the problem of maintaining a collection of independent dictionaries over a common universe. In this chapter, we focus on adding operations to this base repertoire that take two or more sets as arguments. For example, we could consider the standard set-theoretic operations on two sets A and B: https://www.w3.org/1998/Math/MathML"> A op B , op ∈ { ∪ , ∩ , − } . https://s3-euw1-ap-pe-df-pch-content-public-u.s3.eu-west-1.amazonaws.com/9781315119335/1d570ce3-c77a-4782-aa80-1792ea169a3f/content/umath5_34_1.jpg" xmlns:xlink="https://www.w3.org/1999/xlink"/> A data structure may support only an enumerative form of these operations, whereby the result of A op B is, in essence, some kind of enumeration of the set A op B. This result may not be in the same representation as A or B, and so one may not be able operate on it (e.g., ((A op B) op C) may not involve just two executions of op). The complexity of the algorithms will generally be measured in terms of the following parameters: https://www.w3.org/1998/Math/MathML"> n = ∑ A ∈ F | A |  (the total size of all sets in the family) m = | U |  (the size of the universe) k = | F |  (the number of sets in the family) https://s3-euw1-ap-pe-df-pch-content-public-u.s3.eu-west-1.amazonaws.com/9781315119335/1d570ce3-c77a-4782-aa80-1792ea169a3f/content/math5_34_3.jpg" xmlns:xlink="https://www.w3.org/1999/xlink"/>