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, .

• Cơ sở dữ liệu
• Data structures
• Data structures and algorithms
• Computer science
• Design of data structures
• Algorithms in Java
• Ebook Data structures and algorithms made easy
• Data structures and algorithms made easy
• Data structures and algorithmic puzzles
• Data structures for storing strings
• Algorithms design techniques
• algorithms
• data structure lectures
• structured document data
• teaching data structures
• algorithms in data structures
• Lecture Data Structures
• Bài giảng Cấu trúc dữ liệu
• Programming assignments
• Data structures organize data
• Resource constraints
• Lecture Data structures and algorithms
• Cấu trúc dữ liệu và giải thuật
• Abstract data type
• Lecture ECE 250
• Lecture Algorithms and data structures
• Algorithm analysis
• Graph algorithms
• Memory allocation
• AVL trees
• Binary search trees
• Red black trees
• Splay trees
• Dynamic programming