\section{Introduction}
  Most of the classical linear partial differential equations arising in mathematical physics
  can be written in a common operator form. It has been shown in \cite{Picard} that this form
  is an evolutionary problem, given by
  \begin{equation}\label{eq:evo}
    (\partial_tM_0+M_1+A)U=F,
  \end{equation}
  where $\partial_t$ stands for the derivative with respect to time,
  $M_0$ and $M_1$ are bounded linear operators on some Hilbert space $H$,
  $A$ is an unbounded skew-selfadjoint operator on $H$
  and $F$ is a given source term.

  We are interested in a unique solution $U$ of above equation. The theory presented in \cite{Picard}
  deals vanishing initial conditions at $t\to-\infty$, but any non-zero initial condition
  can be incorporated as data into $F$.
  For this purpose let $\rho> 0$ and define the weighted $L^2$-function space
  \[
    H_\rho(\mathbb{R};H):=
      \left\{
          f:\mathbb{R}\to H\,:\, f \mbox{ meas.},
          \int_\mathbb{R} \norm{f(t)}{H}^2 \exp(-2\rho t) \,\mathrm{d}t<\infty
      \right\}.
  \]
  The space $H_\rho(\mathbb{R};H)$ is a Hilbert space endowed with the natural inner
  product given by
  \[
    \scpr{f,g}\,:=
    \int_{\mathbb{R}} \scp{f(t),g(t)} \exp(-2\rho t) \,\mathrm{d}t
  \]
  for all $f,g\in H_\rho(\mathbb{R};H)$, where $\scp{f(t),g(t)}$ is the inner product of $H$.
  The associated weighted $H^k$-function spaces are denoted by $H_\rho^k(\mathbb{R};H)$ for $k\in \mathbb{N}$.
  Now the solution theory of \cite{Picard} states: If there exists a $\rho_0>0$ and a $\gamma>0$
  such that
  \[
    \rho M_0+M_1\geq \gamma\quad\text{for all }\rho\geq\rho_0,
  \]
  then for all right hand sides $F\in H_{\rho}(\mathbb{R},H)$ exists a unique solution $U\in H_{\rho}(\mathbb{R},H)$.

  In \cite{FrTW16} this class of problems was investigated numerically using
  a discontinuous Galerkin approach for the discretisation in time. Here we want to apply
  a continuous approach, namely the continuous Galerkin-Petrov method \cite{Winther81,AM89,Schieweck10,AM15}.
  Like in \cite{FrTW16} we will consider a special subclass of the general class of evolutionary problems,
  although the approach of the time-discretisation is suitable in the general case.

  For the precise class of problems let $n\in\{1,2,3\}$ be the spatial dimension and
  $\Omega\subset \mathbb{R}^n$ be partitioned into measurable, disjoint sets
  $\Omega_{\mathrm{ell}},\Omega_{\mathrm{par}}$ and $\Omega_{\mathrm{hyp}}$. Denoting by $\id{D}$
  the characteristic function of a domain $D\subset\Omega$ we define the linear operators
  \[
    M_0=\begin{pmatrix}[c]
            \id{\Omega_{\mathrm{hyp}}\cup\Omega_{\mathrm{par}}} & 0\\
            0 &\id{\Omega_{\mathrm{hyp}}}
        \end{pmatrix}\quad\text{and}\quad
    M_1=\begin{pmatrix}[c]
          \id{\Omega_{\mathrm{ell}}} & 0 \\
          0 & \id{\Omega_{\mathrm{par}}\cup\Omega_{\mathrm{ell}}}
        \end{pmatrix}.
  \]
  Additionally let the unbounded skew-selfadjoint operator A be given by
  \[
    A=\begin{pmatrix}[c]
          0 & \operatorname{div}\\
          \operatorname{grad}^\circ &0
       \end{pmatrix}.
  \]
  Here $^\circ$ denotes the homogeneous Dirichlet boundary conditions. The Hilbert space $H$ can now be
  specified to
  \[
    H(\Omega)=H_0^1(\Omega)\otimes H_{\operatorname{div}}(\Omega).
  \]

  The resulting evolutionary problem is now of mixed type. More precisely,
  on $\Omega_{\mathrm{ell}}$ we get an equation of elliptic type,
  on $\Omega_{\mathrm{par}}$ the equations becomes parabolic while
  on $\Omega_{\mathrm{hyp}}$ the problem is hyperbolic.

  The solution theory of \cite{Picard} does not only give for a final time $T>0$ and $F\in H_\rho([0,T],H)$
  the existence of a unique solution $U\in H_\rho([0,T],H)$.
  It holds in addition $M_0U\in H_\rho^1([0,T],H)$ and therefore, by the Sobolev embedding theorem, $M_0U$ is continuous in time.
  If the right-hand side is smoother, say $F\in H_\rho^1([0,T],H)$, and $F$
  and $(M_1+A)U_0$ are in the range of $M_0$, then the continuity in time of the solution
  is everywhere and we have, see \cite{TW19}
  \[
    U\in H_\rho^1([0,T],H)\subset C([0,T],H).
  \]
  In the following we want to utilise this additional regularity.
  Section~\ref{sec:method} gives the precise formulation of the method considered.
  Section~\ref{sec:exist} then deals with the existence of discrete solutions,
  Section~\ref{sec:error} presents error estimates and finally
  Section~\ref{sec:numerics} gives some numerical examples and conclusions.

\section{Numerical method}\label{sec:method}
  Let us start wit a semi-discretisation in time.
  The semi-discrete variational form of \eqref{eq:evo} uses a decomposition of $[0,T]$ into $M$
  disjoint intervals $I_m=(t_{m-1},t_m]$ of length $\tau_m=t_m-t_{m-1}$ for $m\in\{1,\dots,M\}$
  and the piecewise polynomial-in-time spaces
  \begin{align*}
    \mathcal{U}^\tau&:=\{u\in H^1_\rho(\mathbb{R},H):u\big|_{I_m}\in\mathcal{P}_{r}(I_m,H),m\in\{1,\dots,M\}\},\\
    \mathcal{V}^\tau&:=\{v\in H_\rho(\mathbb{R},H):v\big|_{I_m}\in\mathcal{P}_{r-1}(I_m,H),m\in\{1,\dots,M\}\}
  \end{align*}
  for the trial and the test functions, where $\mathcal{P}_r(I_m,H)$ is the space of polynomials of degree up to $r$
  on $I_m$ with values in $H$. Let us localise the scalar product in $H_\rho(\mathbb{R},H)$
  to the time intervals $I_m$ by
  \[
    \scprm{f,g}\,:=
    \int_{I_m} \scp{f(t),g(t)} \exp(-2\rho t) \,\mathrm{d}t.
  \]
  Then the variational formulation using the continuous Galerkin-Petrov method reads:\\
  Find $U^\tau\in\mathcal{U}^\tau$ such that for all $V^\tau\in\mathcal{V}^\tau$ and $m\in\{1,\dots,M\}$
  \begin{align}
    \scprm{(\partial_t M_0+M_1+A)U^\tau,V^\tau}&=\scprm{f,V^\tau}=\scprm{\Pi_{r-1}f,V^\tau},\label{eq:evosemidisc}\\
    U^\tau(t_{m-1}^+)&=U^\tau(t_{m-1}^-),\notag
  \end{align}
  where $\Pi_{r-1}$ denotes the weighted $L^2$-projection into $\mathcal{V}^\tau$ and $U^\tau(0^-)=U_0$ is
  the initial value.

  In order to compute an approximation to the solution of problem \eqref{eq:evo}, we need
  also to discretise the spatial domain and the function space $H$. Let $\Omega$ be discretised
  into $\Omega_h$ by a regular simplicial mesh that resolves the sets $\Omega_{\mathrm{ell}},\,
  \Omega_{\mathrm{par}}$ and $\Omega_{\mathrm{hyp}}$, and let $h$ be the maximal diameter
  of the cells of $\Omega_h$. Furthermore, let $k\geq 0$ denote a polynomial degree.
  Then the discrete spaces are given by
  \begin{align*}
    \mathcal{U}^\tau_h
    \!&:=\! \left\{
          u_h\in\mathcal{U}^\tau\!:
          u_h|_{I_m}\!\in\mathcal{P}_r(I_m,V_1\otimes V_2),
          m\!\in\!\{1,\dots,M\}
       \right\},\\
    \mathcal{V}^\tau_h
    \!&:=\! \left\{
          v_h\in\mathcal{V}^\tau\!:
          v_h|_{I_m}\!\in\mathcal{P}_{r-1}(I_m,V_1\otimes V_2),
          m\!\in\!\{1,\dots,M\}
       \right\},
  \end{align*}
  where the spatial spaces are
  \begin{align*}
    V_1&:=\left\{v\in H_0^1(\Omega):\,v|_\sigma\in\mathcal{P}_k(\sigma)\,\forall \sigma\in\Omega_h\right\},\\
    V_2&:=\left\{w\in H_{\operatorname{div}}(\Omega):\,w|_\sigma\in RT_{k-1}(\sigma)\,\forall \sigma\in\Omega_h\right\}.
  \end{align*}
  Here $\mathcal{P}_k(\sigma)$ is the space of polynomials of degree up to $k$ on
  the cell $\sigma$ and $RT_{k-1}(\sigma)$ is the Raviart-Thomas-space, defined by
  \[
    RT_{k-1}(\sigma)=(\mathcal{P}_{k-1}(\sigma))^n+\mathbf{x}\mathcal{P}_{k-1}(\sigma)\subset\mathcal{P}_k(\sigma)^n.
  \]
  The fully discrete method then reads similarly to \eqref{eq:evosemidisc}:\\
  Find $U^\tau_h\in\mathcal{U}^\tau_h$ such that for all $V^\tau_h\in\mathcal{V}^\tau_h$ and $m\in\{1,\dots,M\}$
  \begin{align}
    B_m(U^\tau_h,V^\tau_h):=
    \scprm{(\partial_t M_0+M_1+A)U^\tau_h,V^\tau_h}&=\scprm{f,V^\tau_h},\label{eq:evodisc}\\
    U^\tau_h(t_{m-1}^+)&=U^\tau_h(t_{m-1}^-),\notag
  \end{align}
  where and $U^\tau_h(0^-)=U_0$ is the initial value.

