  The associahedron $\mathcal{A}(G)$ of a graph $G$ has the property that its
vertices can be thought of as the search trees on $G$ and its edges as the
rotations between two search trees. If $G$ is a simple path, then
$\mathcal{A}(G)$ is the usual associahedron and the search trees on $G$ are
binary search trees. Computing distances in the graph of $\mathcal{A}(G)$, or
equivalently, the rotation distance between two binary search trees, is a major
open problem. Here, we consider the different case when $G$ is a complete split
graph. In that case, $\mathcal{A}(G)$ interpolates between the stellohedron and
the permutohedron, and all the search trees on $G$ are brooms. We show that the
rotation distance between any two such brooms and therefore the distance
between any two vertices in the graph of the associahedron of $G$ can be
computed in quasi-quadratic time in the number of vertices of $G$.
