zbMATH — the first resource for mathematics

Improved algorithms for finding level ancestors in dynamic trees. (English) Zbl 0973.68665
Montanari, Ugo (ed.) et al., Automata, languages and programming. 27th international colloquium, ICALP 2000, Geneva, Switzerland, July 9-15, 2000. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 1853, 73-84 (2000).
Summary: Given a node \(x\) at depth \(d\) in a rooted tree \(\text{LevelAncestor} (x,i)\) returns the ancestor to \(x\) in depth \(d-i\). We show how to maintain a tree under addition of new leaves so that updates and level ancestor queries are being performed in worst case constant time. Given a forest of trees with \(n\) nodes where edges can be added, \(m\) queries and updates take \(O(m\alpha (m,n))\) time. This solves two open problems. In a tree with node weights, \(\min(x,y)\) report the node with minimum weight on the path between the nodes \(x\) and \(y\). We can substitute the LevelAncestor query with min, without increasing the complexity for updates and queries. Previously such results have been known only for special cases.
For the entire collection see [Zbl 0941.00034].

68W05 Nonnumerical algorithms
68P05 Data structures
68W40 Analysis of algorithms
05C05 Trees