# Computing RF Tree Distance over Succinct Representations
## 3 Methodology
### Robinson-Foulds Distance Computation  
To compute the Robinson-Foulds distance, our algorithm receives as input two bit vectors that represent the two trees being compared, as well as a mapping between tree indexes. This mapping can be represented by an array of \(n\) integers such that the position of each integer corresponds to the index minus one on the first tree, and the integer value at that position in the array corresponds to the index on the second tree. This way, it is possible to obtain the index of the node with a given label in the second tree given the index of where it is in the first tree. We notice that we only maintain the indexes that correspond to have labels, the others remain with a value of zero. An example of this map for the trees in Figures 4 and 5 is  
\[ \begin{array}{ccccccccccccc}\text{index on }T_{5}&[&0&0&9&7&10&0&3&4&5 \\ \text{index on }T_{4}\text{ (-1)}&0&1&2&3&4&5&6&7&8&9\end{array} ]. \tag{1}\] \begin{table}
\begin{tabular}{l l l} \hline
**Operation** & **Meaning** & **Complexity** \\ \hline \multirow{4}{*}{Enclose(\(bv,p\))} & Returns the position where the smaller & \multirow{4}{*}{\(O(\log(n))\)} \\  & segment strictly containing \(p\) is located, & \\  & with every two matching parentheses & \\  & defining a segment. & \\ \multirow{4}{*}{Excess(\(bv,p\))} & Returns the number of opening minus the & \multirow{4}{*}{\(O(1)\)} \\  & number of closing parentheses until \(p\). & \\ \multirow{4}{*}{\(\text{FindOpen(\(bv,p\))}\)} & Given a position \(p\), returns the position of & \\  & the corresponding opening parenthesis. & \\ \multirow{4}{*}{\(\text{FindClose(\(bv,p\))}\)} & Given a position \(p\), returns the position of & \\  & the corresponding closing parenthesis. & \\ \multirow{4}{*}{\(\text{rmq}(bv,l,r)\)} & Given two positions \(l\) and \(r\), returns the & \\  & position with minimum excess in range \([l..r]\). & \\ \hline \multirow{4}{*}{ClusterSize(\(bv,p\))} & Given the opening position \(p\) of a node, & \multirow{4}{*}{\(O(\log(n))\)} \\  & returns the size of the cluster with that & \\  & node as root. & \\ \multirow{4}{*}{\(\text{FirstChild(\(bv,p\))}\)} & Given the opening position \(p\) of a node, & \multirow{4}{*}{\(O(1)\)} \\  & returns the position for its first child. & \\ \multirow{4}{*}{IsLeaf(\(bv,p\))} & Given the opening position \(p\) of a node, & \multirow{4}{*}{\(O(1)\)} \\  & returns True it is a leaf and False otherwise. & \\ \multirow{4}{*}{\(\text{LCA(\(bv,l,r\))}\)} & Given the opening positions \(l\) and \(r\) of two & \\  & nodes, returns the opening position of their & \\  & lowest common ancestor. & \\ \multirow{4}{*}{\(\text{NumLeaves(\(bv,p\))}\)} & Given the opening position \(p\) of a node, & \multirow{4}{*}{\(O(\log(n))\)} \\  & returns the number of leaves that have that & \\  & node as ancestor. & \\ \multirow{4}{*}{\(\text{PostOrderSelect(\(bv,i\))}\)} & Given the post-order traversal index \(i\) of a & \\  & node, returns its opening position. & \\ \multirow{4}{*}{\(\text{PreOrderMap(\(bv,p\))}\)} & Given an opening position \(p\) of a node, & \multirow{4}{*}{\(O(1)\)} \\  & returns its pre-order traversal index. & \\ \multirow{4}{*}{\(\text{PreOrderSelect(\(bv,i\))}\)} & Given the pre-order traversal index \(i\) of a & \\  & node, returns its opening position. & \\ \hline \end{tabular}
\end{table} 
Table 1: \(Cont.\)As mentioned before, this mapping can be represented in a more compact form. If we take the labels in the trees and enumerate them in some canonical order, assigning them identifiers from \(1\) to \(n\), then each tree represents a permutation \(\pi\) of that enumeration. Hence, given \(T\) and the associated permutation \(\pi\), \(\pi[i]\) is the label at the node of \(T\) with index \(i\), and \(\pi^{-1}[i]\) is the index of the node of \(T\) with label \(i\), for \(i\in\{1,\dots,n\}\). By composing both permutations, we can determine the bijection among the nodes of both trees.