Chapter 13: Sets and Disjoint Sets

13.1The set ADT

A data structure can be described at two levels: what it does — its operations and their effects — and how, meaning its memory layout and the steps of each operation. A description of the first kind is an abstract data type (ADT). This section treats the set as an ADT; hash tables, trees, and bit vectors come in Section 13.2.

13.1.1What is a set?

Think of a class roll. Each name appears once — writing it twice adds nothing — and the order doesn't matter. The only question is "Is Alice in this class?" The mathematical set captures exactly this idea.

Two rules stand out. First, no duplicates: adding an element already present leaves the set unchanged, whereas a list accepts the same value any number of times. Second, sets are unordered: there is no "first" or "third" element, so the ADT has no indexed access. Some implementations visit elements in a particular order, but that is a by-product of the implementation, not part of the definition.

Above all, a set must answer membership queries quickly. An array answers by scanning, in O(n); a good set implementation takes constant time on average, or O(log n). Most of this chapter is about how.

Figure 13.1 shows both rules: add(2) on S = {7, 2, 9, 5} finds 2 already there, so the size stays 4, and the elements are scattered because a set has no "before" or "after."

Sets do three kinds of everyday work:

• Removing duplicates. Add every word of a text to a set and only the distinct words remain. In Java a list becomes a set in one line: new HashSet<>(list).
• Membership. Banned users, visited nodes, and the valid words of a dictionary are sets, queried on every request.
• Set algebra. Mutual friends are the intersection of two friend sets; a site's tags are the union of its posts' tag sets.

13.1.2Set operations

Four basic operations, or set operators, are defined on sets A and B:

• Union, A ∪ B: the elements in A or in B (or in both).
• Intersection, A ∩ B: the elements in both A and B.
• Difference, A − B: the elements in A but not in B.
• Subset, A ⊆ B: every element of A is also in B. This is a yes-or-no question rather than an operation.

Figure 13.2 draws them as Venn diagrams, each set a circle containing its elements: a union shades both circles, an intersection only the lens-shaped overlap, a difference cuts the overlap out of A, and a subset lies entirely inside the other circle.

Union and intersection are commutative — A ∪ B = B ∪ A, A ∩ B = B ∩ A — but difference is not: A − B and B − A usually differ.

The check uses the inclusion–exclusion principle, |A ∪ B| = |A| + |B| − |A ∩ B|: common elements are counted in both sizes, so they are subtracted once.

13.1.3The Set interface in Java

In Java the set ADT is the interface java.util.Set<E>, implemented by HashSet, LinkedHashSet, and TreeSet. Set extends Collection with one contract: no two elements are equal, as decided by equals (in a sorted set, by compare).

A small but valuable detail: add reports whether it added anything, returning true for a new element and false for one already there. That single bit is the basis of the duplicate finder in Section 13.1.4. Likewise, remove returns true only if it removed something.

The set operations are addAll, retainAll, and removeAll. This code repeats Example 13.1:

Set<Integer> a = new HashSet<>(List.of(1,2,3,4,5));
Set<Integer> b = new HashSet<>(List.of(3,4,5,6,7));
Set<Integer> uni = new HashSet<>(a);
uni.addAll(b);     // [1..7]
Set<Integer> both = new HashSet<>(a);
both.retainAll(b); // [3, 4, 5]
Set<Integer> diff = new HashSet<>(a);
diff.removeAll(b); // [1, 2]
a.containsAll(b);  // false

The first two lines build two HashSets. The third copies a into uni, and uni.addAll(b) adds B's elements: 3, 4, 5 are already there, 6 and 7 are new, giving 1 through 7. For the intersection, retainAll(b) on another copy deletes everything not in B, leaving [3, 4, 5]; for the difference, removeAll(b) deletes everything in B, leaving [1, 2]. Finally, a.containsAll(b) asks whether B ⊆ A; 6 is not in A, so the answer is false.

Their cost depends on the implementation. In a HashSet, uni.addAll(b) does one add, O(1) on average, per element of B, plus O(|A|) for the copy; retainAll and removeAll call contains on the other set for each element of the copy. So with hash sets, union, intersection, and difference take O(n + m) on average.

13.1.4Code trace: the first repeat via add

Suppose we want the first value in an array, read left to right, that has appeared before. Without a set, each element is compared with all earlier ones: two nested loops and up to n(n − 1)/2 comparisons, O(n²). With a set, we collect the elements seen so far and test each new one with a single add:

int firstRepeat(int[] a) {
  Set<Integer> seen = new HashSet<>();
  for (int x : a) {
    if (!seen.add(x))   // not added?
      return x;            // already there: a repeat
  }
  return -1;               // no repeats
}

The loop body does two jobs in one line. seen.add(x) adds a new element and returns true; the ! makes the condition false, and the loop continues. For an element seen before, add returns false without changing the set, the condition holds, and the method returns that element. With no repeats, the loop ends and the method returns -1.

This is shorter than contains followed by add, and it searches the bucket once instead of twice.

Let's trace a = [4, 7, 2, 7, 4]. HashSet uses 16 buckets, and an element's bucket is the last four bits of its hash code, hash(x) & 15. An Integer's hash code is its value, so 4 goes to bucket 4, 7 to bucket 7, and 2 to bucket 2.

In the first three passes the buckets are empty, so each add succeeds after one bucket check. In the fourth, bucket 7 already holds 7: add returns false and the method returns 7. The last element, 4, is never examined.

Each element costs one add, O(1) on average, so the method runs in O(n) on average with no nested loop. The price is up to O(n) extra memory for the set — the typical trade of memory for time.

13.2Implementing sets

The set ADT says only "what"; each implementation makes some operations fast and others slow. This section examines four — hash table, balanced binary search tree, sorted array, and bit vector — and ends with a table on which to choose when.

13.2.1Set classes in Java

Java provides three Set classes. All keep the same contract — no duplicates; add, remove, contains — and differ in internal structure and hence in iteration order.

To see the difference, add the same four words to all three:

for (String s : List.of("lemon", "peach", "fig", "lemon")) {
    hash.add(s);  linked.add(s);  tree.add(s);
}
// HashSet       → [lemon, fig, peach]   (bucket order: depends on hash)
// LinkedHashSet → [lemon, peach, fig]   (insertion order)
// TreeSet       → [fig, lemon, peach]   (alphabetical)

