CSCB63H3 Chapter Notes -Linked List, Time Complexity, Disjoint-Set Data Structure
Document Summary
Abstract data structure: a collection of nonempty disjoint dynamic sets -> s = s1, s2, , sk. Only care about getting the same number when asked for a representative of a dynamic set twice without modifying the set. Since we represent each element of a set by an object (this being x) we have the following operations. Each set is a representative (member of the set: make_set(x) Creates new set whose only member is x (the representative) Because its disjoint, we need to make sure x does not belong in another set: union(x, y) Unites set x and y, sx and sy into new set. Assume that these sets are disjoint before operation. After union, sets get destroyed conceptionally -> sx and sy removed from s. One becomes absorbed into another: find_set(x) Returns pointer to representative of unique set containing x. A linked list is a way to implement a disjoint-set data structure.
