diff options
| -rw-r--r-- | mgr.tex | 51 |
1 files changed, 49 insertions, 2 deletions
@@ -134,10 +134,57 @@ 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 -Bender and Farach-Colton's presentation of an algorithm originally attributed to +Bender and Farach-Colton's presentation of an algorithm originally described by Berkman and Vishkin for computing LCA queries. -\subsection{High level overview} +First, let's define an auxillary problem we will use, that of Range Minimum +Queries (RMQ): + +\emph{Given}: an array $A$ of integers. + +\emph{Queries}: given indices $i$ and $j$, return the index of the smallest +element in the subarray $A[i, j]$. + +Fact: RMQ queries can be answered in constant time after linear preprocessing of +the input array. + +We turn to describing the index structure for our tree problem. + +First, we create the array $POST$ of length $n$, which is the post-order of the +nodes. + +Next, we label each node of the tree with its pre-order number. We create the +array $PRE$ with the corresponding pre-order labels of the nodes in $POST$, i.e. +if $POST[i] = v$, then $PRE[i]$ is $v$'s pre-order number. + +Finally, for each node of the tree, we record its index in $POST$ in the array +$INDEX$. + +Observation: given a node $x$ and its descendant $y$, looking at the range +$PRE[INDEX[y], INDEX[x] - 1]$, all the values in this range are descendants of +$x$, and the values smaller than $PRE[INDEX[y]]$ correspond to ancestors of $y$. +In particular, the minimum of that range corresponds to the highest ancestor of +$y$ that's a descendant of $x$. + +In our problem, we only care about ancestors of $y$ that are colored black. So +we perform one final modification of our data structure: for all non-black +vertices $v$, we change $PRE[INDEX[v]]$ to $\infty$ (which can be represented by +$n+1$, an integer greater than any node's pre-order label). With $PRE$ modified +like this, we observe that now the minimum value of $PRE[INDEX[y], INDEX[x] - +1]$ corresponds exactly to the answer of our queries -- the highest black node +between $x$ and $y$. + +We preprocess $PRE$ for RMQ queries in linear time. + +Now when given a query $x$, $y$, we: + +\begin{enumerate} + \item Lookup $i := INDEX[y]$ and $j := INDEX[x] - 1$. + \item Perform an RMQ query on $PRE[i, j]$, giving us index $k$ of the + minimal value in that range. + \item Lookup the corresponding vertex as $z := POST[k]$. This is the + answer to our query. +\end{enumerate} \section{Generalizing words to trees} |