@*Intro. This program solves exercise 6.2.2--50 of {\sl The Art of
Computer Programming\/} (which was added to Volume 3 in September, 2021,
just in time for the 43rd printing!). Here's the statement of that exercise:
\medskip
{\narrower
\noindent{\bf50.}
[30] Let $p_1p_2\ldots p_n$ be a permutation of $\{1,2,\ldots,n\}$.
Suppose the values $p_1$, $p_2$, \dots,~$p_n$ have been inserted successively
into an initially empty binary tree using Algorithm~T, but with $\.Q\gets K$
in step~T5 when storing key~$K$. Explain how to compute all of
the resulting links
\.{LLINK($k$)} and \.{RLINK($k$)} for $1\le k\le n$ in just $O(n)$ steps.
$\bigl($For example, the permutation 3142 would yield
$(\.{LLINK($1$)},\ldots,\.{LLINK($4$)})=(\Lambda,\Lambda,1,\Lambda) $ and
$(\.{RLINK($1$)},\ldots,\.{RLINK($4$)})=(2,\Lambda,4,\Lambda)$.$\bigr)$
\par
}
\medskip
\noindent
The following solution, suggested by Robert E. Tarjan, implicitly uses the
one-to-one correspondence between binary search trees and binary
tournaments in \S3 of Jean Vuillemin's classic paper ``Cartesian trees,''
{\sl Communications of the ACM\/ \bf23} (1980), 229--239. (Stating this
another way, it implicitly uses the fact that the binary search tree
defined by a permutation has the same shape as the ``increasing binary tree''
defined by the {\it inverse\/} of that permutation. The increasing
binary tree defined by a permutation retains symmetric order, but
forces all paths from the root to be increasing.)
@ The given permutation should appear on |stdin|, as the sequence of
numbers $p_1$ $p_2$ \dots~$p_n$, separated by whitespace.
The output on |stdout| will show the root, followed on separate lines
by the links of 1, 2, \dots, $n$.
@d maxn 1024
@d panic(m,k) {@+fprintf(stderr,"%s! (%d)\n",
m,k);@+exit(-666);@+}
@d pan(m) {@+fprintf(stderr,"%s!\n",
m);@+exit(-66);@+}
@c
#include
#include
int p[maxn+2]; /* the given permutation */
int q[maxn+2]; /* its inverse */
int stack[maxn+1]; /* the working stack */
int stackx[maxn+1]; /* indexes associated with the working stack */
int llink[maxn+2],rlink[maxn+1]; /* the answers */
int inx; /* a place for input data from |fscanf| */
void main(void) {
register int i,j,k,m,n,s;
@;
@;
@