Union-find with deletions
Haim Y. Kaplan, Nira Shafrir, Robert Endre Tarjan · 2002
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 ets A and B in the partition by their union, given the name C. The operation find(z) 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