colPlaLab_inv {treebalance}

Generation of the rooted binary tree corresponding to a given Colijn-Plazzotta rank

Description

This function generates the unique rooted binary tree T (in phylo format) that corresponds to the given Colijn-Plazzotta rank CP(T). It is the inverse function of colPlaLab().

colPlaLab(): For a given rooted binary tree T, CP(T) is recursively defined as CP(T)=1 if T consists of only one vertex and otherwise CP(T)=\frac{1}{2}\cdot CP(T_1)\cdot(CP(T_1)-1)+CP(T_2)+1 with CP(T_1) \geq CP(T_2) being the ranks of the two pending subtrees rooted at the children of the root of T. The rank CP(T) of T corresponds to its position in the lexicographically sorted list of (i,j): (1),(1,1),(2,1),(2,2),(3,1),...

colPlaLab_inv(): For a given rank CP the corresponding tree T can be reconstructed by starting from one vertex \rho (labelled CP) and recursively splitting vertices whose labels h are greater than 1 into two children with the labels:

i=\left\lceil\frac{1+\sqrt{8\cdot h-7}}{2}\right\rceil-1

and

j=h-\frac{i\cdot(i-1)}{2}-1

until there are no more vertices to split.
For CP=1 the function returns the smallest possible tree in the phylo format: the tree consisting of a single edge.

Note that problems can arise for extremely high input values (>10e+18).

For details on the Colijn-Plazzotta rank, see also Chapter 21 in "Tree balance indices: a comprehensive survey" (https://doi.org/10.1007/978-3-031-39800-1_21).

Usage

colPlaLab_inv(rank)

Arguments

rank

An integer denoting the Colijn-Plazzotta rank of the sought tree.

Value

colPlaLab_inv returns the unique rooted binary tree for the given rank.

Author(s)

Sophie Kersting

References

C. Colijn and G. Plazzotta. A Metric on Phylogenetic Tree Shapes. Systematic Biology, 67(1):113-126,2018. doi: 10.1093/sysbio/syx046.

N. A. Rosenberg. On the Colijn-Plazzotta numbering scheme for unlabeled binary rooted trees. Discrete Applied Mathematics, 291:88-98, 2021. doi: 10.1016/j.dam.2020.11.021.

Examples

colPlaLab_inv(22)