COEN 179 Lecture Notes - Lecture 17: Disjoint Sets, Observable Universe, Disjoint-Set Data Structure

• School: Santa Clara University
• Department: Computer Engineering
• Course: COEN 179
• Professor: Tran

Document Summary

Purpose: maintain a collection of objects separated into groups (kruskal"s: maintain trees separately) Each group has a representation called the root. A: makeset(x){ rare,gtiankgkey ptr_x = new node(ptr_x. 0, x); //o(1: find_root(ptr_x){ for(p = ptr_x; p != p->parent; p = p->parent) Link_roots(r1, r2){ if(r1 == r2) return; switch(compare(r1->rank, r2->rank)){ case +: r2->parent = r1; return; case -: r1->parent = r2; return; case 0: r2 ->parent = r1; Make -set (vi hoch) sort e increasing weights. F- d for each edge { a. b } ee { Note insrarhsglgcm)ef( log n ) ksm elsie)=2dgn -i. {a, b} root(a) = a root(b) = b. T = {{a, b}: {a, c} root(a) = a root(c) = c. 4 {c, d} (cid:15482: {b, c} root(b) = a root(c) = a skip. 4){c, d} root(c) = a root(d) = d. Theorem: (1)rank(x) = height(x) (2) size(x) = zrankcx)