@*Intro. This (hastily written) program computes the Baxter permutation that corresponds to a given twin tree. See exercises MPR--135 and 7.2.2.1--372 (as revised in the third and subsequent printings of {\sl The Art of Computer Programming}, Volume~4, Fascicle~5) for an introduction to the relevant concepts and terminology. According to exercise 7.2.2.1--372, a twin tree is a data structure characterized by the following interesting properties: (i)~There are $n$ nodes, each of which has four fields called $l_0$, $r_0$, $l_1$, $r_1$. (ii)~The $l_0$ and $r_0$ fields are the left and right links of a binary tree~$T_0$ that's rooted at node~$t_0$. (iii)~The $l_1$ and $r_1$ fields are the left and right links of a binary tree~$T_1$ that's rooted at node~$t_1$. (iv)~The symmetric order of both trees (also called inorder'') is $1\,2\ldots\,n$. (v)~For $1\le k #include @; @; void main(void) { register int i,j,k,l,m,n; @; @; @; } @ Notice that$r[k]$is null if and only if$l[k+1]$is nonnull, in {\it any\/} binary tree whose inorder has$k+1$following~$k$. Therefore, using condition~(v),$l_0[k]=0$if and only if$l_1[k]>0$, for$1= if (fscanf(stdin,"%d %d", &t0,&t1)!=2) pan("I can't read the root numbers"); for (l=maxn,m=n=0; fscanf(stdin,"%d", &inx)==1; n++) { if (inx<=0 || inx>l) panic("bad index",inx); if (inx>m) m=inx; if (fscanf(stdin,"%d %d %d %d", &l0[inx],&r0[inx],&l1[inx],&r1[inx])!=4) panic("I can't read l0,r0,l1,r1",inx); if (l0[inx]<0 || l0[inx]>l) panic("l0 out of range",inx); if (r0[inx]<0 || r0[inx]>l) panic("r0 out of range",inx); if (l1[inx]<0 || l1[inx]>l) panic("l1 out of range",inx); if (r1[inx]<0 || r1[inx]>l) panic("r1 out of range",inx); if (l0[inx]>=inx || l1[inx]>=inx) panic("l0 or l1 too big",inx); if ((r0[inx] && r0[inx]<=inx) || (r1[inx] && r1[inx]<=inx)) panic("r0 or r1 too small",inx); if (l0[inx]!=0 && l1[inx]!=0) panic("l0 and l1 overlap",inx); if (r0[inx]!=0 && r1[inx]!=0) panic("r0 and r1 overlap",inx); if (r0[inx]==r1[inx]) l=inx; /* this |inx| should be the final |n| */ } if (mn) panic("too few lines of input",m-n); if (l!=n) pan("r0 and r1 zero before item n"); /* it's not easy to get that error! */ @ @= int inx; /* data input with |fscanf| */ int t0,t1; /* the roots of $T_0$ and $T_1$ */ int l0[maxn+1],r0[maxn+1],l1[maxn+1],r1[maxn+1]; /* the links */ @ We must verify that the arrays $l_0$, $r_0$, $l_1$, $r_1$ define binary trees whose nodes are 1, 2, \dots,~$n$ in symmetric order. This is textbook stuff---and fun, because it isn't quite as simple as it may seem at first! We've got to make sure that bad input doesn't get us into an infinite loop, which might happen for example if $l[k]=j$ and $r[j]=k$. @= checkinorder0(t0,1,n); checkinorder1(t1,1,n); @ @= void checkinorder0(int root,int lb,int ub) { if (l0[root]==0) { if (root!=lb) panic("inorder0 fails left",root); }@+else { if (l0[root]ub) panic("inorder0 off right",root); checkinorder0(r0[root],root+1,ub); } } @# void checkinorder1(int root,int lb,int ub) { if (l1[root]==0) { if (root!=lb) panic("inorder1 fails left",root); }@+else { if (l1[root]ub) panic("inorder1 off right",root); checkinorder1(r1[root],root+1,ub); } } @*Handy facts about Baxter permutations. As above, let $P$ be the permutation $p_1p_2\ldots p_n$, and let $T_0$ and $T_1$ be the twin trees that result by inserting the elements of $P$ and its reflection $P^R=p_n\ldots p_2p_1$ into an initially empty binary tree. Then the twin trees obtained from $P^R$ are obviously $T_1$ and $T_0$. We can express that condition algebraically by writing $$T_\theta(P^R)=T_{\bar\theta}(P).$$ And it's easy to see, directly from the definition, that $P$ is Baxter if and only if $P^R$ is Baxter: Condition~$(*)$ for~$P$ is condition~$(**)$ for $P^R$, and vice versa. @ The {\it complement\/} of $P$ is $P^C=\bar p_1\bar p_2\ldots\bar p_n= (n{+}1{-}p_1)(n{+}1{-}p_2)\ldots(n{+}1{-}p_n)$, obtained by swapping $1\leftrightarrow n$, $2\leftrightarrow n-1$, etc. The twin trees corresponding to $P^C$ are clearly obtained by reversing the roles of left and right---reflecting each tree. That is, when $l[k]=j$ in~$T$, we have $r[\bar k]=\bar\jmath$ in the reflected tree~$T^R$; similarly, $r[k]=j$ in~$T$ implies $l[\bar k]=\bar\jmath$ in $T^R$. Thus we can write $$T_\theta(P^C)=T_\theta(P)^R.$$ Again, $P$ is Baxter if and only if $P^C$ is Baxter---because complementation, like reflection, interchanges conditions $(*)$ and~$(**)$. (Notice that $\overline k=\overline{k+1}+1$.) @ The {\it inverse\/} of~$P$, namely $P^-=q_1q_2\ldots q_n$ where $p_j=k$ $\iff$ $q_k=j$, is of course a third basic operation that takes permutations into permutations. This operation is important to us because of the following basic principle of afterness'': $$\displaylines{ \hskip3em\hbox{p_k>p_l \iff k comes after l in P^-;}\hfill(\dag)\cr \hskip3em\hbox{k comes after l in P \iff q_k>q_l.}\hfill(\ddag)\cr }$$ @ Indeed, the definition of Baxter-hood can be restated nicely in terms of $p$'s and $q$'s: A~permutation is Baxter if and only if it doesn't have indices $k$ and~$l$ such that $$\displaylines{ \hskip3em\hbox{q_{k+1}l+1 and p_lk+1;}\hfill(*)\cr \hskip3em\hbox{q_kl+1 and p_l>k+1 and p_{l+1}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.