Improved algorithms for finding level ancestors in dynamic trees

被引:0
作者
Alstrup, S [1 ]
Holm, J [1 ]
机构
[1] IT Univ Copenhagen, DK-2400 Copenhagen, Denmark
来源
AUTOMATA LANGUAGES AND PROGRAMMING | 2000年 / 1853卷
关键词
D O I
暂无
中图分类号
TP31 [计算机软件];
学科分类号
081202 ; 0835 ;
摘要
Given a node a: at depth d in a rooted tree LevelAncestor(x, i) returns the ancestor to a 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 (P.F. Dietz, Finding level-ancestors in dynamic trees, LNCS, 519:32-40, 1991). 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 (e.g. R.E. Tarjan. Applications of path compression on balanced trees. J.ACM, 26(4):690-715, 1979).
引用
收藏
页码:73 / 84
页数:12
相关论文
共 30 条
[1]  
Alstrup S, 1997, LECT NOTES COMPUT SC, V1256, P270
[2]  
ALSTRUP S, 1999, 31 ACM S THEO COMP, P499
[3]  
ALSTRUP S, 2000, 7 SCAN WORK ALG THEO
[4]  
ALSTRUP S, 1996, IN PRESS J ALGO, V1097, P212
[5]  
Beame P., 1999, Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, P295, DOI 10.1145/301250.301323
[6]   FINDING LEVEL-ANCESTORS IN TREES [J].
BERKMAN, O ;
VISHKIN, U .
JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1994, 48 (02) :214-230
[7]   RECURSIVE STAR-TREE PARALLEL DATA STRUCTURE [J].
BERKMAN, O ;
VISHKIN, U .
SIAM JOURNAL ON COMPUTING, 1993, 22 (02) :221-242
[8]  
BUCHSBAUM A, 1998, 30 ACM S THEO COMP, P279
[9]   COMPUTING ON A FREE TREE VIA COMPLEXITY-PRESERVING MAPPINGS [J].
CHAZELLE, B .
ALGORITHMICA, 1987, 2 (03) :337-361
[10]  
DIETZ P, 1991, LNCS, V1097, P32