diff options
| -rw-r--r-- | mgr.tex | 10 |
1 files changed, 5 insertions, 5 deletions
@@ -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 |