Finding level-ancestors in trees

摘要

The level-ancestor problem is considered. Suppose a rooted tree T is given for preprocessing. Answer quickly queries of the following form. Given a vertex v and an integer i > 0, find the ith vertex on the path from v to the root. Given any m, 1 ≤ m ≤ log*n, we achieve the following results: (1) O(log(m) n)1 time using an optimal number of processors for preprocessing and constant time using a single processor for processing a query if m is constant. (2) O(log* n) time using an optimal number of processors for preprocessing and O(log* n) time using a single processor for processing a query. These results assume that the Euler tour of the tree and the level (distance from the root) of each vertex are given. Without these assumptions, the only change in result (1) above is that preprocessing time increases to O(log n). An immediate corollary is a serial linear-time bound for preprocessing and a constant-time bound for processing a query.