\section{Existence of discrete solution}\label{sec:exist}
  Let us start by choosing $V^\tau_h=\Pi_{r-1}U^\tau_h$, the $L^2$-projection of $U^\tau_h$
  into the test space $\mathcal{V}^\tau_h$ and denote by
  \[
    \norm{f}{\rho,[0,t_\ell]}^2:=\sum_{m=1}^\ell\scprm{f,f}
  \]
  a localised version of $\norm{f}{\rho}^2=\scpr{f,f}$.

  \begin{lemma}\label{lem:exist}
    It holds for all $\ell\geq 1$
    \[
      \scp{M_0 U^\tau_h(t_\ell),U^\tau_h(t_\ell)}_H\mathrm{e}^{-2\rho t_\ell}+
      \gamma\norm{\Pi_{r-1}U^\tau_h}{\rho,[0,t_\ell]}^2
      \leq\sum_{k=1}^\ell B_k(U^\tau_h,\Pi_{r-1}U^\tau_h)+\scp{M_0 U_0,U_0}_H.
    \]
  \end{lemma}
  \begin{proof}
    Let us consider any interval $I_m$. Then it holds
    \[
      B_m(U^\tau_h,\Pi_{r-1}U^\tau_h)
        = \scprm{\partial_t M_0 U^\tau_h,U^\tau_h}+\scprm{M_1 \Pi_{r-1}U^\tau_h,\Pi_{r-1}U^\tau_h},
    \]
    where the skew-symmetry of $A$ and the definition of $\Pi_{r-1}$ was used.

    For the first term we apply integration by parts and obtain due to the exponential weight
    \[
      \scprm{\partial_t M_0 U^\tau_h,U^\tau_h}
        =\rho\scprm{M_0 U^\tau_h,U^\tau_h}+\scp{M_0 U^\tau_h(t),U^\tau_h(t)}_H\mathrm{e}^{-2\rho t}\big|_{t_{m-1}}^{t_m}.
    \]
    By the $L^2$-orthogonality it follows
    \begin{align*}
      \scprm{M_0 U^\tau_h,U^\tau_h}
        &= \scprm{M_0 (U^\tau_h-\Pi_{r-1}U^\tau_h),U^\tau_h-\Pi_{r-1}U^\tau_h}+\scprm{M_0 \Pi_{r-1}U^\tau_h,\Pi_{r-1}U^\tau_h}\\
        &\geq \scprm{M_0 \Pi_{r-1}U^\tau_h,\Pi_{r-1}U^\tau_h}
    \end{align*}
    and therefore
    \[
      \scprm{\partial_t M_0 U^\tau_h,U^\tau_h}
        \geq \scprm{\rho M_0 \Pi_{r-1}U^\tau_h,\Pi_{r-1}U^\tau_h}+\scp{M_0 U^\tau_h(t),U^\tau_h(t)}_H\mathrm{e}^{-2\rho t}\big|_{t_{m-1}}^{t_m}.
    \]
    With the general existence assumption $\rho M_0+M_1\geq \gamma$
    and $M_0\geq 0$ we obtain
    \begin{gather}
      B_m(U^\tau_h,\Pi_{r-1}U^\tau_h)
        \geq \gamma\norm{\Pi_{r-1}U^\tau_h}{\rho,m}^2+
              \scp{M_0 U^\tau_h(t),U^\tau_h(t)}_H\mathrm{e}^{-2\rho t}\big|_{t_{m-1}}^{t_{m}}.\label{eq:lowerbound}
    \end{gather}
    Summing over the intervals the statement follows.
  \end{proof}
  With Lemma~\ref{lem:exist} we have control over the $L^2$-projection of the solution $U^\tau_h$ and of the final value of $\norm{M_0^{1/2}U^\tau_h(t)}{H}$.
  In order to obtain control of the full solution $U$ we consider two approaches.

  \textbf{1) $\mathbf{M_0}$ has a trivial null space}\\
  In this case we employ the norm equivalence in discrete spaces
  \[
    \norm{U^\tau_h}{\rho,m}^2\sim\norm{\Pi_{r-1}U^\tau_h}{\rho,m}^2+\tau_m\scp{M_0 U^\tau_h(t_m),U^\tau_h(t_m)}_H\mathrm{e}^{-2\rho t_m}
  \]
  with constants independent of $\tau_m$ and $U^\tau_h$ and we obtain
  \begin{align*}
    \norm{U^\tau_h}{\rho,[0,T]}^2
      &\leq C\left[\norm{\Pi_{r-1}U^\tau_h}{\rho,[0,T]}^2
        +\sum_{m=1}^M\tau_m\scp{M_0U^\tau_h(t_m),U^\tau_h(t_m)}_H\mathrm{e}^{-2\rho t_m}\right]\\
      &\leq C\left(\frac{1}{\gamma}+T\right)\left[\sum_{m=1}^MB_m(U^\tau_h,\Pi_{r-1}U^\tau_h)+\scp{M_0 U_0,U_0}_H\right]\\
      &\leq C\left(\frac{1}{\gamma}+T\right)\left[\scp{\Pi_{r-1}f,U^\tau_h}_{\rho,[0,T]}+\scp{M_0 U_0,U_0}_H\right].
  \end{align*}
  Applying a Young inequality we have
  \begin{align*}
    \norm{U^\tau_h}{\rho,[0,T]}^2
      &\leq C^2\left(\frac{1}{\gamma}+T\right)^2\norm{f}{\rho,[0,T]}^2+
                2C\left(\frac{1}{\gamma}+T\right)\scp{M_0 U_0,U_0}_H
  \end{align*}
  Therefore, in the case of $M_0$ with only trivial null-space the linear system is solvable
  and we also have continuous dependence of the solution $U^\tau_h$ on the data.

  \textbf{2) $\mathbf{M_0}$ may have a non-trivial null space}\\
  Here we can apply another norm-equivalence to show the solvability of the discrete systems.
  Using $\rho M_0+M_1\geq\gamma>0$ we have the norm equivalence
  \[
    \norm{U^\tau_h}{\rho,m}^2\sim\norm{\Pi_{r-1}U^\tau_h}{\rho,m}^2+\tau_m\scp{(\rho M_0+M_1) U^\tau_h(t_{m-1}),U^\tau_h(t_{m-1})}_H\mathrm{e}^{-2\rho t_{m-1}}
  \]
  with constants independent of $\tau_m$ and $U^\tau_h$.
  Using a similar approach as before we obtain
  \begin{align*}
    \norm{U^\tau_h}{\rho,[0,T]}^2
      &\leq C\Bigg[\frac{1}{\gamma}\left(\sum_{m=1}^MB_m(U^\tau_h,\Pi_{r-1}U^\tau_h)+\scp{M_0 U_0,U_0}_H\right)\\
      &\qquad      +\sum_{m=1}^{M-1}\rho\tau_{m+1}\left(\sum_{n=1}^m B_n(U^\tau_h,\Pi_{r-1}U^\tau_h)+\scp{M_0 U_0,U_0}_H\right)+\rho\tau_1\scp{M_0U_0,U_0}_H\\
      &\qquad      +\sum_{m=1}^M\tau_m\scp{M_1 U^\tau_h(t_{m-1}),U^\tau_h(t_{m-1})}_H\mathrm{e}^{-2\rho t_{m-1}}\Bigg]\\
      &\leq C\Bigg[\frac{1}{\gamma}\left(\scp{\Pi_{r-1}f,U^\tau_h}_{\rho,[0,T]}+\scp{M_0 U_0,U_0}_H\right)\\
      &\qquad      +\sum_{m=1}^{M-1}\rho\tau_{m+1}\left(\scp{\Pi_{r-1}f,U^\tau_h}_{\rho,[0,t_m]}+\scp{M_0 U_0,U_0}_H\right)+\rho\tau_1\scp{M_0U_0,U_0}_H\\
      &\qquad      +\sum_{m=1}^M\tau_m\scp{M_1 U^\tau_h(t_{m-1}),U^\tau_h(t_{m-1})}_H\mathrm{e}^{-2\rho t_{m-1}}\Bigg]\\
      &\leq C\Bigg[\left(\frac{1}{\gamma}+\rho T\right)\norm{\Pi_{r-1}f}{\rho,[0,T]}\norm{U^\tau_h}{\rho,[0,T]}+\left(\frac{1}{\gamma}+\rho (T+\tau_1)\right)\scp{M_0 U_0,U_0}_H\\
      &\qquad      +T\max_{m\in\{1,\dots,M\}}\scp{M_1 U^\tau_h(t_{m-1}),U^\tau_h(t_{m-1})}_H\mathrm{e}^{-2\rho t_{m-1}}\Bigg].
  \end{align*}
  With a Young inequality follows
  \begin{multline*}
    \norm{U^\tau_h}{\rho,[0,T]}^2
      \leq C^2\left(\frac{1}{\gamma}+\rho T\right)^2\norm{f}{\rho,[0,T]}^2+2C\left(\frac{1}{\gamma}+\rho (T+\tau_1)\right)\scp{M_0 U_0,U_0}_H\\
      \qquad      +2CT\max_{m\in\{1,\dots,M\}}\scp{M_1 U(t_{m-1}),U(t_{m-1})}_H\mathrm{e}^{-2\rho t_{m-1}}.
  \end{multline*}
  Therefore, also in the general case the linear system is solvable
  and the solution on each time interval depends continuously on the data and the initial value of the time interval.

\section{Error-estimation}\label{sec:error}
  \subsection{Semi discretisation in time}
    Note that we do have the Galerkin orthogonality
    \begin{gather}\label{eq:Galorth}
      B_m(U-U^\tau,V)=0
    \end{gather}
    for the solution $U\in H_\rho^1(\mathbb{R},H)$ of \eqref{eq:evo} for $F\in H_\rho^1(\mathbb{R},H)$
    and $U^\tau\in \mathcal{U}^\tau$ of \eqref{eq:evosemidisc}. We now want to estimate the error $U-U^\tau$.
    Let $P_r:H_\rho^1([0,T],H)\to\mathcal{U}^\tau$ be the interpolation operator fulfilling locally
    for all $m$ and $v\in H_\rho^1([0,T],H)$
    \begin{align*}
      (P_rv-v)(t_{m-1})&=0,\\
      (P_rv-v)(t_{m})&=0,\\
      \scprm{P_ru-u,w}&=0\quad\forall w\in\mathcal{P}_{r-2}(I_m,H).
    \end{align*}
    We decompose the error into $u-U=\eta+\xi$, where
    \[
      \eta=u-P_ru,\quad
      \xi=P_ru-U\in\mathcal{U}^\tau.
    \]
    \begin{lemma}
      It holds for any $m\in\{1,\dots,M\}$
      \begin{gather}\label{eq:errineq}
        \scprm{(\partial_t M_0+M_1+A)\xi,V}
          \leq\left(\norm{(2\rho M_0+M_1)\eta}{\rho,m}+
                    \norm{A\eta}{\rho,m}\right)\norm{V}{\rho,m}.
      \end{gather}
    \end{lemma}
    \begin{proof}
      Using the Galerkin orthogonality \eqref{eq:Galorth} it follows
      the error equality
      \[
        \scprm{(\partial_t M_0+M_1+A)\xi,V}
          =-\scprm{(\partial_t M_0+M_1+A)\eta,V}.
      \]
      Then we have by integration by parts and the properties of $P_r$ for all $w\in\mathcal{V}^\tau$ and $v\in H_\rho^1([0,T],H)$
      \begin{align*}
        \scprm{\partial_tM_0(v-P_r v),w}
          &= 2\rho\scprm{M_0(v-P_r v),w}-\scprm{v-P_r v,\partial_t M_0w}+\scp{v-P_r v,w}_H\mathrm{e}^{-2\rho t}\big|_{t_{m-1}}^{t_m}\\
          &= 2\rho\scprm{M_0(v-P_r v),w}.
      \end{align*}
      Thus we get the error equation
      \[
        \scprm{(\partial_t M_0+M_1+A)\xi,V}
          =-\scprm{(2\rho M_0+M_1+A)\eta,V}
      \]
      from which \eqref{eq:errineq} follows by a Cauchy-Schwarz inequality.
    \end{proof}
    In the following estimates we will bound the terms of interest by a norm of the interpolation error given by
    \[
      \norm{\eta}{*,[0,t_m]}:=\norm{(2\rho M_0+M_1)\eta}{\rho,[0,t_m]}+
                              \norm{A\eta}{\rho,[0,t_m]}.
    \]
    \begin{lemma}
      It holds for any $m\in\{1,\dots,M\}$
      \begin{align*}
        \gamma\norm{\Pi_{r-1}\xi}{\rho,[0,t_m]}^2+
        \scp{M_0\xi(t_m),\xi(t_m)}_H\mathrm{e}^{-2\rho t_m}
        &\leq\frac{2}{\gamma}\norm{\eta}{*,[0,t_m]}^2
      \end{align*}
    \end{lemma}
    \begin{proof}
      Let $V^\tau=\Pi_{r-1}\xi$ be the test function in \eqref{eq:errineq}.
      From \eqref{eq:lowerbound} and
      \eqref{eq:errineq}
      we have
      \begin{align*}
        \gamma\norm{\Pi_{r-1}\xi}{\rho,m}^2+\frac{1}{2}\scp{M_0\xi(t),\xi(t)}_H\mathrm{e}^{-2\rho t}\big|_{t_{m-1}}^{t_m}
         &\leq
        \scprm{(\partial_t M_0+M_1+A)\xi,\Pi_{r-1}\xi}\\
        &\leq\left(\norm{(2\rho M_0+M_1)\eta}{\rho,m}+
                  \norm{A\eta}{\rho,m}\right)\norm{\Pi_{r-1}\xi}{\rho,m}.
      \end{align*}
      Now Young's-inequality ($ab\leq \frac{1}{2\gamma}a^2+\frac{\gamma}{2}b^2$) leads to
      \[
        \gamma\norm{\Pi_{r-1}\xi}{\rho,m}^2+\scp{M_0\xi(t),\xi(t)}_H\mathrm{e}^{-2\rho t}\big|_{t_{m-1}}^{t_m}
        \leq\frac{1}{\gamma}\left(\norm{(2\rho M_0+M_1)\eta}{\rho,m}+
                                  \norm{A\eta}{\rho,m}\right)^2
      \]
      which gives upon summation the statement because $M_0\xi(0)=0$.
    \end{proof}
    Thus we have control over the weighted $L^2$-projection of the error
    and its final value.
    \begin{corollary}
      In the case of $M_0$ having only a trivial null-space we have immediate control of the full norm
      due to
      \[
        \norm{\xi}{\rho,m}^2\leq C\left(\norm{\Pi_{r-1}\xi}{\rho,m}^2+\tau_m\scp{M_0\xi(t_m),\xi(t_m)}_H\mathrm{e}^{-2\rho t_m}\right)
      \]
      for some $C>0$ implying
      \[
        \norm{\xi}{\rho,[0,T]}^2
          \leq C \left(\frac{2}{\gamma^2}+\frac{2T}{\gamma}\right)\norm{\eta}{*,[0,T]}^2.
      \]
      In the case of $M_0$ having a non-trivial null-space the norm equivalence considered in
      the existence proof of Section~\ref{sec:exist} do only provide a bound exponentially increasing
      in $1/\min\tau_m$.
    \end{corollary}

  \subsection{Full discretisation}
    Let $\tau:=\max\limits_{m\in\{1,\dots,M\}}\tau_m$ be the maximal time-step length.
    Similarly to \cite[Section 4]{FrTW16} we can now proceed and estimate the error of
    the full discretisation. Here the only difference is the time-discretisation method.
    \begin{theorem}\label{thm:cts}
      We assume for the solution $U$ of \eqref{eq:evo} the
      regularity
      \[
        U\in H_\rho^{1}(\mathbb{R};H^k(\Omega)\times H^k(\Omega))\cap
        H_\rho^{r+3}(\mathbb{R};L^2(\Omega)\times L^2(\Omega))
      \]
      as well as
      \[
        AU\in H_\rho(\mathbb{R}; H^k(\Omega)\times H^k(\Omega)).
      \]
      Then we have for the error of the numerical solution $U^\tau_h$ by
      \eqref{eq:evodisc}
      \[
        \norm{U-\Pi_{r-1}U_h^\tau}{\rho,[0,T]}^2+
        \mathrm{e}^{-2\rho T}\scp{M_0(U-U_h^\tau)(T),(U-U_h^\tau)(T)}
        \leq C (\tau^{2(r+1)} + T h^{2k})
      \]
      and if $M_0$ has only a trivial null space
      \[
        \norm{U-U_h^\tau}{\rho,[0,T]}^2
        \leq C (\tau^{2(r+1)} + T h^{2k}).
      \]
    \end{theorem}
    \begin{proof}
      This is a direct consequence of the results in \cite[Section 4]{FrTW16}
      combined with the estimates of the previous section.
    \end{proof}

