ISSN:
1432-0525
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
Notes:
Summary 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))+α(k,k))}, where the second factor is amortized over k queries, α is a functional inverse of Ackermann's function and depth(x) the distance from node x to the root of T.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF00268844
Permalink