A tight amortized bound for path reversal

DOI10.1016/0020-0190(89)90101-4zbMath0679.68033OpenAlexW2112310302MaRDI QIDQ1822942

Yanyan Li

Publication date: 1989

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(89)90101-4

zbMATH Keywords

data structuresdisjoint set union problempath compression

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Data structures (68P05)

Related Items

An asymptotic study for path reversal. ⋮ Complexity of algorithm and operations on trees ⋮ A systematic analysis of splaying ⋮ The derivation of a tighter bound for top-down skew heaps

Cites Work

• The pairing heap: A new form of self-adjusting heap
• Amortized Computational Complexity
• Self-adjusting binary search trees
• Worst-case Analysis of Set Union Algorithms