zbMATH — the first resource for mathematics

The level ancestor problem simplified. (English) Zbl 1068.68047
Summary: We present a simple algorithm for the Level Ancestor Problem. A Level Ancestor Query LA(\(v,d\)) requests the depth \(d\) ancestor of node \(v\). The Level Ancestor Problem is to preprocess a given rooted tree \(T\) to support level ancestor queries. While optimal solutions to this problem already exist, our new optimal solution is simple enough to be taught and implemented.

68P05 Data structures
05C05 Trees
Full Text: DOI
[1] S. Alstrup, J. Holm, Improved algorithms for finding level-ancestors in dynamic trees, in: 27th Internat. Colloquium on Automata, Languages and Programming (ICALP), Geneva, Switzerland, Lecture Notes in Comput. Sci. Vol. 1853, Springer, Berlin, 2000, pp. 73-84. · Zbl 0973.68665
[2] M.A. Bender, E. Demaine, M. Farach-Colton, Cache-oblivious B-trees, in: 41st Annual Symp. on Foundations of Computer Science (FOCS), 2000, pp. 399-409.
[3] Berkman, O.; Vishkin, U., Finding level-ancestors in trees, J. comput. system sci., 48, 2, 214-230, (1994) · Zbl 0806.68027
[4] P.F. Dietz, Finding level-ancestors in dynamic trees, in: Workshop on Algorithms and Data Structures (WADS), Ottawa, Canada, 1991, pp. 32-40. · Zbl 0765.68025
[5] Gabow, H.N.; Tarjan, R.E., A linear-time algorithm for a special case of disjoint set union, J. comput. system sci., 30, 2, 209-221, (1985) · Zbl 0572.68058
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.