tailieunhanh - Lecture Data Structures: Lesson 35

Lecture Data Structures: Lesson 35 provide students with knowledge about dynamic equivalence problem; the trees we will use are not necessarily binary; to perform union of two sets, we merge the two trees by making the root of one point to the root of the other; . | Dynamic Equivalence Problem We will use a tree to represent each set since each element in a tree has the same root. The root can be used to name the set. There will be a collection of trees each tree representing one set. A collection of trees is called a forest. Lecture Data Structure Dr. Sohail Aslam Dynamic Equivalence Problem The trees we will use are not necessarily binary. To perform union of two sets we merge the two trees by making the root of one point to the root of the other. A find x on element x is performed by returning the root of the tree containing x. Dynamic Equivalence Problem 1 2 3 4 5 6 7 8 Eight elements initially in different sets. Dynamic Equivalence Problem 1 2 3 4 5 7 8 6 After union 5 6 Dynamic Equivalence Problem 1 2 3 4 5 7 6 8 After union 7 8 Dynamic Equivalence Problem 1 2 3 4 5 6 7 8 After union 5 7 Dynamic Equivalence Problem 1 2 3 5 4 6 7 8 After union 3 4 Dynamic Equivalence Problem 1 2 3 4 5 6 7 8 After union 4 5 Dynamic Equivalence Problem Typical tree traversal not required so no need for pointers to children instead we need a pointer to parent an up-tree Parent pointers can be stored in an array parent i set to -1 if i is root . The algorithm for find and union can thus be Dynamic Equivalence Problem Initialization for i 0 i lt n i parent i -1 find i traverse to the root -1 for j i parent j gt 0 j parent j return j Dynamic Equivalence Problem union i j root_i find i root_j find j if root_i root_j parent root_j root_i Parent Array 1 2 3 4 5 6 7 8 -1 -1 -1 -1 -1 -1 -1 -1 1 2 3 4 5 6 7 8 Eight elements initially in different sets. Parent Array 1 2 3 4 5 7 8 6 -1 -1 -1 -1 -1 5 -1 -1 1 2 3 4 5 6 7 8 After union 5 6 Parent Array 1 2 3 4 5 7 6 8 -1 -1 -1 -1 -1 5 -1 7 1 2 3 4 5 6 7 8 After union 7 8 Parent Array 1 2 3 4 5 6 7 8 -1 -1 -1 -1 -1 5 5 7 1 2 3 4 5 6 7 8 After union 5 7 Parent Array 1 2 3 5 4 6 7 8 -1 -1 -1 3 -1 5 5 7 1 2 3 4 5 6 7 8 After union 3 4 Parent Array 1 2 3 4 5 6 7 8 -1 -1 -1 3 3 5 5 7 1 2 3 4 5 6 7 8 .