Applications of Path Compression on Balanced Trees
Robert Endre Tarjan · Journal of the ACM · 1979
Several fast algorithms are presented for computing functions defined on paths in trees under various assumpuons.The algorithms are based on tree mampulatton methods first used to efficiently represent equivalence relations.The algorithms have O((m + n)a(m + n, n)) running tunes, where m and n are measures of the problem size and a Is a functional reverse of Ackermann's function By usmg one or more of these algorithms m combination with other techniques, it is possible to solve the followmg graph problems m O(ma(m, n)) tnne, where m Is the number of edges and n Is the number of vertices m the problem graph A Venfymg a minimum spanning tree m an undirected graph (Best previously known time bound O(m log log n).) B Flndmg dominators in a flow graph (Best previously known tune bound O(n log n + m).) C Solvmg a path problem on a reducible flow graph.(Best previously known time bound.O(m log n) ) Application A is discussed KEY WORDS AND PHRASES balanced tree, dominators, equivalence relation, global flow analysis, graph algonthm, mmnnum spanning tree, path compression, path problem, tree CR CAT~60~mS: 4.12, 4.34, 5.25, 5.32 LINK(v, w)" Combme the trees with roots v and w into a single tree by addmg an edge (v, w) (this makes v the parent of w).UPDATE(r, x)" lfr ts the root of a tree and r has label l, replace I by x ® IWe present algorithms for carrying out on-line an arbitrary sequence of m EVAL, LINK, and UPDATE instructions on a forest initially consisting of n one-vertex trees.Our first and simplest algorithm uses path compression to solve the EVAL-LINK-UPDATE