Given a rooted tree T, the level ancestor problem aims to answer queries of the form LA(v, d), which identify the level d ancestor of a node v in the tree. Several algorithms of varied complexity have been proposed for this problem in the literature, including optimal solutions that preprocess the tree $T$ in linear bounded time and proceed to answer queries in constant time. Despite its significance and numerous applications, to date there have been no comparative studies of the performance of these algorithms and few implementations are widely available. In our experimental study we implemented and compared several solutions to the level ancestor problem, including three theoretically optimal algorithms, and examined their space requirements and time performance in practice.
翻译:根植树 T, 水平祖先问题旨在回答LA(v, d) 形式的询问,该表确定了节点相对于树中的节点的祖先水平。文献中为这一问题提出了几种复杂程度不同的算法,包括以线性约束时间预先处理树的优化解决办法,在线性约束时间里先处理$T,然后不断地回答询问。尽管其重要性和多种应用,但迄今为止对这些算法的性能还没有进行比较研究,而且很少有人可以广泛应用。在我们的实验研究中,我们实施了几项解决方案,并比较了水平祖先问题,包括三个理论上最优的算法,并审查了它们的空间要求和实际时间性能。