"lemon" is added twice but appears once: the second add("lemon") returns false in all three sets. The orders differ, though. HashSet lists elements bucket by bucket; in a 16-bucket table "lemon" lands in bucket 2, "fig" in 5, and "peach" in 8, giving [lemon, fig, peach] — neither insertion nor alphabetical order, and liable to change when the table is resized. LinkedHashSet also threads its elements on a doubly linked list and iterates over it, giving insertion order. TreeSet keeps a search tree and returns elements sorted, by an inorder traversal.

Hence the rule: HashSet when order doesn't matter, LinkedHashSet for insertion order, TreeSet for sorted access. LinkedHashSet pays for order with two extra references per element; TreeSet pays in time, O(log n) instead of O(1).

13.2.2Hash-based sets

A hash-based set stores its elements in a hash table, an array of m cells called buckets. An element's bucket is computed from its hash code, an integer derived from the element (equal elements have equal hash codes), usually as i = hashCode(x) mod m.

A map's hash table keeps a key–value pair per entry; a set needs only the keys. Java's HashSet in fact wraps a HashMap, storing each element as a key with the same dummy object as its value.

Two elements landing in the same bucket is a collision: with 7 buckets, 12 and 19 both go to bucket 5, since 12 mod 7 = 19 mod 7 = 5. The simplest remedy is separate chaining: each bucket holds a list (a chain) of the elements that land there.

Figure 13.4 adds 12, 25, 7, 19, and 12 again to an empty 7-bucket table. 12 goes to bucket 5, 25 to bucket 4 (25 mod 7 = 4), and 7 to bucket 0. 19 also maps to bucket 5, which holds 12 — a collision — so 19 is appended to the chain. The second add(12) scans bucket 5, finds 12, and returns false without adding anything. This check is what makes the structure a set.

Hashing is fast because contains(26) looks only at bucket 26 mod 7 = 5: it compares 26 with 12 and 19 and returns false, never touching buckets 0 and 4. However large the table, a search is confined to one chain.

How long are the chains? If n elements spread evenly over m buckets, the average length is n / m, the load factor λ; here λ = 4/7 ≈ 0.57. When λ exceeds a threshold (0.75 in Java), the table roughly doubles its buckets and redistributes the elements, so λ stays bounded and add, contains, and remove take O(1) on average.

This assumes a hash function that spreads elements well. One that sends everything to the same bucket turns the table into a single chain, and every operation costs O(n).

13.2.3Code trace: add and contains

The two basic methods of a chained hash set are short. The fields are m, the number of buckets; bucket, an array of integer lists; and n, the number of elements. Assuming non-negative elements, the bucket number is simply x % m.

// fields: List<Integer>[] bucket; n; m = 7
boolean add(int x) {          // x ≥ 0
  int i = x % m;               // bucket no.
  for (int y : bucket[i])
    if (y == x) return false;  // already there
  bucket[i].add(x);
  n++;
  return true;
}
boolean contains(int x) {
  int i = x % m;
  for (int y : bucket[i])
    if (y == x) return true;
  return false;
}

add(x) computes i = x % m and walks that bucket's chain. If some y equals x, the element is already present and the method returns false. Otherwise x is appended, n is incremented, and the method returns true. contains(x) does the same scan and returns true or false. Both look at a single chain.

In the first three adds the buckets are empty, so the loop never runs. In add(19) it runs once (12 ≠ 19), and 19 is appended, leaving two elements in bucket 5. In the second add(12), the first comparison succeeds, the method returns false, and n stays 4.

The two contains calls contrast failure and success: contains(26) scans the whole two-element chain in vain, while contains(19) finds a match at the second element. Both look only at bucket 5.

Cost. Computing the bucket is constant time, and a chain scan is proportional to the chain's length, which averages the load factor n / m. With the load factor held constant, both methods are O(1) on average. Memory is O(n + m).

13.2.4Tree-based (sorted) sets

A hash table knows nothing about order. "What is the smallest element?" or "the largest below 17?" can be answered only by scanning everything. When such questions are frequent, the set is implemented with a balanced binary search tree.

In a binary search tree, a node's left subtree holds smaller elements and its right subtree larger ones, so a search from the root discards half the tree at each step. A balanced tree has height O(log n), making search, insertion, and deletion O(log n). Java's TreeSet uses a red-black tree.

Sorted storage has two consequences. An inorder traversal (left subtree, node, right subtree) yields the elements in increasing order — 5, 10, 15, 20, 25, 30, 40 for Figure 13.6. And order-based queries also take O(log n); TreeSet offers them through the NavigableSet interface.

To find floor(17): at the root, 20 > 17, so go left. At 10, 10 ≤ 17: 10 is a candidate; go right for a larger one. At 15, 15 ≤ 17: the candidate becomes 15; go right. 15 has no right child, so the answer is 15. The search is one descent, as long as the tree's height. ceiling(17) follows the same path with the opposite rule and finds 20. A value in the set is its own floor and ceiling.

subSet(10, 30) includes the lower bound and excludes the upper, Java's usual half-open convention. A range query costs O(log n) to find the start plus O(k) for k results.

A tree-based set needs comparable elements: the element class implements Comparable, or the set is given a Comparator. TreeSet treats two elements as equal when compare(a, b) == 0, not by equals.

13.2.5Union and intersection of sorted arrays

The plainest set implementation is a sorted array. Membership is a binary search, O(log n); insertion and deletion shift elements, O(n). In return, union and intersection of two sorted sets are very efficient, using the merge step of merge sort: one pointer per array, both advancing in a single pass. Goodrich, Tamassia, and Goldwasser call this the generic merge.

void unionIntersection(int[] a, int[] b,
    List<Integer> uni, List<Integer> both) {
  int i = 0, j = 0;
  while (i < a.length && j < b.length) {
    if (a[i] < b[j]) uni.add(a[i++]);
    else if (a[i] > b[j]) uni.add(b[j++]);
    else {                     // common element
      uni.add(a[i]);  both.add(a[i]);
      i++;  j++;
    }
  }
  while (i < a.length) uni.add(a[i++]);
  while (j < b.length) uni.add(b[j++]);
}

Pointers i and j start at 0 in a and b. While both arrays have elements left, each pass compares a[i] with b[j]:

• If a[i] < b[j], a[i] is only in a: b is sorted, so nothing from b[j] on can equal it. It goes into the union and i advances.
• If a[i] > b[j], symmetrically, b[j] goes into the union and j advances.
• If they are equal, the element is common: it goes into the union once and into the intersection, and both pointers advance.

