Data Structures for Sets*

Rajeev Raman

University of Leicester


Models of Computation

34.2Simple Randomized Set Representations

The Hash TrieSome Remarks on Unique Representations

34.3Equality Testing

34.4Extremal Sets and Subset Testing

Static Extremal SetsDynamic Set Intersections and Subset Testing

34.5The Disjoint Set Union-Find Problem

The Classical Union-Find Problem and Variants

34.6Partition Maintenance Algorithms




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 ...

Get Handbook of Data Structures and Applications, 2nd Edition now with the O’Reilly learning platform.

O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.