File LoudsTree.h

↰ Parent directory (ADS/succinct)

The ordered tree of any degree in 2n + 1 bits by LOUDS, the level-order unary degree sequence of Jacobson (section 15.2.2 of the notes): a dummy root of degree 1 is put above the root, the nodes are visited by levels, and the degree d of each one is written in unary as :math:` 0^d 1 `, so that B has n 0s, one per node (each one is the child of somebody), and n + 1 1s, one per node and the dummy root (Theorem 15.7).

Definition (ADS/succinct/LoudsTree.h)

Detailed Description

The k-th 0 is the k-th node by levels, and the children of the k-th node are the 0s after the (k + 1)-th 1, the 1 of the dummy root counting first; hence, with rank and select [see File RankSelect.h], in O( 1 ) time:

  • :math:` degree( x ) = Select_1( x + 1 ) - Select_1( x ) - 1 `;

  • :math:` parent( x ) = Rank_1( Select_0( x ) ) = Select_0( x ) - x `;

  • :math:` firstChild( x ) = Select_1( x ) + 1 - x `, unless the degree is 0;

  • :math:` nextSibling( x ) = x + 1 ` if the bit after :math:` Select_0( x ) ` is 0, none otherwise;

with the nodes and the places counted from 1, as in the notes; here they count from 0 (the root is node 0, at the place 0 of B), and the functions are leftmostChild() and rightSibling(), with the names of the TREE of the book [see File Tree.h]. The i-th child is the first one plus i, since the children of a node are consecutive in the order by levels, which a visit in depth does not give. LOUDS does not answer the size of a subtree nor the depth of a node, which the parentheses of a visit in depth do [see File BPTree.h], at the price of a range min-max tree; it is the simplest of the succinct trees and the fastest for the navigation from the root down (Arroyuelo, Canovas, Navarro and Sadakane), e.g., in the tries of the indices.

The contracts [see File Contract.h]: the children lists describe a tree rooted at 0, B is a code of LOUDS (n 0s and n + 1 1s, no prefix with more 0s than 1s before the last 1, an audit), and the nodes are in [ 0 , n ). The functions are defined in LoudsTree.tpp.

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

  1. Jacobson, Space-efficient static trees and graphs, Proc. 30th FOCS, 549-554, 1989, doi:10.1109/SFCS.1989.63533

  1. Arroyuelo, R. Canovas, G. Navarro, K. Sadakane, Succinct trees in practice, Proc. 12th ALENEX, 84-97, 2010, doi:10.1137/1.9781611972900.9

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Namespaces

Classes