When one array runs out, the intersection is complete, and whatever is left in the other array belongs to the union alone. At most one of the two trailing loops does any work.

Let's trace the method with a = [1, 3, 5, 7, 9] and b = [3, 4, 5, 8].

The main loop runs six times. At step 7, b is exhausted and the intersection is [3, 5]; the first trailing loop adds the remaining 9 to the union, and the second never runs. Both outputs come out sorted, so they can serve as sorted-array sets in turn.

Cost. Every pass moves at least one pointer forward and none moves back, so with |a| = n and |b| = m there are at most n + m steps: O(n + m). Unsorted lists need a scan of the other list per element, O(n · m). The difference A − B uses the same skeleton, keeping only the a[i] < b[j] elements and the leftovers of a.

13.2.6Comparing the implementations

Table 13.8 compares an unsorted list with the three implementations, for |A| = n and |B| = m.

An unsorted list scans everything for membership, and insertion must search first to rule out a duplicate; a union searches A for each element of B, O(n · m). A sorted array searches in O(log n) but shifts elements on insertion and deletion, O(n); two pointers give the set operations in O(n + m). A hash table does single-element operations in constant average time, and a union — contains + add per element of B, plus the copy — in O(n + m); but it knows no order, so sorted iteration needs a sort (O(n log n)) and the minimum or a floor needs a full scan. A balanced tree does every single-element operation in O(log n); a union inserts B's m elements into a tree of at most n + m, O(m log(n + m)), and an inorder traversal gives sorted output in O(n).

In practice: default to a hash table, which gives the fastest membership test when order doesn't matter. When order matters, use a tree: everything is O(log n), and sorted queries come free. A sorted array suits a set that is built once, then only queried, with frequent unions or intersections.

13.2.7Sets as bit vectors

If the elements come from a small range of integers, a far more compact representation exists. The set of all possible elements is the universe; for a universe {0, 1, …, U − 1}, store U bits, with bit i set exactly when i is in the set. This is a bit vector.

With at most 32 possible elements, the set fits in one int, and each operation is a single instruction:

• Insertion: a |= 1 << x. 1 << x is a mask with only bit x set; OR sets that bit.
• Membership: (a >> x & 1) == 1. The shift brings bit x to the right end; & 1 isolates it.
• Deletion: a &= ~(1 << x). The inverted mask is 1 except at bit x, so AND clears just that bit.
• Union, intersection, difference: a | b, a & b, a & ~b. Each bit is one element, so bitwise OR, AND, and NOT are exactly the set operations.
• Size: Integer.bitCount(a) counts the 1 bits.

For larger universes, java.util.BitSet keeps the bits in a long array of 64-bit words. Single-element operations stay O(1); set operations go word by word, O(U / 64).

A bit vector's memory depends on the universe, not on the number of elements: U bits. A million-element universe takes 10⁶ / 8 = 125,000 bytes, about 122 KB, against tens of megabytes for a HashSet of a million Integers. For a large universe and a sparse set the balance flips: 3 elements from U = 10⁹ need about 119 MB as a bit vector but a few hundred bytes in a hash set, which is then the right choice.

13.2.8Code trace: set algebra with bit operations

This code builds a = {1, 3, 4} and b = {3, 5} as bit vectors, computes their union, intersection, and difference, and tests whether 3 is in a.

int a = 0, b = 0;
for (int x : new int[]{1, 3, 4})
  a |= 1 << x;          // set bit x
for (int x : new int[]{3, 5})
  b |= 1 << x;
int uni = a | b;        // union
int both = a & b;       // intersection
int diff = a & ~b;      // difference
boolean has3 = (a >> 3 & 1) == 1;

The first rows build the sets: 1 << x is a mask with only bit x set (2, 8, 16), and OR adds it to a, which becomes 2, 10, then 26. Likewise b = 8 + 32 = 40.

The union keeps every bit set in either number: bits 1, 3, 4, 5, value 58, set {1, 3, 4, 5}. The intersection (AND) keeps bits set in both: only bit 3, value 8, set {3}. The difference takes two steps: ~b flips every bit of b, clearing bits 3 and 5 and setting the rest, and a & ~b keeps the bits of a not in b, bits 1 and 4: value 18, set {1, 4}.

The last line tests membership. Shifting a = 0001 1010 right by three gives 0000 0011, with bit 3 at the right end; & 1 isolates it, and the result 1 means 3 is in the set. No operation loops; each is O(1).

13.3Multisets and multimaps

Forbidding duplicates usually helps, but sometimes duplicates are the point. How often does "and" occur in a text? How many apples are in the basket? How many votes did a candidate get? Counting questions like these call for an extension of the set.

13.3.1Multisets

In M = {a, a, b, c, c, c}, a has multiplicity 2, b 1, and c 3. Writing each distinct element once with its multiplicity, {a:2, b:1, c:3}, carries the same information. That is the natural implementation: an element → counter map, which with a hash table reduces every operation to one key lookup.

size() counts repeats: M has 3 distinct elements but size 6. Rather than summing the counters each time, the implementation keeps a counter n, updated by every insertion and removal, so size() is O(1).

Word frequencies, shopping-cart items, and vote counts are classic multisets. Whether two words are anagrams can be tested by comparing their letter multisets.

13.3.2A multiset in Java

Java's library has no multiset class, but one is easy to build on a HashMap<E, Integer>:

class Multiset<E> {
    private final Map<E, Integer> counts = new HashMap<>();
    private int n = 0;                                // number of elements, repeats included
    void add(E e) { counts.merge(e, 1, Integer::sum); n++; }  // 1 if absent, else +1
    int count(E e) { return counts.getOrDefault(e, 0); }
    boolean remove(E e) {
        Integer c = counts.get(e);
        if (c == null) return false;                     // e is absent
        if (c == 1) counts.remove(e);                    // counter would hit 0: delete entry
        else counts.put(e, c - 1);
        n--;
        return true;
    }
    int size() { return n; }
}

counts maps each distinct element to its counter; n counts all elements, repeats included.

• add(e) calls counts.merge(e, 1, Integer::sum), which inserts e with value 1 if absent and otherwise combines old and new values with the given function — addition, so the counter goes up by one. Then n is incremented.
• count(e) uses getOrDefault(e, 0), returning 0 rather than null for an absent element — which, in a multiset, does occur 0 times.
• remove(e) reads the counter. If it is null, the element is absent and the method returns false. A counter of 1 would drop to 0, so the entry is deleted; a larger counter is decremented. Either way n drops and the method returns true.
• size() simply returns n.

