A DATA STRUCTURE FOR DYNAMICALLY MAINTAINING ROOTED TREES

Authors
FREDERICKSON GN
Citation
Gn. Frederickson, A DATA STRUCTURE FOR DYNAMICALLY MAINTAINING ROOTED TREES, Journal of algorithms, 24(1), 1997, pp. 37-65
Citations number
23
Categorie Soggetti
Mathematics,Mathematics,"Computer Science Theory & Methods
Journal title
Journal of algorithms → ACNP
ISSN journal
01966774
Volume
24
Issue
1
Year of publication
1997
Pages
37 - 65
Database
ISI
SICI code
0196-6774(1997)24:1<37:ADSFDM>2.0.ZU;2-#
Abstract
The directed topology tree data structure is developed for maintaining binary trees dynamically. Each of a certain set of tree operations is shown to take O(logn) time, where n is the number of vertices in the trees. The directed topology trees are used to implement link-cut tree s and dynamic expression trees. The results of experimental comparison s with the dynamic trees of Sleator and Tarjan are presented. (C) 1997 Academic Press.