\section{Numerical examples}\label{sec:numerics}
  We consider two examples with unknown solutions. Simulations with known smooth solutions
  were also made and the theoretical orders were observed. The two following examples
  show a more realistic behaviour in the case of changing type systems.
  All computations were done in the finite-element framework $\mathbb{SOFE}$, see
  \texttt{github.com/SOFE-Developers/SOFE}.
  \subsection{1+1d example}
    Let us consider as first example one spatial dimension and combine a hyperbolic and an elliptic region.
    To be more precise, let $\Omega=\left[-\pi,\pi\right]$, $\Omega_{hyp}= \left[-\pi,0\right]$,
    and $\Omega_{ell}=\left[0,\pi\right]$. As final time we set $T=4\pi$. The problem is now given
    by
    \begin{gather}\label{ex:1d}
      \left[
        \partial_t
        \begin{pmatrix}[c]
        \id{\Omega_{hyp}} & 0\\
        0 & \id{\Omega_{hyp}}
        \end{pmatrix}
        +\begin{pmatrix}[c]
          \id{\Omega_{ell}} & 0\\
          0 & \id{\Omega_{ell}}
        \end{pmatrix}
        +\begin{pmatrix}[c]
          0 & \partial_x\\
          \mathring{\partial_x} & 0
        \end{pmatrix}
      \right]U
        =F
    \end{gather}
    with homogeneous Dirichlet-conditions for the first component of $U:\mathbb{R}\times\mathbb{R}\to\mathbb{R}^2$,
    the initial condition $U_0=0$
    and a right-hand side $F(t,x)=(f(t,x),g(t,x))\cdot\id{\geq 0}(t)$, where $\id{\geq 0}(t)$
    is the characteristic function of the non-negative time line and
    \begin{align*}
      f(t,x) &= \frac{1}{5}\sin(3t)+\min\{t,\pi\}\cos(3x),\\
      g(t,x) &= \sin(t)\left(1-\frac{x^2}{\pi^2}\right).
    \end{align*}
    Thus, $F$ is continuous and it holds $F(t)=0$ for $t\leq 0$.
    Therefore, the solution theory of \cite{Picard} gives the existence of a
    unique solution $U$ that is continuous in time. Figure~\ref{fig:sol1d}
    \begin{figure}
     \begin{center}
        \includegraphics[width=0.35\textwidth]{ex1da}
        \includegraphics[width=0.35\textwidth]{ex1db}

     \end{center}
      \caption{Solution of problem \eqref{ex:1d}, first component (left) and second component (right)\label{fig:sol1d}}
    \end{figure}
    shows plots of the components of the solution in the domain. Note that
    the first component has a kink along $x=0$ -- it is continuous but not
    differentiable in $x$. As mesh we use an equidistant mesh of $N$ cells in $\Omega$
    and $M$ cells in $[0,T]$. In order to calculate the errors we use a reference
    solution $U_{ref}$ instead of the unknown solution $U$. The reference solution is computed
    on an $4096\times2048$ mesh with polynomial degrees $k=4$ and $r=3$.
    Table~\ref{tab:ex1d}
    \begin{table}
      \caption{Errors $\norm{U_{ref}-U^\tau_h}{\rho,[0,T]}$ and rates for example \eqref{ex:1d}\label{tab:ex1d}}
      \begin{center}
        \begin{tabular}{rllll}
          \toprule
          $M=2N$
          &\multicolumn{2}{c}{cGP-method}
          &\multicolumn{2}{c}{dG-method}\\
          \midrule
          \multicolumn{5}{c}{$k=2$, $r=1$}\\
          \midrule
            256 & 8.890e-04 &      & 1.808e-04 &     \\
            512 & 3.136e-04 & 1.50 & 7.751e-05 & 1.22\\
           1024 & 1.380e-04 & 1.18 & 3.496e-05 & 1.15\\
           2048 & 6.739e-05 & 1.03 & 1.580e-05 & 1.15\\
          \midrule
          \multicolumn{5}{c}{$k=3$, $r=2$}\\
          \midrule
            256 & 1.187e-04 &      & 6.058e-05 &     \\
            512 & 5.489e-05 & 1.11 & 2.642e-05 & 1.20\\
           1024 & 2.492e-05 & 1.14 & 1.137e-05 & 1.22\\
           2048 & 1.114e-05 & 1.16 & 4.669e-06 & 1.28\\
           \bottomrule
        \end{tabular}
      \end{center}
    \end{table}
    shows the results for different values of $M$ and $N$ and polynomial degrees $k$ and $r$.
    We coupled $k=r+1$ as the theory gives for smooth $U$ the convergence order $\min\{k,r+1\}$
    if $N$ and $M$ are proportional. We observe for the continuous Galerkin-Petrov method
    in the first column only a convergence rate between 1 and 2. Increasing the polynomial
    degree reduces the error, but does not influence the rate much. A reason for this behaviour
    could be that $U$ is not smooth enough for the error estimates to hold.\\
    For comparison we also computed approximations with the discontinuous Galerkin method
    from \cite{FrTW16}. The errors given in the remaining columns show a similar behaviour
    with convergence rates between 1 and 2. Nevertheless, the errors are smaller
    for the discontinuous approach.

  \subsection{1+2d example}
    As second example we consider the last example of \cite{FrTW16}.
    Let $T=5.2$, $\Omega=(0,1)^2\subset\mathbb{R}^2$,
    $\Omega_{\mathrm{hyp}}=\left( \frac{1}{4},\frac{3}{4}\right)^2$ and
    $\Omega_{\mathrm{ell}}=\Omega\setminus\bar\Omega_{\mathrm{hyp}}$
    The problem is given by
    \begin{gather}\label{ex:2d}
      \left[
      \partial_t
      \begin{pmatrix}
        \id{\Omega_{\mathrm{hyp}}} & 0\\
        0 & \id{\Omega_{\mathrm{hyp}}}
      \end{pmatrix}
      +\begin{pmatrix}
        \id{\Omega_{\mathrm{ell}}} & 0\\
        0 & \id{\Omega_{\mathrm{ell}}}
      \end{pmatrix}
      +\begin{pmatrix}
        0 & \operatorname{div} \\
        \operatorname{grad}^\circ & 0
      \end{pmatrix}
      \right]U
      =\begin{pmatrix}
        f\\
        0
      \end{pmatrix},
    \end{gather}
    where
    \[
      f(t,\mathbf{x})=2\sin(\pi t)\cdot\id{\mathbb{R}_{<1/2}\times\mathbb{R}}(\mathbf{x}).
    \]
    Figure~\ref{fig:sol2d}

    \begin{figure}[tb]
      \begin{center}
        \includegraphics[width=0.25\textwidth]{ex2d1.pdf}\quad
        \includegraphics[width=0.25\textwidth]{ex2d2.pdf}\quad
        \includegraphics[width=0.25\textwidth]{ex2d3.pdf}\\
        \includegraphics[width=0.25\textwidth]{ex2d4.pdf}\quad
        \includegraphics[width=0.25\textwidth]{ex2d5.pdf}\quad
        \includegraphics[width=0.25\textwidth]{ex2d6.pdf}
      \end{center}
      \caption{First component of $U$ at times $t=5k/16$ for $k\in\{1,\dots, 6\}$ (top left
               to bottom right) of problem \eqref{ex:2d}}\label{fig:sol2d}
    \end{figure}

    shows some snapshots of the first component of the solution $U:\mathbb{R}\times\mathbb{R}^2\to\mathbb{R}\times\mathbb{R}^2$,
    approximated by a numerical simulation. Again we use equidistant meshes
    with $N$ cells in each dimension of space and $M$ cells in $[0,T]$.
    As reference solution $U_{ref}$ replacing the unknown exact solution we use
    an approximation calculated with $M=192,\,N=96,\,k=3,\,r=2$ and $M=128,\,N=64,\,k=4,\,r=3$, resp.
    Table~\ref{tab:ex2d}
    \begin{table}
      \caption{Errors $\norm{U_{ref}-U^\tau_h}{\rho,[0,T]}$ and rates for example \eqref{ex:2d}\label{tab:ex2d}}
      \begin{center}
        \begin{tabular}{rllll}
          \toprule
          $M=2N$
          &\multicolumn{2}{c}{cGP-method}
          &\multicolumn{2}{c}{dG-method}\\
          \midrule
          \multicolumn{5}{c}{$k=2$, $r=1$}\\
          \midrule
          16 & 1.961e-02 &      & 7.821e-03 &     \\
          32 & 9.199e-03 & 1.09 & 3.018e-03 & 1.37\\
          64 & 3.751e-03 & 1.29 & 8.813e-04 & 1.78\\
          96 & 1.324e-03 & 1.50 & 2.920e-04 & 1.59\\
          \midrule
          \multicolumn{5}{c}{$k=3$, $r=2$}\\
          \midrule
          16 & 5.499e-03 &      & 2.790e-03 &     \\
          32 & 1.435e-03 & 1.94 & 6.385e-04 & 2.13\\
          64 & 4.430e-04 & 1.70 & 2.248e-04 & 1.51\\
          \bottomrule
        \end{tabular}
      \end{center}
    \end{table}
    shows the results. Similarly to the previous example we do not achieve the optimal
    convergence order for both methods. And again the discontinuous Galerkin method has smaller errors.

\section*{Conclusions}
  The continuous solution of an evolutionary system with continuous right hand side
  can be approximated by several methods. Here we investigated the continuous Galerkin-Petrov
  method, that has optimal convergence order for smooth solutions. We have proved this
  for the $L^2$-projection of the error into the test space. For operators $M_0$ having
  only a trivial null space it also follows for the full error. The benefit of the continuous
  method compared to the discontinuous Galerkin method is the continuity that implies a
  non-dissipative behaviour. In our examples with unknown solutions, that are probably not smooth,
  the discontinuous Galerkin method is slightly better. Furthermore, these examples show that
  an increase of the polynomial degree in space over 2 and in time over 1 gives no huge benefit.
  This is different for smooth solutions -- here both methods achieve the theoretical high convergence orders.

\bibliographystyle{plain}


\section{Introduction}

\subsection{Problem and Motivation}

Efficient retrieval of data from a structured, finite, universe is a fundamental computational question in computer science.
A classical data structure designed to search elements of a linearly ordered set is the {\em binary search tree}, in which every node contains an element $x$ of the set, and its two subtrees are binary search trees for the elements that are respectively larger or smaller than $x$.
Due to their fundamental flavor and practical importance, binary search trees are the subject of a considerable scientific literature spanning nearly eight decades of research, as well as being a basic component of software libraries.

\paragraph{Searching Vertices of a Tree.}
We consider the problem of searching for an element that is not part of a linearly ordered set, but rather a vertex of a tree $G$.
For this purpose, we generalize binary search trees to {\em search trees on trees}.
In such a search tree, the root node contains a vertex $x$ of $G$, and its subtrees are search trees on each of the connected components of the forest $G\setminus x$ (see Figure~\ref{fig:ex_search_tree} for an illustration).
Note that the roots of the subtrees need not be adjacent to $x$ in $G$, hence this search tree forms a rooted tree on the same vertex set as $G$, with a possibly distinct edge set. We will refer to such a tree as a \emph{search tree on the tree} $G$.
This tree can be searched by iteratively performing node queries, starting from the root:
at each node $x$, an oracle tells us that either $x$ is the vertex we look for, or in which of the remaining connected components we need to pursue the search.

Note that in the special case where the underlying tree $G$ is a path, a search tree on $G$ is simply a binary search tree on the vertices of $G$ ordered with respect to their location in the path. Search trees on trees are also special cases of trees on graphs, also known as {\em vertex rankings} and they have been studied in various areas of discrete mathematics and computer science, e.g., polyhedral combinatorics, combinatorial optimization, graph theory (we discuss some of the related work in Section~\ref{sec:related_work}).

\paragraph{Adaptive Binary Search Trees --- BST Model of Computation.}
Binary search trees (BSTs) can be viewed as a model of computation where in each operation there is a pointer that starts at the root and can be moved to adjacent nodes at unit cost; additionally a local change known as a \emph{rotation} can be performed at unit cost. A sequence of search operations $X = x_1,\dotsc,x_m$ to nodes of the BST is requested and the goal is to perform all searches at minimum cost. This model was formalized in \cite{Wilber89,DHIP07} and classic binary search trees such as Red-Black trees \cite{DBLP:conf/focs/GuibasS78} and AVL trees \cite{AVL} fit in this model. In the \emph{offline} version of this model, the sequence $X$ is known in advance and the rotations performed might be based on the knowledge of next requests. On the other hand, in the \emph{online} version, each request $x_i$ is revealed after the previous search $x_{i-1}$ has been performed.

In~\cite{ST85}, Sleator and Tarjan conjectured that there exists a single online BST-model algorithm whose runtime over every sufficiently long sequence of searches is within a constant factor of the optimal \textit{offline} BST-model algorithm on that sequence. This notion of optimality, called \emph{dynamic optimality} is much stronger than other typical types of optimality, including those that are stated in terms of a distribution of operations.

Sleator and Tarjan~\cite{ST85} introduced the \emph{Splay Tree}, a self-adjusting BST-model algorithm that uses a small set of restructuring heuristics to move the searched node item to the root.
They conjectured that the splay tree was dynamically optimal in the BST model, a conjecture that remains open.
While constant-factor competitiveness remains elusive in the BST model, a breakthrough in the theory of binary search trees was achieved by Demaine, Harmon, Iacono, and P\v{a}tra\c{s}cu~\cite{DHIP07}, who introduced the {\em tango trees}, which were proved to be $O(\log \log n)$-competitive. (See \ref{s:abst} for a discussion of the history of binary search trees in the context of our result).

\paragraph{Adaptive Search Trees on Trees.} Interestingly, while numerous questions on the optimal design of search trees on trees have been addressed (see Section~\ref{sec:related_work}), adaptivity by changing the search tree on tree has never been considered.
This can be achieved, just in the same way as in binary search trees, via an elementary {\em rotation} operation.
These rotations generalize rotations on binary search trees, as illustrated in Figure~\ref{fig:rotation}.

In this paper, we introduce a natural generalization of the BST computation model involving unit-cost finger moves and rotations, which we call the \emph{general search tree model (GST)}, and consider the design of {\em competitive online search trees on trees} in this model. It is tempting to consider known adaptive binary search tree techniques and try to generalize them to search trees on trees. On the other hand, search trees on trees are much more subtle and many nice properties of BSTs do not generalize. As a result several ``natural'' attempts to generalize the techniques developed for BSTs, seem to fail, as we discuss in detail in Section~\ref{s:compare}. Thus we need several new ideas and techniques in order to design competitive online adaptive search trees.

