The nearest common ancestor in a dynamic tree (Q1821561): Difference between revisions

We consider the problem of determining the nearest common ancestor of two given nodes x and y (denoted by nca(x,y)) in a dynamic arbitrary tree T. We present an implementation of T by a pointer machine which needs linear space, performs m arbitrary insertions and deletions in the initially empty tree T in time O(m) and a query about nca(x,y) can be answered on- line in time O(log(min\(\{\) depth(x),\(depth(y)\})+\alpha (k,k))\), where the second factor is amortized over k queries, \(\alpha\) is a functional inverse of Ackermann's function and depth(x) the distance from node x to the root of T.