From d8c3873255e71f3919a66e934135577c4d0f625d Mon Sep 17 00:00:00 2001 From: Marcin Chrzanowski Date: Thu, 16 Dec 2021 17:20:34 +0100 Subject: Proof --- mgr.tex | 10 +++++----- 1 file 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 -- cgit v1.2.3