TAILIEUCHUNG - Lecture Data structures and algorithms in Java (6th edition): Chapter 14.8 - Goodrich, Tamassia, Goldwasser
This chapter provides knowledge of unionfind. Data structures and algorithms in java provides an introduction to data structures and algorithms, including their design, analysis, and implementation. | Union-Find 3/29/14 21:35 Presentation for use with the textbook Data Structures and Algorithms in Java, 6th edition, by M. T. Goodrich, R. Tamassia, and M. H. Goldwasser, Wiley, 2014 Union-Find Partition Structures © 2014 Goodrich, Tamassia, Goldwasser Union-Find 1 Partitions with Union-Find Operations ! makeSet(x): Create a singleton set containing the element x and return the position storing x in this set ! union(A,B ): Return the set A U B, destroying the old A and B ! find(p): Return the set containing the element at position p © 2014 Goodrich, Tamassia, Goldwasser Union-Find 2 1 Union-Find 3/29/14 21:35 List-based Implementation ! Each set is stored in a sequence represented with a linked-list ! Each node should store an object containing the element and a reference to the set name © 2014 Goodrich, Tamassia, Goldwasser Union-Find 3 Analysis of List-based Representation ! When doing a union, always move elements from the smaller set to the larger set Each time an element is moved it goes to a set of size at least double its old set n Thus, an element can be moved at most O(log n) times n ! Total time needed to do n unions and finds is O(n log n). © 2014 Goodrich, Tamassia, Goldwasser Union-Find 4 2 Union-Find 3/29/14 21:35 Tree-based Implementation ! Each element is stored in a node, which contains a pointer to a set name ! A node v whose set pointer points back to v is also a set name ! Each set is a tree, rooted at a node with a selfreferencing set pointer ! For example: The sets “1”, “2”, and “5”: 1 4 2 7 3 5 6 8 9 © 2014 Goodrich, Tamassia, Goldwasser 10 11 12 Union-Find 5 Union-Find Operations 5 ! To do a union, simply make the root of one tree point to the root of the other 2 8 3 11 9 ! To do a find, follow setname pointers from the starting node until reaching a node whose set-name pointer refers back to itself © 2014 Goodrich, Tamassia, .
đang nạp các trang xem trước
