File JacobsonTree.h

↰ Parent directory (ADS/succinct)

The binary tree of Jacobson in 2n + 1 bits (section 15.2.1 of the notes): the tree of n nodes is completed with a leaf in place of each missing child, its 2n + 1 nodes are visited by levels, and B gets a 1 for a node of the tree and a 0 for a leaf added.

Definition (ADS/succinct/JacobsonTree.h)

Detailed Description

With the places counted from 1, the children of the x-th node by levels are at the places 2x and 2x + 1, as in a heap, since each node adds its two children to the visit; the node at the place p is the :math:` Rank_1( p ) -th one, and the x-th node is at the place :math: Select_1( x ) , a child of the :math: lfloor Select_1( x ) / 2 rfloor -th one. Hence, with rank and select in O( 1 ) time [see :ref:`file_ADS_succinct_RankSelect.h], left(), right() and parent() take O( 1 ) time, in 2n + 1 + o( n ) bits (Theorem 15.6), against the :math:` Theta( n log n ) ` bits of the pointers. The :math:` 2n - Theta( log n ) ` bits needed to tell apart the :math:` C_n approx 4^n / ( n^{3/2} sqrt{pi} ) ` binary trees of n nodes show that the representation is within O( log n ) bits of the optimum.

The nodes are numbered 0 , … , n - 1 by levels, from the left; node v is at the place :math:` select_1( v + 1 ) ` of B, counted from 0, and the data of the nodes, if any, go in a vector indexed by that number. The representation answers the navigation but not the size of a subtree, which needs the order of a visit in depth [see File BPTree.h].

The contracts [see File Contract.h]: the children lists describe a binary tree rooted at 0, and B is the code of a binary tree (2n + 1 bits, the x-th 1 before the places 2x and 2x + 1, an audit); the nodes are in [ 0 , n ). The functions are defined in JacobsonTree.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. Navarro, Compact Data Structures: A Practical Approach, Cambridge University Press, 2016, chapter 8, doi:10.1017/CBO9781316588284

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Namespaces

Classes