\begin{figure}
  \centering
  \begin{subfigure}[t]{0.4\linewidth}
   \begin{tikzpicture}[scale=.8,auto,swap]
    \foreach \pos/\name in {{(1,3)/a}, {(2,2)/b}, {(2,3)/c}, {(4,2)/f}, {(4,6)/j}, {(3,4)/d}, {(4,1)/e}, {(5,2)/h}, {(3,5)/i}, {(4,7)/k}, {(5,6)/l}}
        \node[vertex, label=above left:$\name$] (\name) at \pos {};
    \node[vertex, label=above right:$g$] (g) at (4,3) {};
    \foreach \source/\dest in {a/c,c/b,c/d,d/g,g/f,f/e,f/h,d/i,i/j,j/k,j/l} \path[edge] (\source) -- (\dest);
   \end{tikzpicture}
   \caption{A tree $G$.}
   \label{fig:treeG}
  \end{subfigure}\quad
  \begin{subfigure}[t]{0.4\linewidth}
   \begin{tikzpicture}[scale=.8,auto,swap]
    \foreach \pos/\name in {{(1,5)/a}, {(2,5)/b}, {(2,6)/c}, {(3,5)/f}, {(3,2)/g}, {(5,2)/l}, {(3,3)/d}, {(2,4)/e}, {(3,4)/h}, {(4,4)/i}, {(5,3)/k}, {(5,1)/j}}
        \node[svertex, label=left:$\name$] (\name) at \pos {};
    \foreach \source/\dest in {a/c,b/c,f/c,e/f,h/f,f/i,i/d,i/k,d/g,k/l,j/l} \path[edge] (\source) -- (\dest);
   \end{tikzpicture}
   \caption{A search tree on $G$.}
   \label{fig:searchtree}
  \end{subfigure}
  \caption{Illustration of a search tree on a tree $G$.}
  \label{fig:ex_search_tree}
\end{figure}

\begin{figure}
  \centering
  \begin{subfigure}[t]{0.3\linewidth}
   \begin{tikzpicture}[scale=.8,auto,swap]
    \foreach \pos/\name in {{(1,2)/A}, {(2,1)/B}, {(3,3)/C}, {(4,5)/D}, {(5,4)/E}} \node[vertex, fill=red!20] (\name) at \pos {$\name$};
    \node[vertex, label=above:$p$] (p) at (2,2) {};
    \node[vertex, label=below:$v$] (v) at (4,4) {};
    \foreach \source/\dest in {A/p,B/p,p/C,C/v,v/D,v/E} \path[edge] (\source) -- (\dest);
   \end{tikzpicture}
   \caption{Two vertices $p$ and $v$ in $G$.}
   \label{fig:rot1}
  \end{subfigure}\quad
  \begin{subfigure}[t]{0.4\linewidth}
   \begin{tikzpicture}[scale=.8,auto,swap]
    \begin{scope}[xshift=0cm]
    \foreach \pos/\name in {{(1,2)/A}, {(2,2)/B}, {(3,1)/C}, {(4,1)/D}, {(5,1)/E}} \node[vertex, fill=red!20] (\name) at \pos {$\name$};
    \node[svertex, label=above:$p$] (p) at (2,3) {};
    \node[svertex, label=above:$v$] (v) at (4,2) {};
    \foreach \source/\dest in {p/A,p/B,p/v,v/C,v/D,v/E} \path[edge] (\source) -- (\dest);
  \end{scope}
    \begin{scope}[xshift=6cm]
    \draw[oriented edge] (0,3) -- (1,3);
    \foreach \pos/\name in {{(1,1)/A}, {(2,1)/B}, {(3,1)/C}, {(4,2)/D}, {(5,2)/E}} \node[vertex, fill=red!20] (\name) at \pos {$\name$};
    \node[svertex, label=above:$p$] (p) at (2,2) {};
    \node[svertex, label=above:$v$] (v) at (4,3) {};
    \foreach \source/\dest in {p/A,p/B,p/v,p/C,v/D,v/E} \path[edge] (\source) -- (\dest);
  \end{scope}
\end{tikzpicture}
   \caption{\label{fig:rotation}A rotation on $v$ in the search tree on $G$.}
  \end{subfigure}
  \caption{Rotations.}
\end{figure}

\subsection{Our Results}

In this work we define a model of computation for search trees on trees, the \emph{general search tree model (GST)}. This model generalizes the BST model, which corresponds to the special case where the underlying tree is a path. We obtain both lower and upper bounds for this model, matching the ones known for the BST model.

\paragraph{Lower Bound.} We obtain a lower bound on the cost of any algorithm in the GST model, by generalizing the {\em interleave lower bound} of binary search trees~\cite{Wilber89,DHIP07} to search trees on trees.

\paragraph{Upper Bound.} Our main result is an online algorithm for executing search sequences in search trees on trees that is {\em $O(\log \log n)$-competitive}, that is, whose running time in the GST model is at most a factor $O(\log \log n)$ away from that of any other algorithm, {\em even knowing all search requests in advance}. This matches the best competitive factor known so far for binary search trees.

The basic idea is to connect the cost of the algorithm to the interleave lower bound and show that each time this lower bound increases by 1, the algorithm incurs a cost at most $O(\log \log n)$. This is based on the paradigm developed by Demaine, Harmon, Iacono and P\v{a}tra\c{s}cu for Tango trees~\cite{DHIKP09} to achieve competitive ratio $O(\log \log n)$ for binary search trees. However substantially more involved ideas and techniques are needed to obtain the generalization. First, we develop a notion of {\em Steiner-closed search trees} that seems to be independently useful. Moreover the results on BSTs rely crucially on the fact that a subset of $k$ vertices (defining a \textit{preferred path}, see Section~\ref{sec:ub}) can be stored easily in a BST data structure (like red-black trees) that supports split and merge in $O(\log k)$ time. On the other hand, in search trees there is no straightforward analogue. We need a subtle two-level decomposition involving link-cut trees~\cite{ST83,T83} and show that the resulting data structure is a valid search tree on tree.

\paragraph{Organization.}
In the next subsection, we detail a number of related works. In Section~\ref{s:compare} we provide a comparison between binary search trees and search trees on trees, mentioning the main properties that do not generalize and showing that search trees on trees have a much more rich and subtle structure. In Section~\ref{sec:model}, we give the basic definitions related to search trees and introduce the precise computation model involved.
In Section~\ref{sec:lb}, we show how to generalize the {\em interleave lower bound} of binary search trees to search trees on trees.
The description of our $O(\log \log n)$-competitive algorithm is given in Section~\ref{sec:ub}.

\subsection{Related Work}
\label{sec:related_work}
\subsubsection{Search trees, vertex rankings, and related notions}
The structure we refer to as search trees on trees, and more generally search trees on graphs, has been studied for decades under many different names.
They are known as elimination trees~\cite{P88,A94,BGHK95}, vertex rankings~\cite{S89,D93,BDJKKMT98}, and tubings~\cite{CD06,MP15}, among others.

The minimum height of a search tree on a graph $G$ is known in the graph theory community as the {\em tree-depth} of $G$.
We refer to the text of Ne{\v s}et{\v r}il and Ossona de Mendez~\cite{NO12} for details on the equivalence between the various definitions of tree-depth as well as its connections with other structural parameters of graphs.

