算法和数据结构10.pptVIP

Chapter 8 BINARY AND OTHER TREES Applications Union-Find Problem Union-Find Problem Given a set {1, 2, …, n} of n elements. Initially each element is in a different set. {1}, {2}, …, {n} An intermixed sequence of union and find operations is performed. A union operation combines two sets into one. Each of the n elements is in exactly one set at any time. A find operation identifies the set that contains a particular element. Using Arrays And Chains See Section 3.8.3 for applications as well as for solutions that use arrays and chains. Best time complexity is O(n + u log u + f), where u and f are, respectively, the number of union and find operations that are done. Using a tree (not a binary tree) to represent a set, the time complexity becomes almost O(n + f) (assuming at least n/2 union operations). A Set As A Tree S = {2, 4, 5, 9, 11, 13, 30} Some possible tree representations: Result Of A Find Operation find(i) is to identify the set that contains element i. In most applications of the union-find problem, the user does not provide set identifiers. The requirement is that find(i) and find(j) return the same value iff elements i and j are in the same set. Strategy For find(i) Start at the node that represents element i and climb up the tree until the root is reached. Return the element in the root. To climb the tree, each node must have a parent pointer. Trees With Parent Pointers Possible Node Structure Use nodes that have two fields: element and parent. Use an array table[] such that table[i] is a pointer to the node whose element is i. To do a find(i) operation, start at the node given by table[i] and follow parent fields until a node whose parent field is null is reached. Return element in this root node. Example Better Representation Use an integer array parent[] such that parent[i] is the element that is the parent of element i. Union Operation union(i,j) i and j are the roots of two different trees, i != j. To unite the trees, make one tree a subtree o