After add("a"); add("a");, count("a") returns 2, whereas a Set would ignore the second call and record only that "a" is present. For sorted iteration, use a TreeMap<E, Integer>: operations rise to O(log n), but elements come out in order.

13.3.3Code trace: Multiset counters

We trace these calls on an empty Multiset<String>: add("a"), add("b"), add("a"), add("c"), count("a"), remove("a"), remove("b"), remove("x"), count("b"). The method bodies are:

void add(E e) {
  counts.merge(e, 1, Integer::sum);  n++;
}
int count(E e) {
  return counts.getOrDefault(e, 0);
}
boolean remove(E e) {
  Integer c = counts.get(e);
  if (c == null) return false;
  if (c == 1) counts.remove(e);
  else counts.put(e, c - 1);
  n--;
  return true;
}

The third row shows the difference from a set: merge adds 1 to the old counter, making it 2, and n rises to 3, where a Set would not have changed. The two successful removes take different branches: "a" has counter 2, so the else branch lowers it to 1 and the entry stays; "b" has counter 1, so its entry is deleted. For the absent "x", counts.get returns null and the method returns false at once. Finally, count("b") returns 0: a removed element looks like one never added. The result is M = {a, c}, n = 2.

Cost. Each method touches the map once (remove at most twice), O(1) on average with hashing. Memory is O(d) for d distinct elements: a word occurring millions of times still takes one entry.

13.3.4Multimaps

A multiset records how many times an element occurs. Sometimes we need the repeats themselves: to know which students take a course, each course key must map to a list of students.

Java has no multimap class either; a Map<K, List<V>> mapping each key to a list of values does the job:

Map<String, List<String>> m = new HashMap<>();
void put(String k, String v) {   // create an empty list if absent
  m.computeIfAbsent(k, x -> new ArrayList<>()).add(v);
}
List<String> get(String k) {
  return m.getOrDefault(k, List.of());
}

In put, computeIfAbsent(k, x -> new ArrayList<>()) returns the key's list, first creating and storing an empty one if the key is absent; add(v) then appends to it. For a missing key, get returns an unmodifiable empty list (List.of()) instead of null, sparing the caller a null check.

The map in Figure 13.11 takes six puts: (CS201, Ann), (CS201, Dana), (CS201, Ben), (CS203, Dana), (MATH101, Ben), (MATH101, Carol). get("CS201") returns [Ann, Dana, Ben] and get("PHYS101") an empty list. The size is the number of pairs, 6; there are 3 keys.

Cost. With hashing, put and get are O(1) on average (get returns the list without copying). remove(k, v) finds the list in O(1), then searches it: O(1 + list length). In short, a multiset keeps counts; a multimap keeps the values themselves.

13.4Disjoint sets and Union-Find

So far we have worked with one set, or two. Some problems involve many sets that merge over time: groups of friends in a social network, cities linked by roads, adjacent same-colored pixels in an image. They all ask "Are these two items in the same group?" and "Merge these two groups." This section builds a structure that answers both very quickly.

13.4.1Disjoint sets

The representative is the set's "name." Which element it is doesn't matter, as long as find returns the same one for every element of the set; then "same set?" takes two finds and a comparison.

Union-Find stores each set as a tree in which each node points only to its parent, so arrows run from child to ancestor. The root points to itself and represents the set. Several trees form a forest.

In Figure 13.12, find(6) follows 6 → 5 → 2 → 1 and stops at 1, which points to itself. find(8) follows 8 → 4 → 3 and returns 3. Since 1 ≠ 3, 6 and 8 are in different sets. Merging the sets takes one new arrow: point one root at the other, say 1 at 3.

These are not search trees: nodes have no smaller–larger order and any number of children. A tree's only job is to connect the elements of a set to a common root.

13.4.2The magnet example

Picture 14 strong magnets on a table. Two magnets that touch stick together for good; stuck magnets form a group, and a magnet touching any member of another group merges the two groups. As merging goes on, we want to know at any moment: "Are these two magnets in the same group?"

Number the magnets 1 to 14. Initially each is in its own group: 14 disjoint sets, with find(x) = x for every x. A touch is a union; "same group?" compares two finds.

Each successful merge reduces the number of groups by exactly one. In union(2, 3), the lone 2 joins 3's group {3, 4}, making {2, 3, 4}. Three merges then build {9, 10, 13, 14}, and three more {5, 7, 11, 12}, leaving five groups: four larger ones and 1 on its own.

Are 4 and 10 in the same group? find(4) returns the representative of {2, 3, 4} and find(10) that of {9, 10, 13, 14}; they differ, so no. union(4, 10) then merges the two groups. Eventually all magnets end up in one group with a single root.

Note that Union-Find remembers only who is in which group, not how the groups formed: whether 2 touched 3 or 4 cannot be asked afterward. Discarding that history is one reason the structure is so fast.

13.4.3The find and union operations

More precisely:

find(x) returns the name of x's set, the root of its tree, by following parent links up to the root. Unlike a search-tree lookup, which seeks a value by descending from the root, find starts from a known node and climbs.

union(x, y) replaces two sets with their union by attaching one root below the other. The sets are disjoint, so there is no duplicate check and no copying: a single parent link changes. Set union in Section 13.1 took O(n + m); here, once the roots are known, it is O(1).

In pseudocode:

find(x):
  if x.parent != x:
    x.parent = find(x.parent)  // path compression
  return x.parent

union(x, y):
  root1 = find(x)
  root2 = find(y)
  if root1 != root2:
    // make the root of one set
    // a child of the other's root
    root1.parent = root2

find is recursive: a node that is not its own parent finds its parent's root. The assignment x.parent = find(x.parent) also makes that root x's new parent; this is path compression, covered in Section 13.5.4. union finds both roots and, if they differ, makes the second the parent of the first; if they are equal, the items already share a set.

13.4.4Mapping objects to indices

Union-Find is most efficient on an integer array: the elements are 0..n − 1, and parent[i] holds the index of i's parent, so moving up is a single array read.

Real elements are often letters, cities, or people, so each object first gets an index — any index, but fixed once assigned — through an object → index hash map. Then parent[i] = i makes every element the root of its own one-element set; this initialization is makeSet.

