Complexity of algorithm and operations on trees (Q688696): Difference between revisions

We consider operations on trees like paths reversal and standard path compression. These operations are used in the algorithm to maintain disjoint sets under union [\textit{R. E. Tarjan} and \textit{J. van Leeuwen}, J. Assoc. Comput. Mech. 31, 245-281 (1984; Zbl 0632.68043)]. The path reversal had been used in a recent mutual exclusion algorithm [\textit{M. Trehel} and \textit{M. M. Naimi}, Tech. Sci. Inf. 6, 141-150 (1987; Zbl 0618.68037)]. We give exact values for the worst-case of a sequence of these operations performed on an arbitrary initial tree. To obtain these results, we first give upper bounds by applying the potential function method of amortized analysis introduced by \textit{R. E. Tarjan} [SIAM J. Algebraic Discrete Methods 6, 306-318 (1985; Zbl 0599.68046)]. Then, we show up sequences of operations which costs are exactly the upper proved bounds.