diff options
| -rw-r--r-- | mgr.tex | 27 |
1 files changed, 2 insertions, 25 deletions
@@ -134,34 +134,11 @@ is the highest black node on the path between $x$ and $y$. We will build an index structure, constructible in linear time, that allows us to handle such queries in constant time. The structure is heavily inspired by -Schieber and Vishkin's structure for computing LCA queries. We will present our -version of the structue in full detail, using Schieber and Vishkin's notation -where possible. +Bender and Farach-Colton's presentation of an algorithm originally attributed to +Berkman and Vishkin for computing LCA queries. \subsection{High level overview} -The LCA algorithm given by Schieber and Vishkin bases on two observations, first -made by Harel and Tarjan: - -\begin{itemize} - \item LCA queries can be computed in constant time on \emph{simple paths}. - \item LCA queries can be computed in constant time on \emph{full binary trees}. -\end{itemize} - -We map vertices of our tree $T$ to vertices of a full binary tree $B$ of size -$O(n)$ that has two properties: - -\begin{enumerate} - \item The induced subgraph of all vertices mapped to the same node of $B$ is - a simple path in $T$. - \item If a vertex $v$ of $T$ is mapped to a vertex $b$ of $B$, all of its - descendants are mapped to descendants of $b$ (where $b$ is also a - descendant of itself). -\end{enumerate} - -From 2. we get that also all of $v$'s ancestors are mapped to $b$'s ancestors in -$B$, in particular they are all mapped into at most $\log(n)$ nodes of $B$. - \section{Generalizing words to trees} \chapter{Conclusions} |