Many previous works have been dedicated to constructing minimum-height, and therefore {\em worst-case optimal search trees}~\cite{P88,A94,D93}.
Most relevant to our result, it was shown by Sch{\"a}ffer that a minimum-height search tree on a tree, hence the tree-depth of a tree, can be found in linear time~\cite{S89}.

\subsubsection{Other search tree models}
More recently, different models were proposed for searching for elements in tree and graph-structured universes.
Our definition of search trees is based on {\em vertex queries}: every node of the search tree is associated with a vertex of the searched graph.
In contrast, {\em edge queries} have also been studied~\cite{BFN99,OP06,MOW08,CKLPV16,CJLM11,CJLM14}, in which every node of the search tree is associated with an edge of the graph, and the oracle points to one of the two connected components containing the sought vertex. This is sometimes cast as searching in a partial order. A dynamic variant, supporting insertion and deletion of elements, has been proposed by Heeringa et al.~\cite{HIT11}.
Another model that was recently proposed for searching a graph involves an oracle that given a vertex, returns the first edge incident to this vertex on a shortest path to the sought vertex~\cite{EKS16}.

\subsubsection{Polyhedral combinatorics}
The {\em associahedra} are polytopes whose vertices are in bijection with binary search trees on $n$ elements, and edges correspond to pairs of binary search trees that differ by one single rotation~\cite{T51,S63,L89,CSZ15}. From a classical Catalan bijection, their skeletons are also flip graphs of triangulations of a convex polygon on $n+2$ vertices. {\em Graph associahedra} were studied independently by Carr and Devadoss~\cite{CD06}, and Postnikov~\cite{P09}. Just like in associahedra, the vertices of a graph associahedron defined from a graph $G$ are in bijection with the search trees on $G$, and its skeleton is the {\em rotation graph} of the search trees on $G$, that is, two vertices are connected by an edge of the polytope if and only if the search trees differ by a single rotation. The search trees and the rotations are essentially what is referred to by Carr and Devadoss~\cite{CD06} as {\em tubings} and {\em flips}, respectively. In Postnikov~\cite{P09}, and Postnikov, Reiner, Williams~\cite{P08}, the search trees are called {\em $\mathcal B$-trees}.

Sleator and Tarjan raised the question of the diameter of the associahedron: the largest rotation distance between any two binary search trees on $n$ elements. Together with Thurston, they proved that it was $2n-6$ for sufficiently large values of $n$~\cite{STT86}. A few years ago, Pournin gave a combinatorial proof of this result and established it for every value of $n$~\cite{P14}.
A similar diameter question was studied for graph associahedra by Manneville and Pilaud~\cite{MP15}. They asked the question of the worst-case diameter of {\em tree associahedra}, hence the maximum rotation distance between two search trees on a tree. Cardinal, Langerman, and Perez-Lantero proved that the correct bound was $\Theta (n\log n)$~\cite{CLP18}.
This body of work provides us with the same theoretical background on search trees on graphs and trees as the combinatorics of associahedra does on binary search trees.

\subsubsection{Dynamic optimality of binary search trees} \label{s:abst}
Our work most prominently relies on insights and progress on the so-called {\em dynamic optimality} conjecture for binary search trees which posits the existence of $O(1)$-competitive online binary search trees.
Here we consider the total number of elementary operations, finger moves and rotations, required to search a given sequence of nodes in the tree, and wish this number to lie within a constant factor of that of any other algorithm, even when the latter has access to the sequence of queries in advance.
We refer to Iacono for a survey on this question~\cite{I13}.

It is famously conjectured that splay trees have the dynamic optimality property.
This remains unproven, although a number of weaker runtime bounds, such as the static optimality property~\cite{ST85}  (splay trees are as good as the best static BST), the working set property~\cite{ST85} (searching an item is fast if it has been searched recently), and the dynamic finger property~\cite{CMSS00,C00} (searching an item is fast if it is close in key-space to the previous search), are known to hold.
The crucial {\em Access Lemma} of splay trees and the conditions under which it holds have been extensively analyzed~\cite{S96,GM04,CG0MS15b}.

More recently, the {\em geometric view} on binary search trees was introduced by Demaine, Harmon, Iacono, Kane, and P\v{a}tra\c{s}cu~\cite{DHIKP09}. In this view, optimality of binary search trees is cast as a geometric problem on point sets in the plane. It also introduces the online {\em greedy binary search trees}, an online version of the greedy algorithm introduced independently by Lucas~\cite{L88} and Munro~\cite{Munro00}, conjectured to be dynamically optimal as well.
Recently, greedy has been proven to satisfy the dynamic finger property~\cite{IL16}, a generalization of static optimality and dynamic finger which is related to the idea of \emph{lazy search} introduced in~\cite{DBLP:journals/algorithmica/BoseDIL16}, as well as certain so-called pattern avoiding search sequences \cite{DBLP:conf/focs/ChalermsookG0MS15}.

Although both splay trees and the greedy algorithm are conjectured to be $O(1)$-competitive, the best known upper bound on their competitive ratio is $O(\log n)$. The best competitive ratio known is $O(\log \log n)$, first achieved by Demaine et. al.~\cite{DHIP07} using {\em tango trees}. Tango trees are designed to approximately match the so-called {\em interleave lower bound}, a variant of a lower bound from Wilber~\cite{Wilber89}. Based on this idea several other $O(\log \log n)$-competitive BST algorithms were later developed~\cite{WDS06,G08}, shown to satisfy several additional properties like the working set bound. It is this structure that we are able to generalize to search trees on trees.

\subsection{From Binary to General Search Trees} \label{s:compare}

It is tempting to think that generalizing the results from the binary search tree model to trees on trees is straightforward.
It is not. In this section we give several examples of standard and well-known properties of BSTs that do not carry over to search trees on trees and a brief overview of our approach to circumvent the obstacles in the generalization. In fact, given those major differences, it came as a surprise to us that an algorithmic result matching the best known for BSTs can be achieved.

\paragraph{Optimal Static Trees.} Given a probability distribution of the searches constructing a static BST that minimizes the cost of an expected search is a well-studied and frequency taught problem, occupying a section in the ubiquitous CLRS text \cite{DBLP:books/daglib/0023376}.
A quadratic-time algorithm due to Knuth \cite{DBLP:journals/acta/Knuth71} is a classic application of dynamic programming and a linear-time algorithm proposed in \cite{DBLP:conf/stoc/Fredman75} and fully analyzed in \cite{DBLP:journals/siamcomp/Mehlhorn77} comes within an additive constant of optimal.
However, for trees-on-trees we have no polynomial algorithm or approximation, and attempts to generalize algorithms for trees fail; for example picking as the root the centroid in the distribution and recursing (as in \cite{DBLP:journals/acta/Mehlhorn75}) does not always approximate the optimal tree within a constant factor; dynamic programming also does not have an obvious polynomial-time solution as the number of connected subtrees of a tree is exponential (as opposed to the quadratic number of connected subpaths of a path).

Furthermore, in BST information theory \cite{Shannon1948} applies and it is well-known that the entropy of the distribution is a lower bound on the search cost due. This is not the case for search trees on trees; this is easily seen in, for example a $(n-1)$-star with equal probabilities, by choosing the center of the star as the root every search can be completed in two steps, while entropy gives the higher $\log_2 n$.
Informally, this is because in binary search trees one comparison gives one bit of information, but in the GST model a comparison gives an amount of information that varies with the degree of the node.

\paragraph{Geometric View.} The {\em geometric view} also constitutes a major contribution to the theory of binary search trees~\cite{DHIKP09}. In this setting, searches to nodes of a binary search trees are pictured as points in the plane, with one dimension being key value and the other time, and any execution of a binary search tree algorithm on this query sequence is pictured as a superset of these points, that satisfy the a geometric condition known as arboral setisfaction.
The proof of equivalence between this point set and a binary search tree algorithm relies crucially on the fact that any binary search tree is at rotation distance at most linear from any other~\cite{STT86}.
This is not true for search trees on trees: there exist pairs of search trees on a tree $G$ of $n$ vertices that are at rotation distance $\Omega (n\log n)$~\cite{CLP18}.
It is because of this that extending the geometric view to the trees-on-trees setting fails, even when one dimension is viewed as being tree-shaped.

\paragraph{Splay Trees and Greedy.} One might also ask whether there is a natural generalization of the splay tree algorithm to search trees on trees. Even taking into account the most relaxed conditions for the access lemma to hold~\cite{S96,CG0MS15b}, the question remains unclear due to entropy not being a lower bound.
Additionally, a natural adaption of the reconfiguration heuristic of splay trees to the trees-on-trees setting results in a structure that can be as bad as possible, even on a star graph.
It is also unclear how we can generalize greedy binary search trees --- another candidate for dynamic optimality~\cite{I13} --- to the tree setting as the online variant depends on the transformations inherent in the geometric view.

\paragraph{Our Approach.} It is in this context of the failure of so much of the machinery that has been developed over the past fifty years of BST research to carry over to the GST model that we surprisingly are able to develop a $O(\log \log n)$-competitive algorithm in the GST model.
Our result is inspired by the BST-model Tango trees, but as the reader shall discover we need a number of new observations, such as the notion of Steiner-closed, which are specific to the GST model.
Crucial to obtaining our result is observing that while entropy-based lower bounds fail in the GST model, we are able to adapt one of the lower bounds due to Wilber \cite{Wilber89} to the GST model. This lower bound is then matched by a factor $O(\log \log n)$ to our data structure using a two-level decomposition. We first decompose a balanced search tree into preferred paths which are represented by search trees. By resorting to Sleator and Tarjan's link-cut trees~\cite{ST83} for handling the changes in preferred paths, we end up with a two-level decomposition into paths, which is eventually managed by splay trees.

\section{ Computation model}
\label{sec:model}

We proceed by defining our rotation-based search tree model.

\begin{defn}[Search tree on a tree]
A rooted tree $T$ is a valid \emph{search tree}
on a given unrooted tree $G = (V,E)$ if
the root $r$ of $T$ stores a vertex of $G$ and
the rooted subtrees of $T\setminus r$ are valid search trees on the connected components of $G \setminus r$.
\end{defn}

Note that in the above definition the trees $T$ and $G$ do not have degree restrictions. While $T$ is rooted, there is no order among the children of a node. Observe that in case the tree $G$ is a path, then a search tree $T$ of $G$ is a binary search tree (BST) with respect to the total order implied by the path. Thus, search trees on trees are a natural generalization of binary search trees.
Throughout the rest of the paper we assume a fixed tree $G$ unless otherwise indicated and $n$ denotes the number of vertices in $G$.

\begin{defn}[Rotation]
A rotation on a non-root node $v$ of $T$ is a local change which yields another search tree constructed as follows:
Let $p$ be the parent of $v$ in $T$.
Swap $p$ and $v$ in $T$. All children of $p$ remain children of $p$. For a child $u$ of $v$, let $S_u$ be the set of nodes in its subtree. For at most one child $u$ of $v$, there might be a node of $S_u$ adjacent to $p$ in $G$; then $u$ becomes a child of $p$; all other children of $v$ remain children of $v$.
\end{defn}

We refer to Figures~\ref{fig:rotation} and~\ref{fig:rotations_2} for a visual explanation. The following is a direct observation.

\begin{figure}
  \centering
   \begin{tikzpicture}[scale=.8,auto,swap]
    \begin{scope}[xshift=0cm]
    \foreach \pos/\name in {{(1,5)/a}, {(2,5)/b}, {(2,6)/c}, {(3,5)/f}, {(3,2)/g}, {(5,2)/l}, {(3,3)/d}, {(2,4)/e}, {(3,4)/h}, {(4,4)/i}, {(5,3)/k}, {(5,1)/j}}
        \node[svertex, label=left:$\name$] (\name) at \pos {};
    \foreach \source/\dest in {a/c,b/c,f/c,e/f,h/f,i/d,i/k,d/g,k/l,j/l} \path[edge] (\source) -- (\dest);
    \path[thick edge] (f) -- (i);
  \end{scope}
  \begin{scope}[xshift=6cm]
    \draw[oriented edge] (-1,6) -- (0,6);
    \foreach \pos/\name in {{(1,5)/a}, {(2,6)/c}, {(2,5)/b}, {(3,5)/i}, {(2,4)/f}, {(4,4)/k}, {(1,3)/e}, {(2,3)/h}, {(3,3)/d}, {(4,3)/l}, {(3,2)/g}, {(4,2)/j}} \node[svertex, label=left:$\name$] (\name) at \pos {};
    \foreach \source/\dest in {a/c,c/b,c/i,i/k,e/f,f/i,f/h,k/l,d/g,j/l} \path[edge] (\source) -- (\dest);
    \path[thick edge] (f) -- (d);
  \end{scope}
  \begin{scope}[xshift=11cm]
    \draw[oriented edge] (-1,6) -- (0,6);
    \foreach \pos/\name in {{(1,5)/a}, {(2,6)/c}, {(2,5)/b}, {(3,5)/i}, {(2,3)/f}, {(4,4)/k}, {(1,2)/e}, {(2,2)/h}, {(2,4)/d}, {(4,3)/l}, {(3,2)/g}, {(4,2)/j}} \node[svertex, label=left:$\name$] (\name) at \pos {};
    \foreach \source/\dest in {a/c,c/b,c/i,i/k,i/d,e/f,f/h,f/g,k/l,j/l,d/f} \path[edge] (\source) -- (\dest);
  \end{scope}
  \end{tikzpicture}
  \caption{Rotations in search trees on tree $G$ of Figure~\ref{fig:treeG}. The rotation is performed on the blue edge. Thus, for example, in the left tree $i$ is a child of $f$ and in the middle tree $f$ has become a child of $i$.}
  \label{fig:rotations_2}
\end{figure}

\begin{obs}
If $T$ is a valid search tree on $G$, and $v$ is a nonroot node of $T$, then the tree obtained after a rotation on $v$ is a valid search tree on $G$
\end{obs}

\begin{defn}[GST model of computation]
In the GST model of computation, we are given a tree $G$ and we maintain a tree $T$ which is valid search tree on $G$. At each time, there is a single node pointer at $T$. At unit cost we can perform the following operations:
\begin{enumerate}
\item Move the pointer to a child or the parent of the current node.
\item Rotate the current node $v$.
\end{enumerate}
A \emph{search} operation for $v\in V$ is any sequence of unit-cost operations where the pointer starts at the root $r$ of $T$ and points to $v$ at some point during the execution of the operation.
\end{defn}

Using this definition, it is easy to see that the GST model is a generalization of the binary search tree (BST) model of computation.

\begin{obs}[Relation with BST model]
\label{obs:gst2bst}
If the tree $G$ is a path, any valid search tree $T$ on $G$ is a binary search tree, search tree rotations correspond to BST rotations, and the GST model of computation is equivalent to the BST model of computation as formulated in \cite{DHIP07}.
\end{obs}

A sequence $X=x_1, x_2, \ldots x_m$ is a valid search sequence in a tree $G=(V,E)$ if all $x_i \in V$. The main goal of this work is to examine the complexity of executing a search sequence in the GST model.

\begin{defn}[Optimal]
Let $OPT(G,X)$ be the optimal cost of any  GST-model algorithm to execute the sequence of searches $X$ starting from any initial search tree $T$ on $G$.
\end{defn}

Note that while we formally care about rotations and pointer moves only, we are mostly interested in practical algorithms, for which the overall cost, including additional bookkeeping operations, is kept within a reasonable factor of the GST cost.

The notion of preferred child of a node in a search tree will be crucial for both the lower and the upper bound.

\begin{defn}[Preferred Child]
Let $P$ be a valid search tree on $G$. Let $y$ be a non-leaf node of $P$, with children $y_1,\dotsc,y_d$. At each time $t \in [1,m]$, we define the \textit{preferred child} of $y$ to be the child $y_i$ whose subtree $P(y_i)$ contains the most recent searched vertex in $x_1, \ldots x_t$ that is in a node of $P(y)$ (or is undefined if none of these searches are in $P(y)$). In case last request in $P(y)$ is to $y$, we set preferred child of $y$ to be $y_1$.
\end{defn}

Note that the preferred child of a node changes throughout the execution of sequence $X$. Understanding and characterizing those changes is an essential part of both the lower bound and the construction of our data structure.

\section{Lower bound}
\label{sec:lb}

In this section we give a lower bound on the optimal cost of executing a sequence of searches in vertices of a tree $G$ in the search tree model (GST), by generalizing the interleave lower bound of~\cite{DHIP07} for binary search trees.

In the following definitions assume a fixed tree $G = (V,E)$ on $n$ vertices and let $X=x_1,x_2, \ldots x_m$ be a request sequence of searches drawn from $V$. We begin by defining the interleave bound.

\begin{defn}[Interleave Bound]
Let $P$ be a valid search tree on $G$. The interleave bound of a node $y$ of $P$ is the number of times the preferred child of $y$ changes over time $1, 2, \ldots m$.  The interleave bound $I(G,P,X)$ is the sum of the interleave bounds of the nodes.
\end{defn}

Note that in the definition above, $P$ is a \textit{fixed} search tree and does not change throughout the execution of $X$. We show that the interleave bound value of \emph{any} fixed tree $P$ can be used to obtain a lower bound on $\OPT(G,X)$, the optimal cost to execute $X$ in the GST model.

\begin{theorem}[Interleave Lower Bound in the GST model]
\label{thm:lower_bound}
Let $P$ be a valid search tree on $G $. For any search sequence $X$ in the GST model of computation, we have that $OPT(G,X) \geq I(G, P,X)/2-n$.
\end{theorem}

\begin{proof}
 Let $\ALG$ be any GST-model algorithm. At a high-level, the proof consists of two main steps:
\begin{enumerate}[(i)]
\item We show that if for a fixed node $y$ in $P$ the interleave bound value is $q$, then there are at least $q/2-1$ unit-cost operations performed by $\ALG$. We charge those operations to node $y$.
 \item We show that for two different nodes $y \neq z$ of $P$, the unit-cost operations charged to $y$ and $z$ are disjoint.
\end{enumerate}

It is easy to see that those two steps imply the theorem; by summing overall nodes $y$ of $P$, we get that $\ALG$ has cost at least $I(G, P,X)/2 - n $.

\vspace{0.2cm}

\paragraph{Notation and Definitions} Before proving parts (i) and (ii) we introduce some definitions and notation. Let $T_t$ be the tree maintained by $\ALG$ after the $t$th search for $t=1,\dotsc,m$.

In all following definitions, we fix $y$ to be a node of $P$ of degree $d$ with children $y_1,\dotsc,y_d$ (ordered arbitrarily but consistently throughout the whole execution). Let $P(y)$ denote the subtree of $P$ rooted at $y$. For $i=1,\dotsc,d$, let $\ell_i$ be the node of subtree $P(y_i)$ with the smallest depth in tree $T_t$ (assuming that $y \in P(y_1)$), for any  $1\leq t \leq m$.

\begin{defn}[Dominating node and dominating subtree]
Let $\ell_{i_t}$ be the node with smallest depth in $T_t$ among $\ell_1,\dotsc,\ell_{d}$, for some $1 \leq i_t \leq d$. Then, $\ell_{i_t}$ is the lowest common ancestor in $T_t$ of all nodes stored in $P(y)$. We call $\ell_{i_t}$ the \emph{dominating node of $P(y)$ in $T_t$} and $P(y_{i_t})$ the \emph{dominating subtree} of $P(y)$.
\end{defn}
Note that as the tree $T_t$ evolves over time, the dominating subtree of $y$ might change. We couple this definition with the definition of transition points.

\begin{defn}[Transition point]
Let $\ell_{i_t}$ be the dominating node of $P(y)$ in $T_t$. For each $i \neq i_t$, we call $\ell_i$ to be the \emph{transition point} of $y$ for $P(y_i)$ at time $t$.
\end{defn}

Note that at each given time $t$ we have exactly $d-1$ transition points of $y$, one corresponding to each $P(y_i)$, for $i \neq i_t$. In the proof of step (i), we will charge $y$ only for touches of $\ALG$ to its transition points.

\paragraph{Properties of transition points.} We now state some basic observations following from the definition of transition points which will be crucial in our proof.

\begin{obs}
\label{obs:transition_opt_1}
A transition point of a node $y \in P$ can not be the root of $T_t$, since $\ell_{i_t}$ is its ancestor. Thus whenever $\ALG$ has to touch a transition point of $y$, it incurs a cost of at least 1.
\end{obs}

\begin{obs}
\label{obs:trans_touch}
Let $\ell_{i_t}$ be the dominating node of $P(y)$ in $T_t$. If the request $x_{t+1}$ is to a node of subtree $P(y_i)$ for some $i \neq i_t$, then the transition point $\ell_{i}$ has to be touched by $\ALG$.
\end{obs}

\paragraph{Proof of Step (i).} Assume that the interleave bound for $y$ equals $q$. Consider the subsequence of requests $x_{j_1},\dotsc,x_{j_q}$ where the preferred child of $y$ changes. Clearly, any two consecutive requests $x_{j_k},x_{j_{k+1}}$ are from different subtrees $P(y_k),P(y_{k+1})$.

\vspace{0.05cm}

 \textit{Requests in non-dominating subtrees:} Each time a node from a non-dominating subtree $P(y_i)$ is requested, the transition node $\ell_i$ has to be touched (by Observation~\ref{obs:trans_touch}). Thus at least one unit-cost operation has to be performed (by Observation~\ref{obs:transition_opt_1}). We charge this operation to $y$.

 \vspace{0.05cm}

 \textit{Requests in dominating subtrees:} Let $x_{j_k},x_{j_{k+1}}$ be two consecutive requests such that in both requests a node from the dominating subtree is requested. Since the subtrees $P(y_k)$ and $P(y_{k+1})$ are different, that means the dominating subtree changed at least once during $(j_k,j_{k+1})$; $P(y_{k+1})$ was not a dominating subtree at time $j_k$, but it is at time $j_{k+1}$, thus at some time point during  $(j_k,j_{k+1})$ there should have been a rotation between the lowest common ancestor of points of $P(y_{k+1})$ (which was a transition point of $y$) and the dominating point of $P(y)$. We get that the transition point of $y$ for $P(y_{k+1})$ is touched at least once during $(j_k,j_{k+1})$ and we charge one to this touch.

\vspace{0.05cm}

\textit{Counting the cost:} Let $q_1$ (resp. $q_2$) be the number of requests to non-dominating (resp. dominating) subtrees of $P(y)$. Note that $q_1 + q_2 = q$. To get an overall bound on the number of unit-cost operations charged to $y$, we perform a simple case analysis on values of $q_1,q_2$.

In case $q_2 \leq \lceil q/2 \rceil$, we count only the unit-cost operations charged for requests on non-dominating subtrees. There are $q_1$ of them. We have that $q_1 = q - q_2  \geq  q/2-1  $.

On the other hand, in case $q_2 > \lceil q/2 \rceil $, we count all requests charged. There are $q_1$ requests to non-dominating subtrees. Among the requests to dominating subtrees, the ones that are preceded by a request to a non-dominating subtree (there are $q_1$ of them) are not charged. All the others (there are $q_2 - q_1$ of them) are charged. We get that the total charge to $y$ is at least $q_1 + (q_2 - q_1) = q_2 \geq q/2 -1$.

Overall we charged at least $q/2 - 1 $ requests.

\paragraph{Proof of Step (ii).} We prove the following lemma.
\begin{lemma}
At any given time $t$, each node $v$ of $T_t$ can be a transition node of at most one node $y$ of $P$.
\end{lemma}

\begin{proof}
Take two nodes $y$ and $z$ of $P$. If trees $P(y)$ and $P(z)$ are disjoint, then clearly all transition points of $y$ and $z$ are different. Otherwise, if $P(y)$ and $P(z)$ intersect, one of $y,z$ is an ancestor of the other in $P$. Assume without loss of generality that $y$ is an ancestor of $z$. If the dominating subtree for $y$ is the subtree including $P(z)$, then all transition points of $y$ are not in $P(z)$. Otherwise, there is a transition point $\ell$ for $y$ in the subtree of $P(y)$ which includes $P(z)$. Observe that $\ell$ is the lowest common ancestor of all points of $P(z)$ it $T_t$, so it can not be a transition point for $z$.  \qedhere
\end{proof}

\vspace{0.1cm}

\noindent Since preferred child changes for nodes $y$ of $P$ are charged to touches of transition points for $y$, this implies that by summing overall nodes, no unit cost operation is counted twice. We conclude that the cost of $\ALG$ is at least $I(G,P,X)/2 - n. \qedhere$

\end{proof}

\section{Tango Trees on Trees}
\label{sec:ub}

In this section, we develop a dynamic search tree data structure that achieves a competitive ratio of $O(\log \log n)$, for search sequences of length $\Omega(n)$. To achieve this, we connect the cost of our algorithm to the \textit{interleave lower bound} for search trees presented in Section~\ref{sec:lb}.

 \paragraph{{\normalfont{\textbf{Preferred paths.}}}} A crucial ingredient in building our data structure is the notion of a \textit{preferred path}. Let $P$ be a fixed valid search tree of a tree $G$. We define a \textit{preferred path} in $P$ as follows: Start from a node that is not the preferred child of its parent (or start from the root) and perform a walk by following the preferred child of the current node, until reaching a leaf. If the preferred child is undefined, pick one arbitrarily.

 Note that each change of preferred child during a search sequence results to changes in the preferred paths of $P$. Let $y$ be a node in a preferred path $\Pi$. If $y$ changes preferred child from $y_j$ to $y_{j'}$, then $\Pi$ splits into two paths $\Pi_1$ and $\Pi_2$ where $\Pi_1$ is from the root to $y$ and $\Pi_2$ is rooted at $y_j$ and ends at a leaf. Then, $\Pi_1$ is merged with the preferred path previously rooted at $y_{j'}$

\begin{obs}
\label{obs:preferred_path_changes}
During a search sequence $X$, there are at most $I(G,P,X) +n$ preferred path changes.
\end{obs}
The additive $n$ stems from the fact that when the preferred child of a node $v$ is undefined, we pick one of them arbitrarily in order to form a preferred path. Thus when the preferred child of $v$ is defined for first time, a preferred path change might occur. Over all nodes there are at most $n$ such preferred path changes.

\paragraph{{\normalfont{\textbf{High-level overview.}}}}
We fix a search tree $P$ of $G$ which we will call \textit{reference tree}, with the property that the height of $P$ is $O(\log n)$.
Note that the reference search tree is used only for the analysis, we do not need to actually store it.

At a high-level,  we show that for each preferred path of $P$ ``touched'', we can perform search and all update operations (cutting and merging preferred paths) with an overhead factor $O(\log \log n)$. This implies that we have a dynamic search tree execution with cost $O(\log \log n \cdot (I(G,P,X) +n) ) $, due to Observation~\ref{obs:preferred_path_changes}. This combined with Theorem~\ref{thm:lower_bound} implies that the cost of our dynamic search tree data structure is $O(\log \log n) \cdot \OPT(G,X)$ for sufficiently long sequences.

In traditional tango trees, the preferred paths are represented by binary search trees, such as red-black trees~\cite{DHIP07}, or splay trees~\cite{WDS06}. This is possible because the sets of nodes on a preferred path are totally ordered. In contrast, in our case, the sets of nodes on a preferred path no longer are totally ordered. We enforce a property on the nodes of a preferred path that we call the {\em Steiner-closed} property. Surprisingly, this property ensures that the nodes of a preferred path correspond to trees that are obtained as minors of $G$. Thus, to perform the cutting and merging of preferred paths, we need a data structure that allows us to manipulate arbitrary trees. It turns out that Sleator and Tarjan's link-cut trees are precisely what we need~\cite{ST83,T83}.

\paragraph{Roadmap.} The rest of this section is organized as follows.
In subsection~\ref{subsec:steiner}, we introduce the notion of Steiner-closed sets and Steiner-closed trees.
 In subsection~\ref{sec:reftree} we show that there exists a Steiner-closed reference tree $P$ of depth $O(\log n)$, and that the nodes contained in a preferred path form a tree obtained as a minor of $G$.
 In subsection~\ref{subsec:aux}, we show that the changes of preferred paths can be implemented using link-cut trees.
 Finally, in subsection~\ref{subsec:alg} we summarize our overall structure and prove that our data structure is $O(\log \log n)$-competitive.

\subsection{Steiner closed sets and trees}
\label{subsec:steiner}

In the following, for two vertices $a$ and $b$ in $G$, let $P(a, b)$ be the the set of vertices on the path from $a$ to $b$.
We first define the notion of convex hull on a set of vertices of a tree.

\begin{defn}[Convex Hull]
Given a tree $G=(V,E)$, for a set $S \subseteq V$ of vertices, we
define the convex hull $\CH(S)$ be the subgraph of $G$ induced by the
vertices on all paths $P(a, b)$, for all pairs of points $a, b$ in $S$.
\end{defn}

We now introduce the notion of {\em Steiner-closed} which is critical for our result.

\begin{defn}[Steiner-closed set]
\label{def:steiner-set}
A set $S$ is a {\em Steiner-closed} set of vertices of a tree $G$
provided that every vertex in $\CH(S)\setminus S$ has degree exactly two in $\CH(S)$.
\end{defn}

\begin{defn}[Steiner-closed tree]
\label{def:steiner-closed-tree}
A search tree $T$ of a tree $G$ is a {\em Steiner-closed} tree
provided that the set of nodes on the path in $T$ from the root to an
arbitrary node in $T$ is a Steiner-closed set with respect to $G$.
\end{defn}

The following is one of the key properties of Steiner-closed trees that lets us manipulate them efficiently. Essentially,
we show that there are not many structural changes that occur in $G$ when splitting and merging paths from the root in
a Steiner-closed search tree $T$ of $G$.

\begin{lemma} \label{lem:jit}
Let $\Pi=p_0, \ldots, p_j$ be a path from the root $p_0$ to a node $p_j$ in a Steiner-closed search tree $T$ of tree $G$. For any $i\in\{1,\ldots, j\}$, let $\Pi'=p_i,\ldots,p_j$. Removing $\CH(\Pi')$ from $\CH(\Pi)$ results in at most 2 connected components.
\end{lemma}
\begin{proof}
Let $\Pi'' = p_0,\ldots, p_{i-1}$. Since $T$ is Steiner-closed, we note that by definition, $\CH(\Pi'')$ is a Steiner-closed set with respect to $G$. For sake of a contradiction, suppose that removing $\CH(\Pi')$ from $\CH(\Pi)$ in $G$ results in at least 3 connected components. Let $C_1, C_2$ and $C_3$ be 3 of these components. Since $\CH(\Pi')$ is a subtree of $\CH(\Pi)$ let $c_ic_i'$ with $i\in\{1,2,3\}$ be the cut edges that connect $C_i$ to $\CH(\Pi')$ with $c_i\in C_i$ and $c_i'\in \CH(\Pi')$. Let $P(c_1,c_2)$ be the path in $\CH(\Pi)$ from $c_1$ to $c_2$ and $P(c_1,c_3)$ the path from $c_1$ to $c_3$. Let $v$ be the first vertex where $P(c_1,c_2)$ and $P(c_1,c_3)$ diverge. Note that $v \not \in \Pi''$. However, $v\in \CH(\Pi'')$ since $c_1, c_2$ and $c_3$ are in $\Pi''$. Moreover, $v$ has degree at least 3 in $\CH(\Pi'')$ which contradicts the fact that $\Pi''$ is a Steiner-closed set in $G$.
\end{proof}

