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).
colPlaLab_inv(rank)colPlaLab_inv returns the unique rooted binary tree for the given rank.
An integer denoting the Colijn-Plazzotta rank of the sought tree.
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.