A tight amortized bound for path reversal (Q1822942): Difference between revisions

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.