The Level Ancestor Problem simplified

被引：94

作者：

Bender, MA ^{[1
]}

Farach-Colton, M

机构：

[1] SUNY Stony Brook, Dept Comp Sci, Stony Brook, NY 11794 USA

[2] Rutgers State Univ, Dept Comp Sci, Piscataway, NJ 08854 USA

来源：

THEORETICAL COMPUTER SCIENCE | 2004年 / 321卷 / 01期

关键词：

data structures; rooted trees; Level Ancestor Problem;

D O I：

10.1016/j.tcs.2003.05.002

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

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. (C) 2003 Elsevier B.V. All rights reserved.

引用

页码：5 / 12

页数：8

共 5 条

[1]

Alstrup S, 2000, LECT NOTES COMPUT SC, V1853, P73

[2] Cache-oblivious B-trees [J].

Bender, MA ;

Demaine, ED ;

Farach-Colton, M .

41ST ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, PROCEEDINGS, 2000, :399-409

[3] FINDING LEVEL-ANCESTORS IN TREES [J].

BERKMAN, O ;

VISHKIN, U .

JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1994, 48 (02) :214-230

[4]

DIETZ PF, 1991, WORKSH ALG DAT STRUC, P32

[5] A LINEAR-TIME ALGORITHM FOR A SPECIAL CASE OF DISJOINT SET UNION [J].

GABOW, HN ;

TARJAN, RE .

JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1985, 30 (02) :209-221

← 1 →