Section 9.1. Working with Sets

Chapter 9. More Advanced Data Structures

A graphic representation of data abstracted from the banks of every computer in the human system. Unthinkable complexity. Lines of light ranged in the nonspace of the mind, clusters and constellations of data. Like city lights, receding.

William Gibson

There are, of course, more complex and interesting data structures than arrays, hashes, and their cousins. Some of the ones we'll look at here have direct or indirect support in Ruby; others are "roll-your-own" for the most part. Fortunately, Ruby simplifies the construction of custom data structures.

The mathematical set can be dealt with by means of arrays, as we've already seen. But recent versions of Ruby have a Set class that serves this purpose well.

Stacks and queues are two common data structures in computer science. The first edition of this book paid rather too much attention to them; if you want to know about their uses in general, I have outlined a few of those here. For the rest, there are numerous first-year computer science books.

Trees are useful from the perspective of sorting, searching, and simply representing hierarchical data. We cover binary trees here, with a few notes about multiway trees.

The generalization of a tree is a graph. A graph is simply a collection of nodes joined by edges that may have weights or directions associated with them. These are useful in many different areas of problem-solving such as networking and knowledge engineering.

But sets are the easiest topic. We'll look at sets first.