\begin{figure}
\centering
\begin{subfigure}[c]{0.4\textwidth}
  \begin{tikzpicture}[scale=1,auto,swap]
    \foreach \pos/\name in {{(1,3)/a}, {(2,2)/b}, {(4,1)/e}, {(5,2)/h}, {(3,5)/i}, {(4,3)/g}, {(3,4)/d}, {(4,7)/k}, {(5,6)/l}}
        \node[vertex] (\name) at \pos {};
    \foreach \pos/\name/\lab in {{(2,3)/c/a}, {(4,2)/f/b}, {(4,6)/j/c}} \node[svertex,label=above left:$\lab$] (\name) at \pos {};
    \foreach \source/\dest in {a/c,c/b,c/d,d/g,g/f,f/e,f/h,d/i,i/j,j/k,j/l} \path[edge] (\source) -- (\dest);
    \path[dashed oriented edge] (c) to (f) to [out=50,in=-30] (j);
\end{tikzpicture}
\caption{A prefix of a path in a search tree on $G$ that is not Steiner-closed.}
\label{fig:path}
\end{subfigure}
\begin{subfigure}[c]{0.4\textwidth}
  \begin{tikzpicture}[scale=1,auto,swap]
    \foreach \pos/\name in {{(1,3)/a}, {(2,2)/b}, {(4,1)/e}, {(5,2)/h}, {(3,5)/i}, {(4,3)/g}, {(4,7)/k}, {(5,6)/l}} \node[vertex] (\name) at \pos {};
    \node[steiner,label=left:$s$] (d) at (3,4) {};
    \foreach \pos/\name/\lab in {{(2,3)/c/a}, {(4,2)/f/b}, {(4,6)/j/c}} \node[svertex,label=above left:$\lab$] (\name) at \pos {};
    \foreach \source/\dest in {a/c,c/b,c/d,d/g,g/f,f/e,f/h,d/i,i/j,j/k,j/l} \path[edge] (\source) -- (\dest);
    \path[dashed oriented edge] (c) -- (f) to [out=50,in=-5] (d) to [out=50,in=-60] (j);
\end{tikzpicture}
\caption{A Steiner-closed path.}
\label{fig:steinerpath}
\end{subfigure}
\caption{Steiner-closed paths.}
\end{figure}

\begin{figure}
  \centering
  \begin{subfigure}[c]{0.4\linewidth}
   \begin{tikzpicture}[scale=1,auto,swap]
    \foreach \pos/\name in {{(1,3)/a}, {(2,2)/b}, {(2,3)/c}, {(4,2)/f}, {(4,6)/j}, {(3,4)/d}, {(4,1)/e}, {(5,2)/h}, {(3,5)/i}, {(4,7)/k}, {(5,6)/l}}
        \node[vertex, label=above left:$\name$] (\name) at \pos {};
    \node[vertex, label=above right:$g$] (g) at (4,3) {};
    \foreach \source/\dest in {a/c,c/b,c/d,d/g,g/f,f/e,f/h,d/i,i/j,j/k,j/l} \path[edge] (\source) -- (\dest);
   \end{tikzpicture}
   \caption{A tree $G$.}
   \label{fig:treeG3}
  \end{subfigure}\quad
  \begin{subfigure}[c]{0.4\linewidth}
   \begin{tikzpicture}[scale=1,auto,swap]
    \foreach \pos/\name in {{(1,5)/a}, {(2,5)/b}, {(2,6)/c}, {(3,5)/f}, {(3,3)/g}, {(2,4)/e}, {(3,4)/h}, {(5,3)/i}, {(5,0)/l}, {(5,2)/k}}
        \node[svertex, label=left:$\name$] (\name) at \pos {};
    \foreach \pos/\name in {{(4,4)/d}, {(5,1)/j}} \node[steiner, label=left:$\name$] (\name) at \pos {};
    \foreach \source/\dest in {a/c,b/c,f/c,e/f,h/f,d/f,g/d,d/i,i/k,k/j,l/j} \path[edge] (\source) -- (\dest);
   \end{tikzpicture}
   \caption{A Steiner-closed search tree.}
   \label{fig:steinertree}
  \end{subfigure}
  \caption{Steiner-closed search tree obtained from the search tree in Figure~\ref{fig:searchtree}.}
