Succinct Dynamic Cardinal Trees with Constant Time Operations for Small Alphabet

Abstract. 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 + n log k + o(n log k) 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(log log n), and the update time of O((log log n) 2 / log log log n) to O(1), solving an open problem in [1].