Paper Info
Title
Succinct representation of dynamic trees
Abstract
We study the problem of maintaining a dynamic ordered tree succinctly under updates of the following form: insertion or deletion of a leaf, insertion of a node on an edge (edge subdivision) or deletion of a node with only one child (the child becomes a child of its former grandparent). We allow satellite data of a fixed size to be associated to the nodes of the tree. We support update operations in constant amortized time and support access to satellite data and basic navigation operations in worst-case constant time; the basic navigation operations include parent, first/last-child, previous/next-child. These operations are moving from a node to its parent, leftmost/rightmost child, and its previous and next child respectively. We demonstrate that to efficiently support more extended operations, such as determining the i-th child of a node, rank of a child among its siblings, or size of the subtree rooted at a node, one requires a restrictive pattern for update strategy, for which we propose the finger-update model. In this model, updates are performed at the location of a finger that is only allowed to crawl on the tree between a child and a parent or between consecutive siblings. Under this model, we describe how the named extended operations are performed in worst-case constant time. Previous work on dynamic succinct trees (Munro et al., 2001 [17]; Raman and Rao, 2003 [19]) is mainly restricted to binary trees and achieves poly-logarithmic (Munro et al., 2001 [17]) or ''poly-log-log'' (Raman and Rao, 2003 [19]) update time under a more restricted model, where updates are performed in traversals starting at the root and ending at the root and queries can be answered when the traversal is completed. A previous result on ordinal trees achieves only sublinear amortized update time and ''poly-log-log'' query time (Gupta et al., 2007 [11]). More recently, the update time has been improved to O(logn/loglogn) while queries can be performed in O(logn/loglogn) time (Sadakane and Navarro, 2010 [20]).
Year
DOI
Venue
2011
10.1016/j.tcs.2010.10.030
Theor. Comput. Sci.
Keywords
DocType
Volume
Succinct data structures,succinct representation,satellite data,rightmost child,next child,basic navigation operation,query time,worst-case constant time,i-th child,update time,constant amortized time,dynamic tree,Dynamic trees,Ordered trees,extended operation
Journal
412
Issue
ISSN
Citations 
24
Theoretical Computer Science
6
PageRank 
References 
Authors
0.45
10
2
Name
Order
Citations
PageRank
Arash Farzan113611.07
J. Ian Munro23010462.97