Academic
Publications
Succinct Dynamic Cardinal Trees with Constant Time Operations for Small Alphabet

Succinct Dynamic Cardinal Trees with Constant Time Operations for Small Alphabet,10.1007/978-3-642-20877-5_21,Pooya Davoodi,Satti Srinivasa Rao

Succinct Dynamic Cardinal Trees with Constant Time Operations for Small Alphabet  
BibTex | RIS | RefWorks Download
A k-ary cardinal tree is a rooted tree in which each node has at most k children, and each edge is labeled with a symbol from the alphabet {1,...,k}. We present a succinct representation for k-ary cardinal trees of n nodes where k = O(polylog(n)). Our data structure requires 2n + nlogk + o(nlogk) bits and performs the following operations in O(1) time: parent, child(i) label-child(α), degree, subtree-size, preorder, is-ancestor(x), insert-leaf(α), delete-leaf(α). The update times are amortized. The space is close to the information theoretic lower bound. The operations are performed in the course of traversing the tree. This improves the succinct dynamic k-ary cardinal trees representation of Arroyuelo [1] for small alphabet, by speeding up both the query time of O(loglogn), and the update time of O((loglogn)2/logloglogn) to O(1), solving an open problem in [1].
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.