Map<Character, Integer> index = new HashMap<>();   // 'E'→0, 'F'→1, …
int[] parent = new int[12];
for (int i = 0; i < 12; i++) parent[i] = i;              // 12 singleton sets

The first line holds the letter → index map; the next two build a 12-cell parent array with each cell pointing to itself: 12 singleton sets. A call like union('C', 'K') looks up the indices (4 and 9) and then works on the array. The map is O(1) on average, so the translation adds nothing to the cost; initialization is O(n).

13.4.5union step by step

Let's trace union calls on the 12 letters of Table 13.14, without path compression, under this rule: attach the root of the smaller tree to the root of the larger; on equal sizes, the second root goes under the first. Each root stores its tree's size (number of elements). Section 13.5.2 explains the rule; here we just apply it.

In union(D, I), D is not a root: find(D) returns its parent C, and the singleton I joins C's tree of size 3. In union(C, A), C's tree {C, K, D, I} (size 4) meets A's {A, J, B} (size 3); the smaller goes under C, and the new size is 7.

In the second union(A, B), both finds return C (B's path is B → A → C), so nothing changes: merging two elements of one set is harmless. In union(H, B), H's root is F and B's is C; F's tree {F, E, L, H, G} (size 5) goes under C's (size 7). All 12 elements now form one set with root C.

Are H and B now in the same set? find(H) takes two steps (H → F → C), find(B) two (B → A → C); the roots match, so yes, after 4 steps. The tree's height is 3, the deepest node being G (G → H → F → C). Such a small height for 12 elements is no accident; it comes from union by size.

13.4.6Another idea: Quick-Find

A simpler representation uses no trees. In Sedgewick and Wayne's Quick-Find, a flat array id holds each element's set name, equal for elements of the same set, so find(p) is a single read, id[p]: O(1).

union pays: union(p, q) must rename every element of p's set, and since their positions are unknown, it scans the whole array: O(n).

The table maps out this section and the next. Quick-Find makes find fast, but gathering n elements into one set takes n − 1 array-scanning unions, O(n²). The naive parent tree (Quick-Union) makes union cheap, but trees can grow tall, and find depends on height. The best result combines two improvements that keep trees flat; the α(n) in the table, introduced in Section 13.5.5, never exceeds 4 in practice.

13.4.7Code trace: Quick-Find union

int find(int p) { return id[p]; }  // O(1)
void union(int p, int q) {
  int pid = id[p], qid = id[q];
  if (pid == qid) return;
  for (int i = 0; i < id.length; i++)
    if (id[i] == pid)
      id[i] = qid;           // O(n) scan
}

union reads the two set names; if they are equal, it returns at once. Otherwise it writes qid into every cell whose name is pid.

Starting from Figure 13.15, id = [1, 1, 3, 3, 4, 5], we call union(1, 3) and then union(4, 3).

union(1, 3) renames cells 0 and 1; union(4, 3) renames only cell 4. Yet each call examines all six cells.

Cost. Every union examines n cells, so the n − 1 merges that gather everything into one set cost (n − 1) · n visits, O(n²): 56 for 8 elements, about 10¹² for a million — useless in practice. Making find constant makes union expensive; the parent tree reverses the balance.

13.5Making Union-Find fast

With a parent tree, union is one assignment once the roots are known. All the cost is in find, which takes as many steps as the node's distance from the root, so speeding up Union-Find means keeping trees flat. This section presents two simple ideas and the surprising result of combining them.

13.5.1Why improve it?

Let the naive union(x, y) always put x's root below y's, and call union(1, 2), union(2, 3), union(3, 4), union(4, 5) on five singletons. Each call puts the growing tree under a single node, lengthening the chain by one, until the tree is 1 → 2 → 3 → 4 → 5, of height n − 1 = 4; find(1) follows four links.

Under "attach the smaller tree under the larger," 1 still goes under 2, but then each singleton (3, 4, 5) is added to the root 2. The result is a star of height 1, and every find takes at most one step.

On a chain, every find takes O(n), so a badly ordered sequence of m finds costs O(m · n), possibly worse than Quick-Find. Two simple ideas keep trees flat: (1) union by size or by rank and (2) path compression. Together they make each operation nearly constant: O(α(n)).

13.5.2Union by size

The reasoning: attaching a tree below another root deepens every node of that tree by one, so moving the smaller tree deepens fewer nodes, and the larger tree's nodes keep their depths.

In Figure 13.18, putting the larger tree under the smaller deepens 2, 3, 6, and 9, and 9 sinks from depth 2 to 3. Moving the smaller tree deepens only the shallow nodes 1, 4, and 7; 4 and 7 reach depth 2, 9 stays deepest, and the height remains 2.

This matches Section 13.4.5: ⌊log₂ 12⌋ = 3, and the height was 3. The bound is tight: merging 8 elements into equal trees of two, then four, then eight gives height log₂ 8 = 3, and nothing worse is possible.

13.5.3Union by rank

Tracking height instead of size works as well, but under path compression the true height is costly to maintain: a find may lower it, and detecting that means walking the whole tree. So we keep an upper bound instead.

CLRS splits the operations into three parts:

makeSet(x):
  parent[x] = x
  rank[x] = 0

find(x):   // with path compression
  if x != parent[x]:
    parent[x] = find(parent[x])
  return parent[x]

link(x, y):   // x, y are roots
  if rank[x] > rank[y]:
    parent[y] = x
  else:
    parent[x] = y
    if rank[x] == rank[y]:
      rank[y] = rank[y] + 1

union(x, y):
  link(find(x), find(y))

makeSet(x) makes x its own parent with rank 0. find(x) compresses paths. link(x, y) joins two roots: the one of lower rank goes under the other, and on a tie y's rank goes up. union(x, y) finds the two roots and links them. The rank array holds the ranks.

Why increment on a tie? When two trees of rank r merge, one root becomes the other's child, its deepest node drops a level, and the height can reach r + 1. With unequal ranks, the lower tree's deepened nodes stay within the taller tree's height.

This bound is reached by merging 16 elements in pairs, fours, and eights: the final merge of two eight-element trees gives rank 4 = log₂ 16.

With path compression, rank and height drift apart: compression flattens the tree without updating the rank, which remains only an upper bound. That is not a bug; rank is good enough for deciding links and costs nothing to maintain.

13.5.4Path compression

The second idea exploits find itself. find(x) walks from x to the root, and every node on that path has the same root; linking them all directly to it makes later finds take a single step.

The recursive find does this by itself, parent[x] = find(parent[x]): the recursion descends to the root, and on the way back each call makes that root its node's parent.

Trace find(3) in Figure 13.19. Since parent[3] = 6, find(6) is called, then find(5), then find(7), which returns 7, the root. On the way back, find(5) writes parent[5] = 7 (no change), find(6) writes parent[6] = 7, and find(3) writes parent[3] = 7: the path of 3 shrinks from three steps to one. 10, a child of 6, was off the path and keeps its parent, yet its path shrinks too, to 10 → 6 → 7.

Compression doesn't speed up the find that performs it, which does a little extra work (one write per node). The payoff comes later: a long path, once walked, is gone, and later queries on those nodes are cheap — a typical case for amortized analysis, which averages cost over a sequence of operations.

13.5.5Complexity and the inverse Ackermann function

The first two rows follow from the previous sections, since a union costs two finds plus constant-time linking. The third says that path compression alone gives logarithmic average cost: one find may be slow, but long paths shorten once walked, bounding the total.

The last row is the chapter's most striking result. α(n) is the inverse Ackermann function. The Ackermann function A_k(j) grows at a mind-boggling rate, each increase of k giving a function that applies the previous one to itself repeatedly. Its inverse α(n), the smallest k with A_k(1) ≥ n, grows correspondingly slowly. With the CLRS definition, A₄(1) vastly exceeds 10⁸⁰, an estimate of the number of atoms in the observable universe, so α(n) ≤ 4 for any conceivable input. In practice it is a constant.

The proof is beyond these notes (CLRS gives it a section of its own), but three remarks help. The bound is amortized: one find can still take O(log n), but the total never exceeds O(m · α(n)). It is tight: Tarjan also showed sequences that force time proportional to m · α, so the algorithm never quite reaches linear time — hence "good but not linear" in his title. And memory is small: two integer arrays, parent[n] and rank[n] (or size[n]), O(n).

Union-Find has many uses. Kruskal's minimum spanning tree algorithm uses find to ask whether an edge would close a cycle. A graph's connected components emerge from merging as edges arrive (Section 13.5.10). Image processing groups adjacent same-colored pixels into regions (region labeling), and networks ask whether two machines can reach each other.

13.5.6Java: node-based Union-Find

Union-Find can also hold its elements as objects, each node storing its data, its rank, and a reference to its parent:

class SetNode {
  int data;
  int rank;   // bound on height
  SetNode parent;

  SetNode(int data) {
    this.data = data;
    this.parent = this;
    this.rank = 0;
  }
}

SetNode find(SetNode node) {
  if (node != node.parent)
    node.parent = find(node.parent); // compression
  return node.parent;
}

The constructor makes the node its own parent with rank 0, the object form of makeSet. find translates the pseudocode: a node that is not its own parent gets its parent's root as its new parent (path compression), and that root is returned. node != node.parent compares references, which is right here: the question is whether both point to the same object.

void union(SetNode x, SetNode y) {
  SetNode rootX = find(x);
  SetNode rootY = find(y);
  if (rootX == rootY) return;
  // union by rank
  if (rootX.rank < rootY.rank) {
    rootX.parent = rootY;
  } else if (rootX.rank > rootY.rank) {
    rootY.parent = rootX;
  } else { // equal: pick one
    rootX.parent = rootY;
    rootY.rank++;
  }
}

union finds both roots and returns if they are the same object. Otherwise the root of lower rank goes under the other; on a tie, rootX goes under rootY, whose rank goes up. Elements are used directly as objects, with no index map, at a price in memory and speed: every node is a separate object, and following references is slower than reading an array.

13.5.7Java: array-based Union-Find

For elements 0..n − 1, two integer arrays suffice. This is the form most used in practice:

class UnionFind {
  private final int[] parent, rank;
  UnionFind(int n) {
    parent = new int[n];  rank = new int[n];
    for (int i = 0; i < n; i++) parent[i] = i;
  }
  int find(int x) {
    if (parent[x] != x) parent[x] = find(parent[x]);
    return parent[x];
  }
  boolean union(int x, int y) {
    int rx = find(x), ry = find(y);
    if (rx == ry) return false;
    if (rank[rx] < rank[ry]) parent[rx] = ry;
    else if (rank[rx] > rank[ry]) parent[ry] = rx;
    else { parent[rx] = ry; rank[ry]++; }
    return true;
  }
}

Every element starts as its own parent, and rank starts at zero, Java's default. find compresses paths in one line. union returns false if the two roots coincide; otherwise it links them by rank and returns true.

The boolean result is deliberate: it says whether the call actually merged two different sets. Kruskal's algorithm asks exactly this before adding an edge — an edge whose endpoints already share a set would close a cycle and is skipped — and component counting (Section 13.5.10) relies on it too.

For example, after UnionFind uf = new UnionFind(5); uf.union(0, 1); uf.union(3, 4);, uf.find(1) == uf.find(0) is true and uf.find(1) == uf.find(3) is false. In the first merge the ranks are equal, so 0 goes under 1 and rank[1] = 1; in the second, 3 goes under 4.

13.5.8Code trace: find and union

We trace the array-based structure on 6 elements with union(0, 1), union(2, 3), union(0, 2), union(4, 0), union(1, 4), using these methods:

int find(int x) {
  if (parent[x] != x) parent[x] = find(parent[x]);
  return parent[x];
}
boolean union(int x, int y) {
  int rx = find(x), ry = find(y);
  if (rx == ry) return false;
  if (rank[rx] < rank[ry]) parent[rx] = ry;
  else if (rank[rx] > rank[ry]) parent[ry] = rx;
  else { parent[rx] = ry; rank[ry]++; }
  return true;
}

In the first two calls all elements are roots, so each find returns at once. The ranks are equal, so the else branch runs (parent[rx] = ry, rank[ry]++): {0, 1} gets root 1 and {2, 3} root 3, both of rank 1.

In union(0, 2), find(0) sees parent[0] = 1 ≠ 0, calls find(1), which returns the root 1, and rewrites parent[0] = 1, unchanged. Likewise find(2) = 3. The roots 1 and 3 have equal rank, so 1 goes under 3 and rank[3] = 2. The tree now has root 3 with children 2 and 1, and 0 under 1: height 2, as rank 2 says.

union(4, 0) shows path compression at work. find(4) returns 4; find(0) recurses 0 → 1 → 3, and on the way back writes parent[1] = 3 (unchanged) and parent[0] = 3, moving 0 directly under the root. Since rank[4] = 0 < rank[3] = 2, 4 is attached to 3, and neither rank nor height changes.

In union(1, 4), both finds return 3, so rx == ry and the method returns false — for Kruskal's algorithm, an edge that would close a cycle.

The trace ends with rank and height apart: rank[3] = 2, but with 0 moved up the true height is 1, and the rank is still a valid upper bound. Together, rank and path compression cost about O(α(n)) per operation.

13.5.9Iterative find with path compression

To avoid recursion, find can use two loops: the first finds the root, the second walks the path again and links each node to the root.

int find(int x) {
  int root = x;
  while (parent[root] != root) root = parent[root];
  while (parent[x] != root) {    // path compression
    int next = parent[x];
    parent[x] = root;
    x = next;
  }
  return root;
}

The first loop moves root up from x until it reaches the node that points to itself. The second restarts at x; each step saves the old parent in next, writes parent[x] = root, and moves up with x = next. The old parent must be saved first, or the rest of the path is lost. The loop stops when parent[x] is already the root.

Here is find(4) on the chain parent = [0, 0, 1, 2, 3] (4 → 3 → 2 → 1 → 0), left by bad merges.

The first loop reaches the root in four steps; the second relinks 4, 3, and 2 to 0 and stops at 1, already a child of the root. The method returns 0, and every later find on these nodes takes one step. Without recursion, no chain is long enough to overflow the stack.

Cost. Each loop walks the path once, so the time is still O(path length). The compression matches the recursive version, but extra memory is O(1) rather than one call frame per step.

13.5.10Application: counting connected components

A connected component of a graph is a maximal group of nodes that can reach one another by paths. How many components does a graph with n nodes and a given edge list have? Union-Find answers naturally: each node starts alone, and each edge merges its endpoints' components.

int countComponents(int n, int[][] edges) {
  UnionFind uf = new UnionFind(n);
  int count = n;        // n singleton sets
  for (int[] e : edges)
    if (uf.union(e[0], e[1]))
      count--;          // two components merged
  return count;
}

count starts at n, every node being its own component. A union that returns true has merged two components, so the count drops by one; false means the endpoints already share a component, the edge closes a cycle, and the count stays. Again, union's return value is the heart of the method.

A trace with 7 nodes and the edges (0, 1), (1, 2), (3, 4), (0, 2), (5, 6):

At (1, 2), 1 has rank 1 and 2 rank 0, so 2 goes under 1. At (0, 2), both endpoints have root 1, so union returns false and count stays 4: this edge closes the triangle 0–1–2. Three components remain, and the method returns 3.

Cost. Building takes O(n), and each of the m edges one union (two finds): O(n + m · α(n)) in all. Depth-first search answers in O(n + m), but Union-Find shines at dynamic connectivity: as edges arrive one at a time, the count is current after each, while depth-first search would start over. The graph is connected exactly when count == 1.

13.6Common mistakes

The chapter's mistakes fall into two groups: the first three concern Java sets, the last three Union-Find and sorted sets.

The first is insidious because nothing fails; answers are just wrong. Add a Point whose hash code comes from x and y while it is (1, 2), then set p.x = 5. Its hash code changes, but it stays in the old bucket, so set.contains(p) looks elsewhere and fails, though the set's size is still 1. That is why immutable objects (String, Integer, records) are preferred as set elements and map keys.

The third arises because a for-each loop runs on an iterator that tracks structural changes; if the set changes by another route mid-loop, the iterator throws at its next step. removeIf is safe because it removes through the iterator itself.

13.7Summary

• A set is an unordered collection of distinct elements, with insertion, removal, and membership as basic operations. Union (∪), intersection (∩), difference (−, not commutative), and subset (⊆) are the set operations.
• Java's Set interface: add returns false for an element already present, detecting repeats in one call; addAll, retainAll, removeAll work in place, so copy a set first to keep it.
• A hash-based set puts each element in the bucket given by its hash code, chaining collisions. With a bounded load factor, add, contains, remove are O(1) on average, O(n) with a bad hash function. Override equals and hashCode together.
• A tree-based set (TreeSet, a red-black tree) does everything in O(log n), including sorted queries such as first, floor, ceiling, subSet; equality is decided by compare.
• Sorted arrays give union and intersection in one two-pointer pass, O(n + m); on a common element both pointers advance.
• A bit vector stores a set over a small universe in U bits; single-element operations, and set operations for U ≤ 32, are single instructions, and BitSet operations take O(U / 64). Sparse sets use less memory as hash sets.
• A multiset records multiplicities in an element → counter map, deleting zero counters; size() counts repeats. A multimap maps a key to a list of values (Map<K, List<V>>).
• Disjoint sets partition elements into groups. Union-Find keeps each group as a tree whose root represents it; find climbs to the root, union links two roots. Objects are first mapped to indices.
• Quick-Find has O(1) find but array-scanning unions: n − 1 merges cost O(n²). A naive parent tree can become a chain, with O(n) find.
• Union by size or by rank bounds the height by ⌊log₂ n⌋ (a rank-r tree has at least 2^r elements). Path compression links every node on find's path to the root. Together they run m operations in O(m · α(n)) (Tarjan, 1975), with α(n) ≤ 4.
• union's boolean says whether it really merged: each true decrements the component count, and in Kruskal's algorithm a false marks a cycle-forming edge.

13.8Key terms

Each term links to the course glossary, which gives its Turkish equivalent and its use in other chapters.

• set
• abstract data type (ADT)
• union
• intersection
• difference
• subset
• hash table
• hash code
• bucket
• collision
• separate chaining
• load factor
• binary search tree (BST)
• red-black tree
• inorder
• merge sort
• bit vector
• multiset
• multimap
• map
• disjoint sets (union-find)
• parent
• root
• height
• union by size
• rank
• union by rank
• path compression
• amortized analysis
• connected component
• Kruskal's algorithm
• iterator

13.9Test Yourself

1. For A = {1, 3, 5, 7, 9} and B = {3, 6, 9}, what are A ∪ B, A ∩ B, A − B, and B − A? Are {3, 9} ⊆ B and B ⊆ A true?

   Answer

   A ∪ B = {1, 3, 5, 6, 7, 9}, A ∩ B = {3, 9}, A − B = {1, 5, 7}, B − A = {6}. {3, 9} ⊆ B is true; B ⊆ A is false, because 6 ∉ A. Check: |A ∪ B| = 5 + 3 − 2 = 6.

2. What does firstRepeat(new int[]{5, 1, 9, 1, 5}) return? How many times is add called before the method returns?

   Answer

   1. The first three adds (5, 1, 9) return true, leaving {1, 5, 9}; the fourth, add(1), returns false, so the method returns 1 after 4 adds. The final 5 is never examined: it repeats too, but later.

3. The values 14, 3, 21, 10, 3 are added in order to a chained hash set with 7 buckets (bucket = x % 7). What does each add return, and what is the final state of the buckets? How many comparisons does a following contains(17) make?

   Answer

   Buckets: 14 → 0, 3 → 3, 21 → 0, 10 → 3, 3 → 3, so the calls return true, true, true, true, false. Bucket 0 holds 14 → 21, bucket 3 holds 3 → 10, the rest are empty, and n = 4. contains(17) goes to bucket 17 mod 7 = 3, compares with 3 and 10 (2 comparisons), and returns false.

4. unionIntersection is called with a = [2, 5, 8, 11] and b = [1, 5, 11, 12, 15]. What are uni and both? How many times does the main loop run?

   Answer

   Passes: 2 > 1 → add 1; 2 < 5 → add 2; 5 = 5 → common; 8 < 11 → add 8; 11 = 11 → common. Then i = 4 = a.length, ending the main loop after 5 passes, and the leftover 12 and 15 join the union: uni = [1, 2, 5, 8, 11, 12, 15], both = [5, 11].

5. The set a is built from the bits {0, 4, 6} and b from {4, 5}. What are the numeric values of a, b, a | b, a & b, and a & ~b, and which sets do they represent?

   Answer

   a = 1 + 16 + 64 = 81 (0101 0001), b = 16 + 32 = 48 (0011 0000). a | b = 113 (0111 0001) → {0, 4, 5, 6}. a & b = 16 → {4}. a & ~b = 65 (0100 0001) → {0, 6}. Four bits are set in the union: Integer.bitCount(a | b) = 4.

6. The letters of the word "tattoos" are added to a Multiset<Character>. Then remove('t') is called twice and remove('a') once. What do count('t'), count('a'), and size() return? How many entries are left in the map?

   Answer

   After the insertions the map is {t:3, a:1, o:2, s:1}, n = 7. The two remove('t') calls take the counter 3 → 2 → 1; remove('a') deletes its entry. count('t') = 1, count('a') = 0, size() = 4, and three entries remain: {t:1, o:2, s:1}.

7. For the TreeSet S = {4, 9, 13, 18, 22, 30}, what do floor(20), ceiling(20), subSet(9, 22), and floor(3) return?

   Answer

   floor(20) = 18 (largest ≤ 20), ceiling(20) = 22 (smallest ≥ 20), subSet(9, 22) = [9, 13, 18] (22 excluded). floor(3) returns null, since no element is ≤ 3; assigning it to an int throws a NullPointerException.

8. On an array-based UnionFind(6), the calls union(0, 1), union(1, 2), union(3, 4), union(4, 5), union(2, 5), union(0, 3) are made in order. What does the last call return? What are the final parent and rank arrays?

   Answer

   (0, 1): equal ranks, 0 → 1, rank[1] = 1. (1, 2): 2 → 1. (3, 4): 3 → 4, rank[4] = 1. (4, 5): 5 → 4. (2, 5): roots 1 and 4 of equal rank; 1 → 4, rank[4] = 2. (0, 3): find(0) walks 0 → 1 → 4 and compresses 0 onto 4; find(3) = 4; same root, so false. Final: parent = [4, 4, 1, 4, 4, 4], rank = [0, 1, 0, 0, 2, 0]. 2 still points to 1, since no find passed through it.

9. With parent = [0, 0, 1, 2, 2, 4], the iterative find(5) is called. In how many steps is the root found, and what is the final array? Why doesn't 3's parent change?

   Answer

   The path 5 → 4 → 2 → 1 → 0 finds the root in 4 steps. The second loop links 5, 4, and 2 to 0 (1 already is), giving [0, 0, 0, 2, 0, 0]. 3, a child of 2, is not on the path walked, and compression changes only that path; still, 3's path shrinks to 3 → 2 → 0.

10. Under union by size (with the second root going under the first on ties), what is the greatest possible height of a tree of 8 elements? Give a sequence of unions that produces it.

    Answer

    At most ⌊log₂ 8⌋ = 3, by the theorem. union(0,1), union(2,3), union(4,5), union(6,7) make four pairs; union(0,2) and union(4,6) two fours; union(0,4) one tree, with parent = [0, 0, 0, 2, 0, 4, 4, 6] and the path 7 → 6 → 4 → 0 of 3 steps. Each merge joined equal-sized trees, raising the height by one.

13.10Further reading

• M. T. Goodrich, R. Tamassia, and M. H. Goldwasser, Data Structures and Algorithms in Java (6th ed., 2014), Sections 10.5 and 14.7: the set, multiset, and multimap ADTs, the generic merge, and Union-Find within Kruskal's algorithm, in Java close to that of these notes.
• R. Sedgewick and K. Wayne, Algorithms (4th ed., 2011), Section 1.5: the path from Quick-Find through Quick-Union and weighted union to path compression, compared with experimental measurements.
• T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms (4th ed., 2022), Chapter 19: disjoint-set forests, union by rank, path compression, and a formal proof of the O(m · α(n)) bound.
• R. E. Tarjan, "Efficiency of a Good But Not Linear Set Union Algorithm" (1975): the original paper showing that rank and path compression together give the inverse Ackermann bound, and that the bound is tight.

13.11References

1. T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, 4th ed., MIT Press, 2022.
2. B. A. Galler, M. J. Fischer, "An improved equivalence algorithm," Communications of the ACM, 7(5), 301–303, 1964.
3. M. T. Goodrich, R. Tamassia, M. H. Goldwasser, Data Structures and Algorithms in Java, 6th ed., Wiley, 2014.
4. Oracle, Java SE 17 API Specification: documentation for java.util.Set, HashSet, TreeSet, and BitSet.
5. R. Sedgewick, K. Wayne, Algorithms, 4th ed., Addison-Wesley, 2011.
6. R. E. Tarjan, "Efficiency of a Good But Not Linear Set Union Algorithm," Journal of the ACM, 22(2), 215–225, 1975.

Related pages: Chapter 13 slides · Study questions · Glossary · © Sercan Külcü. All rights reserved.