File BPTree.h

↰ Parent directory (ADS/succinct)

The ordered tree of any degree in 2n bits by its balanced parentheses: a visit in depth writes ‘(’ when it enters a node and ‘)’ when it leaves it, so that a node is the pair of its parentheses and its subtree is what they enclose (the code that the notes use to count the trees of n nodes, the footnote of section 15.2.1).

Definition (ADS/succinct/BPTree.h)

Detailed Description

The nodes are numbered in preorder, node v being the (v + 1)-th ‘(’ at the place :math:` select_1( v + 1 ) , and with the matching of the parentheses [see :ref:`file_ADS_succinct_BalancedParentheses.h]:

  • parent( v ) is enclose() of its ‘(’, leftmostChild( v ) is v + 1 if the next parenthesis is a ‘(’, and rightSibling( v ) the ‘(’ after its ‘)’, if any;

  • subtreeSize( v ) is half the distance from its ‘(’ to its ‘)’, depth( v ) is the excess at its ‘(’ less 1, and u is an ancestor of v if the ‘(’ of v is between the parentheses of u;

in the time of a search in the range min-max tree, :math:` O( log ( n / 512 ) ) ` plus the scan of a block, and O( 1 ) for leftmostChild(), depth() and isLeaf(). Against LOUDS [see File LoudsTree.h], the parentheses also give the size of a subtree, the depth and the ancestors, and number the nodes of a subtree consecutively (from v to v + subtreeSize( v ) - 1), at the price of the searches; DFUDS of Benoit, Demaine, Munro, Raman, Raman and Rao, the degrees in unary in preorder, also gives the i-th child in O( 1 ) time with the same matching, which the notes do not treat.

The contracts [see File Contract.h]: the children lists describe a tree rooted at 0, the parentheses are balanced and enclose one tree, and the nodes are in [ 0 , n ). The functions are defined in BPTree.tpp.

  1. Ferragina, Pearls of Algorithm Engineering, Cambridge University Press, 2023, chapter 15

    1. Munro, V. Raman, Succinct representation of balanced parentheses and static trees, SIAM Journal on Computing 31(3), 762-776, 2001, doi:10.1137/S0097539799364092

  1. Benoit, E. D. Demaine, J. I. Munro, R. Raman, V. Raman, S. S. Rao, Representing trees of higher degree, Algorithmica 43(4), 275-292, 2005, doi:10.1007/s00453-004-1146-6

  1. Navarro, K. Sadakane, Fully functional static and dynamic succinct trees, ACM Transactions on Algorithms 10(3), 16, 2014, doi:10.1145/2601073

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Namespaces

Classes