Representing Dynamic Binary Trees Succinctly

We introduce a new updatable representation f binary trees. The structure requires the information theoretic minimum 2n + o(n) bits and supports basic navigational operations in constant time and subtree size in O(lg n). In contrast o the linear update costs of previously proposed succinct repre-sentations, our representation supports updates in O(lg 2 n) amortized time. 1 Introduct ion Trees, particularly binary trees, are elementary struc-tures in many aspects of computing. The standard rep-resentation of a tree, with a pointer or two per parent-child relationship, is easy to navigate and update. Fur-thermore, the structure can be easily augmented so that operations uch as determining subtree size can also be supported in constant ime. Unfortunately, this repre-sentation can be very costly, even prohibitive, in terms of space. This is particularly true in applications uch as text indexing, where the node of a binary tree corre-sponds to an index point in a text file. Taking this reasonable point of view that a pointer used in representing an n node tree takes lg n bits, the usual representation of a binary tree requires 2nigh bits (even without parent pointers). On the other hand, a binary tree can be represented in fewer than 2n bits, as there are only (2~)/(n + 1) or about 22'~/n a/2 binary trees on n nodes. Indeed Jacobson[5], Munro and Raman[7], and others have proposed 2n + o(n) bit representations that permit fast navigation of a tree. These approaches, and the work presented here, all lead to a mapping from the n (internal) nodes of a tree onto the integers [1, n/and from the external nodes onto the integers [1, n + 1]. This leads to a way of associating auxiliary data with nodes and external nodes. Most of these approaches, however, are inherently static. The focus of this paper is a succinct, quickly navigable and updatable representation of binary trees. Our representations deal with arbitrary binary trees on