Handbook of Data Structures and Applications, 2nd Edition

34

Data Structures for Sets^*

Rajeev Raman

University of Leicester

34.1Introduction

Models of Computation

34.2Simple Randomized Set Representations

The Hash Trie•Some Remarks on Unique Representations

34.3Equality Testing

34.4Extremal Sets and Subset Testing

Static Extremal Sets•Dynamic Set Intersections and Subset Testing

34.5The Disjoint Set Union-Find Problem

The Classical Union-Find Problem and Variants

34.6Partition Maintenance Algorithms

34.7Conclusions

References

34.1Introduction

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 F of sets, where all sets ...