Union-find with deletions

ABSTRACT

In the classical union-find problem we maintain a partition of a universe of n elements into disjoint sets subject to the operations union and find. The operation union(A, B, C) replaces sets A and B in the partition by their union, given the name C. The operation find(x) returns the name of the set containing the element x. In this paper we revisit the union-find problem in a context where the underlying partitioned universe is not fixed. Specifically, we allow a delete(x) operation which removes the element x from the set containing it. We consider both worst-case performance and amortized performance. In both settings the challenge is to dynamically keep the size of the structure representing each set proportional to the number of elements in the set which may now decrease as a result of deletions.For any fixed k, we describe a data structure that supports find and delete in O(logkn) worst-case time and union in O(k) worst-case time. This matches the best possible worst-case bounds for find and union in the classical setting. Furthermore, using an incremental global rebuilding technique we obtain a reduction converting any union-find data structure to a union-find with deletions data structure. Our reduction is such that the time bounds for find and union change only by a constant factor. The time it takes to delete an element x is the same as the time it takes to find the set containing x plus the time it takes to unite a singleton set with this set.In an amortized setting a classical data structure of Tarjan supports a sequence of m finds and at most n unions on a universe of n elements in O(n + mα(m + n, n, log n)) time where α(m, n, l) = min{k | Ak(⌊m/n⌋) > l} and Ai(j) is Ackermann's function as described in [6]. We refine the analysis of this data structure and show that in fact the cost of each find is proportional to the size of the corresponding set. Specifically, we show that one can pay for a sequence of union and find operations by charging a constant to each participating element and O(α(m, n, log(l))) for a find of an element in a set of size l. We also show how keep these amortized costs for each find and each participating element while allowing deletions. The amortized cost of deleting an element from a set of l elements is the same as the amortized cost of finding the element; namely, O(α(m, n, log(l))).

REFERENCES

• 1: A. M. Ben-Amram and Z. Galil. A generalization of a lower bound technique due to Fredman and Saks. Algorithmica, 30:34-66, 2001.
• 2: Norbert Blum, On the single-operation worst-case time complexity of the disjoint set union problem, SIAM Journal on Computing, v.15 n.4, p.1021-1024, Nov. 1986 [doi>10.1137/0215072]
• 3: M. Fredman , M. Saks, The cell probe complexity of dynamic data structures, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.345-354, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73040]
• 4: Michael L. Fredman , Robert Endre Tarjan, Fibonacci heaps and their uses in improved network optimization algorithms, Journal of the ACM (JACM), v.34 n.3, p.596-615, July 1987 [doi>10.1145/28869.28874]
• 5: M. Korupolu, R. Mettu, V. Ramachandran, and Y. Zhao. Experimental evaluation of algorithms for incremental graph connectivity and biconnectivity, 1996.
• 6: Dexter C. Kozen, The design and analysis of algorithms, Springer-Verlag New York, Inc., New York, NY, 1992
• 7: M. Smid. A data structure for the union-find problem having good single-operation complexity. ALCOM: algorithms review, Newsletter of the ESPRIT II Basic Research action program project no. 3075, 1, 1990.
• 8: Robert Endre Tarjan, Efficiency of a Good But Not Linear Set Union Algorithm, Journal of the ACM (JACM), v.22 n.2, p.215-225, April 1975 [doi>10.1145/321879.321884]
• 9: Robert E. Tarjan , Jan van Leeuwen, Worst-case Analysis of Set Union Algorithms, Journal of the ACM (JACM), v.31 n.2, p.245-281, April 1984 [doi>10.1145/62.2160]