\end{figure}

\vomit{
Note that for a set $\lbrace a,b \rbrace$ we have that $\CH(\lbrace a,b \rbrace) = P(a,b)$. Next, we define the notion of a Steiner vertex.

\begin{defn}[Steiner vertex]
\label{def:steiner}
For three vertices $a, b$ and  $c$ in G, let $\St(a, b, c)$ be $P(a, b)\cap P(b,c)\cap P(a, c)$.
More generally, for a set $S$ of vertices in $G$ such that $|S| \geq 2$, and vertex $a$ in $G$, define $P(a, S) = \cap_{b\in S} P(a, b)$ and $\St(a, S)$ to be $P(a, S)\cap \CH(S)$.
\end{defn}

Note that $\St(a,S)$ is always a unique vertex, the one where the path $P(a,S)$ meets the convex hull of $S$.
The definitions are illustrated on Figure~\ref{fig:steiner}.

\begin{lemma}
\label{lem:steiner_ch}
$\St(v,S) = v$ iff $v \in \CH(S)$.
\end{lemma}
\begin{proof}
($\Rightarrow$) If $v \notin \CH(S)$, then clearly $\St(v,S) \neq a$, since by definition $\St(v,S) \in \CH(S)$. Thus $\St(v,S) = v \Rightarrow v \in \CH(S)$.
($\Leftarrow$) If $v \in \CH(S)$ we have that $P(v,S) = v$. Since
\end{proof}

We now define the notion of a Steiner-closed\ set.

\begin{defn}[Steiner-closed]
\label{def:steiner-closed}
Define a set $S$ of vertices with $|S| \geq 3$ to be \emph{Steiner-closed} for $G$ if for all
$a,b,c$ in $S$, $\St(a,b,c)\in S$. A search tree $T$ is said to be
Steiner-closed if the set of vertices on every path from the root of $T$
to any node $v$ is Steiner-closed.
\end{defn}

These definitions are illustrated on Figures~\ref{fig:steinerpath} and \ref{fig:steinertree}.

\begin{obs}
\label{steiner_add_ch}
Let $S$ be a Steiner-closed\ set of vertices of a tree $G$. Then, for any vertex $u \in \CH(S)$, we have that $S \cup \lbrace u \rbrace$ is also Steiner-closed.
\end{obs}

This comes from the fact that due to Lemma~\ref{lem:steiner_ch} $\St(u,S) = u \in S \cup \lbrace u \rbrace$.

\begin{obs}
\label{obs:non-closed-vertex}
Let $S$ be a Steiner-closed\ set of vertices of a tree $G$ and $v$ be a vertex of $G$ such that $S \cup \lbrace v \rbrace $ is not Steiner-closed. Then $\St(v,S) \in \CH(S) \setminus S$
\end{obs}

This comes since by definition of Steiner vertices we have that $\St(v,S) \in \CH(S)$ and the fact that if $\St(v,S) \in S$, then $S \cup \lbrace v \rbrace$ is Steiner-closed.

\begin{lemma}
\label{lem:steiner_add_node}
Let $S$ be a Steiner-closed\ set of nodes of a tree $G$ and $v$ be a node of $G$ such that $S \cup \lbrace v \rbrace $ is not Steiner-closed. Let $s = \St(v,S) $. The set $ S \cup \lbrace s \rbrace \cup \lbrace v \rbrace  $ is Steiner-closed.
\end{lemma}

\begin{proof}
Due to Observation~\ref{obs:non-closed-vertex} we have that $s \in \CH(S) \setminus S$. Due to Observation~\ref{steiner_add_ch}, we get that the set $S \cup \lbrace s \rbrace$ is Steiner-closed . By definition of $s$, we get that for any $a,b$ in $S$ such that $\St(a,b,v) \notin S$, we have that $\St(a,b,v) = s $. Moreover, for each $a \in S$, we have that $\St(a,s,v) = s$. Since $s \in (S \cup \lbrace s \rbrace \cup \lbrace v \rbrace) $, we get that $S \cup \lbrace s \rbrace \cup \lbrace v \rbrace$ is Steiner-closed.
\end{proof}

\paragraph{{\normalfont{\textbf{Adjacent vertices.}}}}
Next, we define the notion of adjacent vertices with respect to a set $S$.  For two nodes $a$ and $b$ of tree $G$, let $\bar{P}(a,b)$ be the set of nodes $v \neq \lbrace a,b \rbrace$ of the path from $a$ to $b$.

\begin{defn}[Adjacent vertices of a set $S$]
\label{def:adj}
Let $S \subset V$ be a set of vertices of a tree $G$. For any vertex $a \in V \setminus S$ we define the set of \textit{adjacent vertices} with respect to $S$, denoted by $\adj(a,S)$ to be all vertices $b \in S$ such that there is no node $c \in S$ in the path $\bar{P}(a,b)$.
\end{defn}

\begin{lemma}
\label{lem:steiner_adj}
Let $S$ be Steiner-closed\ set of nodes of a tree $G$ and $v$ be a node of $G$ such that $S \cup \lbrace v \rbrace $ is not Steiner-closed. Let $s = \St(v,S) $. We have that $\adj(v,S) = \adj(s,S)$.
\end{lemma}

\begin{proof}
By Observation~\ref{obs:non-closed-vertex}, $s \in \CH(S) \setminus S $, thus $\adj(s,S)$ is well-defined. Moreover, by definition $s \in \cap_{b \in S} P(v,b)$. That means, there is no vertex $c \in S$ in the path $\bar{P}(v,s)$. This implies that $s$ and $v$ have the same set of adjacent vertices with respect to $S$.
\end{proof}

\begin{obs}
\label{obs:connected_adj}
Let $S \subset V$ be a set of vertices of $G$. Consider the induced subgraph $G[V\setminus S]$ obtained by removing all vertices of $S$ and their incident edges. A set of vertices $V' \subset V \setminus S $ such that $\adj(v,S) = S'$ for some $S' \subset S$ forms a connected component of $G[V\setminus S]$.
\end{obs}

The following lemma is the main property we need to be able to implement the auxiliary tree data structure.

\begin{lemma}
\label{lem:steiner_adj_atmost2}
For a Steiner-closed\ set $S$, each node in $V \setminus S$ has at most two adjacent nodes in $S$.
\end{lemma}

\begin{proof}
First mention that for all nodes $v$ such that $v \notin \CH(S)$ and $\St(v,S) \in S$, we have that $|\adj(v,S)| = 1$ and in particular $\adj(v,S) = \St(v,S)$. This is easy to see.

It remains to prove it for nodes $v \in \CH(S) \setminus S $ and for nodes $v \notin \CH(S)$ such that $\St(v,S) \in \CH(S) \setminus S$.

Let us first consider the case  $v \in \CH(S) \setminus S $. Assume $|\adj(v,S)| \geq 3$. Take three vertices $(a,b,c) \in \adj(v,S)$. Let $P(v,\lbrace a,b,c \rbrace) = P(v,a) \cup P(v,b) \cup P(v,c)$. We have that:
\begin{enumerate}[(i)]
\item For $s = \St(a,b,c)$ by definition $s \in \CH(\lbrace a,b,c \rbrace)$ and $s \in S$ since $S$ is Steiner-closed. Thus $s \in \CH(\lbrace a,b,c \rbrace) \cap S $.
\item $\CH(\lbrace a,b,c \rbrace) \subseteq P(v,\lbrace a,b,c \rbrace)$. Thus $s \in P(v,\lbrace a,b,c \rbrace) \cap S $.
\item Since all $a,b,c$ are adjacent to $v$, no vertex in $P(v,\lbrace a,b,c \rbrace) \setminus \lbrace a,b,c \rbrace$ is in $S$. In other words, $ P(v,\lbrace a,b,c \rbrace) \cap S = \lbrace a,b,c \rbrace  $.
\end{enumerate}

The above together imply that $\St(a,b,c) \in \lbrace a,b,c \rbrace$. Without loss of generality, let $\St(a,b,c) = b$. That means $b$ is in the path between $a$ and $c$. This contradicts the fact that all $a,b,c$ are adjacent to $v$; assume $v$ is adjacent to $a$ and $b$, this implies $b$ is in the path between $v$ and $c$, hence that $c$ is not adjacent to $a$, a contradiction.

It remains to consider the case $v \notin \CH(S)$ such that $\St(v,S) \in \CH(S) \setminus S$. Let $s = \St(v,S)$. Clearly $s \in CH(S)$, thus the discussion above implies that $ |\adj(s,S)| \leq 2 $. Due to Lemma~\ref{lem:steiner_adj} we get that $\adj(v,S) = \adj(s,S)$, hence $|\adj(v,S)| \leq 2$.
\end{proof}
}
\paragraph{A static Steiner-closed\ tree.}
Our next lemma shows that given any arbitrary search tree $T$ on a tree $G$, we can transform it to a Steiner-closed\ tree $T'$ of height at most twice the height of $T$.

