m-chrzan.xyz
aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--mgr.tex10
1 files changed, 5 insertions, 5 deletions
diff --git a/mgr.tex b/mgr.tex
index b675720..bda5183 100644
--- a/mgr.tex
+++ b/mgr.tex
@@ -626,11 +626,11 @@ array $\indextable$.
\end{enumerate}
\end{observation}
-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}.
+Proof: 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