Sets as a data structure

The set as an abstract type (membership, add, remove, union, intersection, difference; no duplicates, no order) and its three implementations: hash table, sorted tree, bit vector, with the cost of each operation.

22 cards
5 topics
Free

Study this deck

The outline, topic by topic

Each topic is weighted the way the exam weighs it.

Concepts
Questions
Sort and link
Scenarios
Understand

A few cards from the deck

Set: what is it?
Show the answer
A collection of distinct values where you only ask: is a value in it, add, remove. No value appears twice and no order is guaranteed.
Adding a value already present changes nothing. It is an abstract type: a table, a tree or a bit vector implements it.
What does this program print?

```python
a = {1, 2, 2, 3}
b = {3, 4}
print(len(a), a & b, a - b)
`
- 3 {3} {1, 2}
- 4 {3} {1, 2}
- 3 {3, 4} {1, 2, 2}
- 3 {1, 2} {3}
Show the answer
3 {3} {1, 2}
Duplicates vanish at construction: a is {1, 2, 3}, of size 3. The intersection keeps what is shared (3), the difference what is in a alone (1 and 2).
A set contains no …: adding the same value twice leaves its size unchanged the second time.
Show the answer
A set contains no duplicate: adding the same value twice leaves its size unchanged the second time.
len({1, 2, 2, 3}) is 3. This is the most common use: removing duplicates from a list with set(list).
Union, intersection, difference: what is it?
Show the answer
The three ways to combine two sets: all elements of either, those in both at once, those of the first not in the second.
In Python: a | b, a & b and a - b. The difference is not symmetric: a - b and b - a usually differ.
An application keeps the identifiers of processed orders and must, on each request, display the identifiers in increasing order. Which set implementation to choose?
- A tree set, which is walked in order
- A hash set: insertion order is preserved
- A bit vector, whatever the range of identifiers
- A hash set sorted on each request, for an O(1) cost
Show the answer
A tree set, which is walked in order
A sorted tree returns elements in order without effort. A hash set offers no order to rely on, and sorting it on each request costs O(n log n). A bit vector only suits a small, bounded range of integers.

Study this deck