A tight amortized bound for path reversal (Q1822942): Difference between revisions
From MaRDI portal
Set OpenAlex properties. |
ReferenceBot (talk | contribs) Changed an Item |
||
Property / cites work | |||
Property / cites work: The pairing heap: A new form of self-adjusting heap / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Self-adjusting binary search trees / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Amortized Computational Complexity / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Worst-case Analysis of Set Union Algorithms / rank | |||
Normal rank |
Latest revision as of 10:33, 20 June 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A tight amortized bound for path reversal |
scientific article |
Statements
A tight amortized bound for path reversal (English)
0 references
1989
0 references
An n-node tree T is considered as a data structure, and the path reversal at an node x in T (performed by traversing the path from x to the tree root r and making x the parent of each node on the path other than x) is considered as the only one operation allowed on this data structure. The cost of one reversal is the number of edges on the path reversed. The amortized complexity of m reversals in an n-node tree is the average cost per one reversal according to the worst-case sequence performed at the worst-case n-node tree. The upper bound log n\(+n \log n/2m\) on the amortized complexity is proved.
0 references
data structures
0 references
disjoint set union problem
0 references
path compression
0 references