p_n$.
Indeed, this operation is equivalent to deleting~$n$ from
the inverse permutation!
For example, we've seen that 218367945 is a Baxter permutation.
Its inverse, 214895637, is therefore also Baxter. Removing 9 gives
the Baxter permutation 21485637, whose inverse 21735684 is Baxter.
@ Similarly, we can remove 1 and decrease each remaining element by~1.
We can also remove $p_1$, and renumber the others.
Indeed, a moment's thought shows also the converse: If $P$ is non-Baxter,
we can use some combination of the operations remove-the-largest,
remove-the-last, remove-the-smallest, and/or remove-the-first, until
we reach either 3142 or 2413.
@*Solving the problem.
Instead of renumbering, after the deletion of $n$ or $p_n$ or $1$ or $p_1$
from a Baxter permutation, we can simply consider the remaining sequence
to be a permutation of the numbers that are left; and we can form a
twin tree with them, ignoring the tree links from nodes that have
been removed.
For example, we can regard `2763' as a permutation of the elements
$\{2,3,6,7\}$. Tree $T_0$ of its twin tree structure has root~2 and
links
$$\thinmuskip=7mu
l_0[2]=0,r_0[2]=7;\
l_0[3]=0,r_0[3]=0;\
l_0[6]=3,r_0[6]=0;\
l_0[7]=6,r_0[7]=0;$$
tree $T_1$, similarly, has root~3 and links
$$\thinmuskip=7mu
l_1[2]=0,r_1[2]=0;\
l_1[3]=2,r_1[3]=6;\
l_1[6]=0,r_1[6]=7;\
l_1[7]=0,r_1[7]=0.$$
All other links are irrelevant.
The inorder of both trees is the natural order of the elements that
remain, namely 2367.
Call this a ``generalized twin tree,'' for a ``generalized permutation.''
If $k$ is an element of a generalized permutation, the notation
`$k+1$' stands not for the sum of $k$ and~1 but rather for the
element that immediately follows~$k$, namely $k$'s inorder successor.
In our example, $3+1=6$ and $6-1=3$.
@ Recall that our task is to
discover a Baxter permutation that yields a given twin tree.
We might as well extend that task, by assuming that's we've been
given a {\it generalized\/} twin tree, for which we want to
discover a {\it generalized\/} Baxter permutation.
Suppose we've been given a generalized twin tree with $n$ nodes. The solution is
obvious when $n=1$, so we may assume that $n>1$.
The first step is also obvious: We know $p_1$, because it's the root of~$T_0$.
So our strategy will be to delete $p_1$ from the generalized twin tree,
then figure out what generalized twin tree should produce the
other elements $p_2$, \dots,~$p_n$ of the generalized permutation.
Let $p=p_1$.
Notice that $p$ is always a leaf of $T_1$, because it was the
last element inserted into that tree. So it's easy to remove $p$ from~$T_1$;
we simply zero out the link that pointed to it.
There are two cases. If $p$ was a left child, say $l_1[i]=p$,
we'll want to set $l_1[i]\gets 0$. In that case $i=p+1$, the
inorder successor of~$p$. Otherwise $p$ was a right child,
say $r_1[i]=p$, and we'll want to set $r_1[i]\gets0$;
in that case $i=p-1$, the inorder {\it predecessor\/} of~$p$.
How should we remove $p$ from~$T_0$? If $l_0[p]=0$,
we simply move the root of~$T_0$ down to $r_0[p]$. Similarly,
if $r_0[p]=0$, we simply move $T_0$'s root to $l_0[p]$.
But if both $j=l_0[p]$ and $k=r_0[p]$ are nonzero,
we need to decide which of them should be the new root of~$T_0$,
depending on which of them came earlier in the permutation we're
trying to discover. And we also need to figure out how to
merge the other nodes into a single tree.
Fortunately there's only one way to go. Suppose, for instance, that
$i=p+1$; the other case is symmetrical. Since $j=
for (k=1;k<=n;k++) {
if (l1[k]) parent[l1[k]]=k;
if (r1[k]) parent[r1[k]]=-k;
}
while (1) {
printf("%d ",
t0); /* the first element, $p$, of the remaining generalized perm */
i=parent[t0];
if (i>0) { /* $i=p+1$, the case considered above */
l1[i]=0; /* remove $p$ from $T_1$ */
if (r0[t0]==0) t0=l0[t0]; /* |p| is the largest that remains */
else {
l0[i]=l0[t0];
t0=r0[t0];
}
}@+else if (i==0) break; /* tree size was 1 */
else {
i=-i; /* $i=p-1$, the symmetrical case */
r1[i]=0; /* remove $p$ from $T_1$ */
if (l0[t0]==0) t0=r0[t0]; /* |p| is the smallest that remains */
else {
r0[i]=r0[t0];
t0=l0[t0];
}
}
}
printf("\n");
@ @=
int parent[maxn+1]; /* parents in $T_1$ */
@*Index.