diff options
| -rw-r--r-- | mgr.tex | 34 |
1 files changed, 28 insertions, 6 deletions
@@ -443,14 +443,36 @@ array \indextable. \begin{observation} Given a node $x$ and its descendant $y$, looking at the range - $\prefixtable[\indextable[y], \indextable[x] - 1]$, all the values in this - range are descendants of $x$, and the values smaller than - $\prefixtable[\indextable[y]]$ correspond to ancestors of $y$. In - particular, the minimum of that range corresponds to the highest ancestor of - $y$ that is also a descendant of $x$. + $\prefixtable[\indextable[y], \indextable[x] - 1]$: + \begin{enumerate} + \item All the values in this range correspond to descendants of $x$. + \label{obs-descendants} + \item The values smaller than $\prefixtable[\indextable[y]]$ correspond + to ancestors of $y$. \label{obs-ancestors} + \item In particular, the minimum of this range corresponds to the + highest ancestor of $y$ that is also a descendant of $x$. + \label{obs-conclusion} + \end{enumerate} \end{observation} -In our problem, we only care about ancestors of $y$ that are colored black. So +The pre-order labels in \prefixtable\ are ordered according to a post-order. In +a post-order, the root of a subtree is visited directly after all its +descendants. Since $y$ is a descendant of $x$, all values between its position +in \prefixtable\ and $x$'s position there will also be descendants of $x$, +giving item \ref{obs-descendants}. + +The values in \prefixtable\ are pre-order numbers. In a pre-order, for a given +node $z$, the only nodes that will have lower pre-order numbers are $z$'s +ancestors, and the children of these ancestors that are to the left of the child +towards $z$. By starting our range at index $\indextable[y]$, we've skipped over +all of the second types of vertices with lower pre-order numbers, leaving only +$y$'s ancestors as nodes in the range with a lower pre-order number. This gives +us item \ref{obs-ancestors}. + +Items \ref{obs-descendants} and \ref{obs-ancestors} together give us item +\ref{obs-conclusion}. + +In our problem, we only care about ancestors of $y$ that are marked. So we perform one final modification of our data structure: for all non-black vertices $v$, we change $\prefixtable[\indextable[v]]$ to $\infty$ (which can be represented by $n+1$, an integer greater than any node's pre-order label). With |