Abstract | ||
---|---|---|
A union-find data structure maintains a collection of disjoint sets under the operations makeset, union, and find. Kaplan, Shafrir, and Tarjan [SODA 2002] designed data structures for an extension of the union-find problem in which items of the sets maintained may be deleted. The cost of a delete operation in their implementations is essentially the same as the cost of a find operation; namely, O(log n) worst-case and O(α⌈ M/N⌉ (n)) amortized, where n is the number of items in the set returned by the find operation, N is the total number of makeset operations performed, M is the total number of find operations performed, and α⌈ M/N⌉(n) is a functional inverse of Ackermann’s function. They left open the question whether delete operations can be implemented more efficiently than find operations, for example, in o(log n) worst-case time. We resolve this open problem by presenting a relatively simple modification of the classical union-find data structure that supports delete, as well as makeset and union operations, in constant worst-case time, while still supporting find operations in O(log n) worst-case time and O(α⌈ M/N⌉ (n)) amortized time. Our analysis supplies, in particular, a very concise potential-based amortized analysis of the standard union-find data structure that yields an O(α⌈ M/N⌉ (n)) amortized bound on the cost of find operations. All previous potential-based analyses yielded the weaker amortized bound of O(α⌈ M/N⌉ (N)). Furthermore, our tighter analysis extends to one-path variants of the path compression technique such as path splitting. |
Year | DOI | Venue |
---|---|---|
2005 | 10.1145/2636922 | ACM Transactions on Algorithms |
Keywords | DocType | Volume |
data structure | Conference | 11 |
Issue | ISSN | ISBN |
1 | 1549-6325 | 3-540-27580-0 |
Citations | PageRank | References |
4 | 0.42 | 20 |
Authors | ||
6 |
Name | Order | Citations | PageRank |
---|---|---|---|
Stephen Alstrup | 1 | 657 | 42.60 |
Inge Li Gørtz | 2 | 128 | 20.94 |
Theis Rauhe | 3 | 661 | 35.11 |
Mikkel Thorup | 4 | 5081 | 366.30 |
Uri Zwick | 5 | 3586 | 257.02 |
IL Gortz | 6 | 11 | 0.95 |