\begin{lemma}
\label{lem:steiner_ref}
Given a valid search tree $T$ on a tree $G$, we can create another valid search tree $T'$ of $G$, such that $T'$ is Steiner-closed\ and $\height(T') \leq 2 \height(T)$ .
\end{lemma}

\begin{proof}
We show how to transform an arbitrary valid search tree $T$ of a tree $G$ into a Steiner-closed\ search tree $T'$ where the depth of any node in $T'$ is at most
twice its depth in $T$. We perform a depth-first search on $T$ and build our Steiner-closed\ tree incrementally. Let $r$ be the root of $T$. For any non-root node $v$ with parent $p(v)$, let $S_v$ be the set of elements in the path from the root $r$ to $v$. At each step $i$ we transform the tree $T_i$ into the tree $T_{i+1}$ such that $T_0 = T$ and $T_{final} = T' $.

We describe one step of our transformation. Suppose the current tree is $T_i$ and our DFS visits a node $v \in T$ such that: (i) the set $S_{p(v)}$ is Steiner-closed in $G$ and (ii) the set $S_v$ is not Steiner-closed. This means that $\CH(S_v)$ contains a unique vertex $s\in \CH(S_v)\setminus S$ with degree at least 3. Observe that the vertices on the path between $p(v)$ and $v$ in $G$ are contained in the subtree rooted at $v$ in $T_i$. Since $s$ is on this path, it is in the subtree rooted at $v$ in $T_i$. We obtain $T_{i+1}$ by rotating $s$ up the tree until it is between $p(v)$ and $v$, that is, we make it a parent of $v$ and a child of $p(v)$. Note that in $T_{i+1}$ the path from $v$ up to root is now Steiner-closed\  by construction. We then continue our DFS traversal from node $s$.

Let $v_s$ be the child of $v$ in $T_i$ such that $s$ is in the subtree rooted at $v_s$. Let also $v_1,\dotsc,v_d$ be the other children of $v$. Since we perform single rotations to move $s$ up until it becomes a parent of $v$, it is easy to see that by switching from $T_i$ to $T_{i+1}$, the depth of all nodes in subtrees rooted at $v_1,\dotsc,v_d$ increases by 1 and the depth of all other nodes of $T_i$ does not increase. Thus, for a node $w$ in a subtree rooted at $v_j$, $1 \leq j \leq d$, we have that the depth of $w$ increases by 1, the new root-to-$w$ path is the same as before augmented by node $s$ and the path from root to $v$ is Steiner-closed. This implies that all possible depth increases of $w$ will be caused by nodes in the path between $v$ and $w$. Summing overall changes, we get that for any node of the tree at depth $d$ in $T_{0}$, its depth can increase by 1 at most $d$ times, i.e., its depth at $T'$ is at most $2d$.

At the end of this process, $T'$ is Steiner-closed\ by construction. Since the depth of every node at most doubles, the height of $T'$ is at most twice the height of $T$.
\end{proof}

\subsection{Building the Reference tree}
\label{sec:reftree}

To build our reference tree we use as a building block the centroid decomposition $C$ of $G$.

\begin{lemma}
\label{lem:centroid}
Given a tree $G$, there is a search tree $C$ of $G$ with height at most $\log_2 n +1$.
The tree $C$ is a centroid decomposition tree obtained by recursive application of Jordan's theorem~\cite{j1869,harary6graph}:
Given a tree $G$ with $n$ vertices, there exists a vertex whose removal partitions the tree into components, each with at most $n/2$ vertices.
\end{lemma}

The centroid decomposition of a tree $G$ can be seen as the generalization of balanced binary search trees with height $O(\log n)$. Figure~\ref{fig:centroid_decomposition} shows an example. A centroid decomposition can be computed in time $O(n \log n)$, since we need $O(n)$ to find the centroid of a tree on $n$ vertices.
Using Lemma~\ref{lem:centroid} and Lemma~\ref{lem:steiner_ref} we get the following corollary.

\begin{figure}
  \centering
  \begin{subfigure}[t]{0.4\linewidth}
   \begin{tikzpicture}[scale=.8,auto,swap]
    \foreach \pos/\name in {{(1,3)/a}, {(2,2)/b}, {(2,3)/c}, {(4,2)/f}, {(4,6)/j}, {(3,4)/d}, {(4,1)/e}, {(5,2)/h}, {(3,5)/i}, {(4,7)/k}, {(5,6)/l}}
        \node[vertex, label=above left:$\name$] (\name) at \pos {};
    \node[vertex, label=above right:$g$] (g) at (4,3) {};
    \foreach \source/\dest in {a/c,c/b,c/d,d/g,g/f,f/e,f/h,d/i,i/j,j/k,j/l} \path[edge] (\source) -- (\dest);
   \end{tikzpicture}
   \caption{A tree $G$.}
   \label{fig:treeG2}
  \end{subfigure}\quad
  \begin{subfigure}[t]{0.5\linewidth}
   \begin{tikzpicture}[scale=.8,auto,swap]
    \foreach \pos/\name in {{(1,1)/a}, {(3,1)/b}, {(2,2)/c}, {(4,1)/e}, {(5,2)/f}, {(5,1)/g}, {(6,1)/h}, {(7,1)/i}, {(8,1)/k}, {(9,1)/l}}
       \node[svertex, label=left:$\name$] (\name) at \pos {};
    \node[svertex, label=above left:$d$] (d) at (5,3) {};
    \node[svertex, label=above left:$j$] (j) at (8,2) {};
    \foreach \source/\dest in {a/c,b/c,c/d,d/f,e/f,g/f,h/f,i/j,d/j,j/k,j/l} \path[edge] (\source) -- (\dest);
   \end{tikzpicture}
   \caption{The centroid decomposition of $G$.}
   \label{fig:centroidtree}
  \end{subfigure}
  \caption{Centroid decomposition.}
  \label{fig:centroid_decomposition}
\end{figure}

\begin{corol}
\label{ref:cor-reference}
For any tree $G$ on $n$ vertices, there exists a valid search tree $P$ on $G$ which is Steiner-closed\ and it has height at most $2 \log n +2$.
\end{corol}

This is because the centroid decomposition $C$ has height $\log n +1$, thus the tree $P$ can be obtained by applying Lemma~\ref{lem:steiner_ref} for $T=C$. The tree $P$ will be our reference tree in the rest of this paper. We need to show that each preferred path of $P$ can be stored in a search tree. To do that, we first observe that all preferred paths of $P$ are Steiner-closed.

\begin{obs}
\label{obs:Steiner_subtree}
If a search tree $T$ of a tree $G$ is Steiner-closed, then for all nodes $v$ in $T$, the subtree $T_v$ rooted at $v$ is also Steiner-closed.
\end{obs}

This comes from the fact that the subtree rooted at $v$ contains a connected component obtained after the removal of vertices in the path from the root of $T$ to the parent of $v$. Since $T$ is Steiner-closed, then  $T_v$ should also be Steiner-closed. This observation implies that all preferred paths of $P$ are Steiner-closed. The next lemma shows that a Steiner-closed\ set $S$ corresponds to a tree on $S$ which is a obtained by contracting edges of $G$.
Let $\bar{P}(a,b)$ denote the set of nodes $v \neq \lbrace a,b \rbrace$ of the path from $a$ to $b$.

\begin{defn}
\label{def:GS}
For a Steiner-closed set of vertices $S$ of $G$, let $G(S)$ to be the graph with vertex set $S$ where two vertices
$a,b\in S$ are connected by an edge if and only if no $c\in S$ is in $\bar{P}(a,b)$.
\end{defn}

Our next Lemma directly follows from Definition \ref{def:steiner-set}.
\begin{lemma}
\label{lem:search_tree_preferred}
For any Steiner-closed\ set $S$, $G(S)$ is a tree.
\end{lemma}

\begin{comment}
\begin{proof}
The proof has two steps. We first show that $G(S)$ is connected for any $S \subseteq V$. We then show that if $S$ is Steiner-closed, then $G(S)$ is a tree.

\paragraph{$G(S)$ is connected.} We show that for any two nodes $u$ and $v$ of $S$, there exists a path from $u$ to $v$ in $G(S)$. Clearly, if there are no vertices of $S$ in $\bar{P}(u,v)$, then there exists an edge $(u,v)$ in $G(S)$.

It remains to show that in case there are vertices of $S$ in $\bar{P}(u,v)$, then there exists a path from $u$ to $v$ in $G(S)$. We use induction on the number of such vertices. In the base case, there is only one vertex $w \in S$ in $\bar{P}(u,v)$. That means, in $G(S)$, there exist edges $(u,w)$ and $(w,v)$, thus there exists a path from $u$ to $v$.

 For the induction hypothesis, assume that it is true for the case of $i$ vertices of $S$ in $\bar{P}(u,v)$. We will show that in case there are $i+1$ vertices of $S$ in $\bar{P}(u,v)$, then $u$ and $v$ are connected in $G(S)$. Let $w_1,\dotsc,w_{i+1}$ be the vertices of $S$ that belong to $\bar{P}(u,v)$, such that $w_1$ is the closest to $u$ and $w_{i+1}$ the closest to $v$. By the induction hypothesis, there exists a path from $w_1$ to $v$ in $G(S)$, since there are $i$ nodes of $S$ in the path $\bar{P}(w_1,v)$. Since there is an edge $(u,w_1)$ in $G(S)$, we get that there exists a path from $u$ to $v$.

\paragraph{$G(S)$ has no cycles.} We now show that if $S$ is Steiner-closed, then $G(S)$ is a has no cycles. Since we know that $G(S)$ is connected, this implies that $G(S)$ is a tree.

The main observation here is that if $(u,v)$ is an edge of $G(S)$, then for any $a \in S$ $\St(a,u,v) \in \lbrace u,v \rbrace$. To see that, note that $\St(a,u,v) \in \CH(u,v) = P(u,v)$. Assume that $\St(a,u,v)$ is a node $w \in \bar{P}(u,v)$. By definition of $G(S)$ and the fact that $(u,v)$ is an edge of $G(S)$, we have that $w \notin S$. Thus $S$ is not Steiner-closed, a contradiction. We get that $\St(a,u,v) \in \CH(u,v) \setminus \bar{P}(u,v) = \lbrace u,v \rbrace $ for any $a \in S$.

Take a path $v_1,\dotsc,v_{\ell}$ in $G(S)$ for any $\ell \geq 3$. We claim that $v_2,\dotsc,v_{\ell-1}$ are in $\bar{P}(v_1,v_{\ell})$. This implies that there can not be an edge $(v_{\ell},v_1)$ in $G(S)$. Thus there are no cycles in $G(S)$.

We now prove the claim by induction. Base case $\ell=3$. Path $v_1,v_2,v_3$. There exist edges $(v_1,v_2)$ and $(v_2,v_3)$. By the observation above, $\St(v_1,v_2,v_3) = v_2$. That means, $v_2$ is between $v_1$ and $v_3$.

Induction step: Assume this is true for $\ell \geq 3$. That means $v_2,\dotsc,v_{\ell-1}$ are in $\bar{P}(v_1,v_{\ell})$. We will show that $v_{\ell}$ is in the path between $v_1$ and $v_{\ell+1}$, which implies that there can not be an edge $(v_{1},v_{\ell+1})$ in $G(S)$ and consequently no cycle of length $\ell+1$.

There exist edges $(v_{\ell-1},v_{\ell})$ and $(v_{\ell},v_{\ell+1})$. By the observation above, $\St(v_{\ell-1},v_{\ell},v_{\ell+1}) = v_{\ell}$, thus $v_{\ell}$ is between $v_{\ell-1}$ and $v_{\ell+1}$. Since by the induction hypothesis $v_2,\dotsc,v_{\ell-1}$ are in $\bar{P}(v_1,v_{\ell})$, we get that $v_2,\dotsc,v_{\ell-1},v_{\ell}$ are in $\bar{P}(v_1,v_{\ell+1})$.
 \end{proof}
\end{comment}

It now remains to show how to maintain the trees $G(S)$ corresponding to the preferred paths of $P$.

\subsection{Maintaining preferred paths with link-cut trees}
\label{subsec:aux}

 We now show that a collection of Steiner-closed preferred paths, each of which has length at most $k$, can be stored in a data structure supporting search, cut and merge at a cost of $O(\log k)$ in the GST model of computation. Our goal is to use this for the preferred paths of $P$ of length $k = O(\log n)$, to get the $O(\log k) = O(\log \log n)$ bound.

During an execution of a search sequence we need to perform the following operations on preferred paths:
\begin{enumerate}[(i)]
 \item Search for a node in a preferred path $\Pi$.
 \item Cut a preferred path $\Pi$ into two paths, one consisting of nodes of depth smaller than $d$ in $P$ and the other of nodes of depth at least $d$. We denote this operation $\cut(\Pi,d)$.
 \item Merge two preferred paths $\Pi_1$ and $\Pi_2$, where the bottom node of $\Pi_1$ is the parent of the top node of $\Pi_2$.
\end{enumerate}

Let $\Pi$ be a preferred path containing a Steiner-closed\ set of nodes $S$. In order to split $\Pi$ into two paths, we split $G(S)$ into two trees $G(S_1)$ and $G(S_2)$, where $S_1$ and $S_2$ are the nodes in $\Pi_1$ and $\Pi_2$. From Observation~\ref{obs:Steiner_subtree}, we know that the bottom part $\Pi_2$ is also Steiner-closed, which implies $G(S_2)$ is a tree. The path $\Pi_1$ is clearly Steiner-closed\, since $P$ is Steiner-closed.
In fact, from the Steiner-closed\ property and Lemma~\ref{lem:jit}, we have that $G(S_2)$ can be obtained from $G(S)$ by cutting at most two edges of $G(S)$.

Conversely, if we merge two preferred paths $\Pi_1$ and $\Pi_2$ into one path $\Pi$, where the bottom of $\Pi_1$ is connected to the top of $\Pi_2$ in $P$, we need to construct the tree $G(S)$, where $S$ is the union of the sets of nodes $S_1$ and $S_2$ in the paths $\Pi_1$ and $\Pi_2$. Again $G(S_2)$ can be merged with $G(S_1)$ to yield $G(S)$ by cutting $G(S_1)$ at at most two places, and linking the two trees by adding two edges.

\paragraph{Basic operations that need to be supported in logarithmic time.}
We need to implement a data structure supporting the above operations on the forest of trees $G(S)$ at $O(\log k)$ cost in the GST model.
Each of these operations can be split into a constant number of one of these two operations: {\em cut} a tree into two by removing an edge, and {\em link} two trees into one by adding an edge. In what follows, we refer to the trees $G(S)$, for each set $S$ of nodes in a preferred path of $P$, as the {\em represented trees}.

Here we resort to the classical link-cut trees data structure from Sleator and Tarjan\cite{ST83}. Link-cut trees can be used to implement link and cut operations on a forest of unrooted trees in amortized time proportional to the logarithm of the size of the largest tree in the forest. We refer to Tarjan's textbook for details~\cite{T83}.

The link-cut tree data structure implements a heavy-path decomposition on the represented trees. Each heavy path in this decomposition is in turn represented by a splay tree~\cite{ST85}. Note that this decomposition should not be confused with the decomposition of $P$ into preferred paths; we are performing two levels of decomposition into paths. Link-cut trees effectively reduce the problem of maintaining the forest of trees to binary search tree operations. Our data structure eventually consists of a hierarchy of splay trees, each representing a path in a tree $G(S)$, which in turn corresponds to a path in the reference tree $P$.

We now have to check that the whole structure is indeed a search tree on $G$, and that the binary search tree operations are indeed proper elementary operations in the GST model.
This we can observe by considering the first preferred path $\Pi$ in $P$ with nodes $S$, and the first heavy path in the decomposition of $G(S)$, stored as a splay tree. Searching in such a splay tree amounts to searching along a path of $G(S)$, whose convex hull is a path in $G$. Recalling our Observation~\ref{obs:gst2bst}, this is a proper search in the GST model. The search now proceeds by searching the next heavy paths in $G(S)$, and maybe switch to other preferred paths of $P$. Overall, this is a proper search in $G$. Similarly, rotations in the splay trees are rotations of the search tree on $G$ as defined in the GST model.

\subsection{Our Algorithm}
\label{subsec:alg}

Let us first sum up the overall data structure.
Given the graph $G$, we construct a balanced Steiner-closed\ search tree $P$ on $G$, which we refer to as the reference tree. We dynamically maintain a decomposition of $P$ into preferred paths. Each such preferred path with nodes $S$ corresponds to an unrooted tree $G(S)$, which is a minor of $G$. As searches are performed, preferred paths are updated, and these updates correspond to linking and cutting trees $G(S)$. For this, we use link-cut trees. Those in turn decompose the trees $G(S)$ into paths and reduce the operations to link and cut on paths. These operations can be handled by splay trees. Together, they form a search tree on $G$.

\paragraph{{\normalfont{\textbf{Bounding the cost.}}}} We now compare the cost of our Tango Search Tree\ data structure to $\OPT(G,X)$. The following lemma makes the essential connection between the number of preferred paths touched during a search and the cost of our algorithm.

\begin{lemma}
\label{lem:tango_wilber1}
Let $\ell$ be the number of preferred child changes during a search. Then the cost of this search is $O((\ell+1)(1+\log \log n))$.
\end{lemma}
\begin{proof}
During the search, the pointer touches exactly $\ell+1$ preferred paths. We account separately for the search cost and the update cost.

For each preferred path touched, the search cost is $O(\lceil \log \log n \rceil)$. Thus the total search cost is clearly $O((\ell+1)(1+\log \log n))$.

We now account for the update cost. Recall that we can cut and merge preferred paths on $k$ nodes in time $O(1 +\log k)$. Since each preferred path has at most $O(\log n)$ nodes, we can perform those updates in time $O(1 +\log \log n)$. There are $\ell$ preferred path changes, and for each change we perform one cut and and one merge operation, we get that the total time for merging and cutting is $O(\ell \cdot (1 +\log \log n))$.  The lemma follows. \end{proof}

We now combine this lemma with Theorem~\ref{thm:lower_bound} to get the competitive ratio of Tango Search Tree.

\begin{theorem}
\label{thm:tango_comp}
For any search sequence of length $m=\Omega(n )$, Tango Search Tree\ are $O(\log \log n)$-competitive.
\end{theorem}
\begin{proof}
We account only for the cost occurred during searches, since the cost of transforming the input tree into a valid Tango Search Tree\ is just a fixed additive term which does not depend on the input sequence.

By Observation~\ref{obs:preferred_path_changes} we have that the total number of preferred path changes is at most $I(G,P,X)+n$. Using Lemma~\ref{lem:tango_wilber1} and summing up over all search requests, we get that the cost of Tango Search Tree\ is $O((I(G,P,X)+n+m)(1+\log \log n))$.

By Theorem~\ref{thm:lower_bound} this is bounded by $O((\OPT(G,X)+n+m) \cdot (1+\log \log n) ) $. Note that $\OPT(G,X) \geq m$. Since $m=\Omega(n)$, we have that $  \OPT(G,X) + n +m = O( \OPT(G,X))$. We get that the total cost is upper bounded by \[  O \lrp{ \OPT(G,X) \cdot (1 + \log \log n) }. \qedhere \]
\end{proof}