O'Reilly logo

Handbook of Data Structures and Applications, 2nd Edition by Sartaj Sahni, Dinesh P. Mehta

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

34

Data Structures for Sets*

Rajeev Raman

University of Leicester

34.1Introduction

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

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

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required