Optimal pointer algorithms for finding nearest common ancestors in dynamic trees

We consider the problem of finding the nearest common ancestor of two given nodes x and y (denoted by nca(x,y)) in a dynamic forest of rooted trees. Interspersed with nea-queries are online commands link(x, y), where x, but not necessarily y, is a tree root. The effect of a command link(x, y) is to combine the trees containing x and y, by making y the parent of x. This problem was originally proposed by A. V. Aho, J. E. Hopcroft, and J. D. Ullman (SIAM J. Comput. 5, No. 1 (1976), 115-132). We present a pointer machine algorithm, which performs n link and m nca operations in time O(n + m log log n), matching a lower bound by D. Harel and R. E. Tarjan (SIAM J. Comput. 13, No. 2 (1984), 338-355). The previous best bound on a pointer machine was O((n + m)log n), due to D. D. Sleator and R. E. Tarjan (J. Comput. System Sci. 26, No. 3 (1983), 362-391). (C) 2000 Academic Press.