colPlaLab_inv: Generation of the rooted binary tree corresponding to a given...
In treebalance: Computation of Tree (Im)Balance Indices

Description Usage Arguments Value Author(s) References Examples

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() with the method 'binary'.

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)=1/2*CP(T1)(CP(T1)-1)+CP(T2)+1 with CP(T1)>=CP(T2) being the ranks of the two pending subtrees rooted at the children 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 ρ (labelled CP) and recursively splitting vertices whose labels h are greater than 1 into two children with the labels:

i=ceil((1+sqrt(8*h-7))/2)-1

and

j=h-(i*(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).

1	colPlaLab_inv(rank)

rank

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

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

Sophie Kersting

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.