arXiv preprint ·
Union-Find with Constant-Time Deletions Across the Optimal Worst-Case Tradeoff
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
We consider union-find with deletions, where the representation and the cost of a query must depend on the current number of live elements rather than on the number of elements ever created. For every integer parameter $k\ge 2$, we give a linear-space data structure supporting $\mathsf{MakeSet}$ in $O(1)$ worst-case time, $\mathsf{Union}$ in $O(k)$ worst-case time, $\mathsf{Delete}$ in $O(1)$ worst-case time, and $\mathsf{Find}$ in $O\left(1+\frac{\log n}{\log k}\right)$ worst-case time for a set containing $n$ live elements. A deletion is given only an element handle, not the identifier of its current set. The construction separates global rank growth from local deletion repair. A logical set is represented by fewer than $k$ disjoint ranked trees. Equal-level trees are collected without physical linking until $k$ certificates are available, at which point one base-$k$ carry is performed in $O(k)$ time. Each member tree uses a strengthened form of the full/reduced local rebuilding scheme of Ben-Amram and Yoffe. A $q$-ary value argument, with $q=3/2$, couples the local trees to the base-$k$ certificates and yields the stated current-size height bound. A small but essential rule handles high-rank stars, a state that the base-$k$ carry can create but that does not arise directly in the binary-rank construction underlying the earlier local scheme.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
Algorithmic Collusion and the Complexity of Information-Value-Free Equilibria
The Inverse Lyndon Array
An Arboricity-Sensitive Algorithm for the $K_r-e$-Free Graph Sandwich Problem
Local Representatives and Shortest Completions for Next-to-Shortest Paths in Directed Graphs
Single-Pass Estimation of the Clustering Coefficient Distribution in Graph Streams
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.