栈置换–二叉树同构 [stack-tree-isomorphism]

Definition 1. 栈置换 [stack-permutation]

栈置换 (stack permutation) 也称作栈混洗 (stack shuffle). 给定一个非空栈 $A$ 和空栈 $B$ 与 $S$, 每次只允许 $(i)$ 弹出 $A$ 并压入 $S$. $(ii)$ 弹出 $S$ 并压入 $B$. 可以想见, 最终 $A$ 的元素一定会全部进入 $B$. 这样的 $B$ 就称为 $A$ 的一个栈置换.

不难发现, $A$ 的所有栈置换其实就是 $A$ 的所有出栈可能. 熟知 $n$ 元素栈共有 $\frac1{n+1}{2n \choose n}$ 种出栈情况. 另一方面, $n$ 个节点能构成 $\frac1{n+1}{2n \choose n}$ 种二叉树, 两者的计算都可以在 Catalan 数的相关条目中找到. 这表明两者作为集合同构, 一个可以考虑的问题是, 如何实现该同构? 即, 具体地写出这个双射. 这方面的 开创性工作 来自 R. F. Hille.

Definition 2. Hille 编码 [hille-encode]

以下三条规则给出 Hille 编码到二叉树的转换过程. 同时不难验证, 任给一个二叉树, 可以通过这三条规则得到其 Hille 编码.

  • 1 表示添加当前树节点的左子树. 例如 111 表示的树为 (⋅ (⋅ (⋅))).
  • 01 表示添加当前树节点的右子树. 例如 10101 表示的树为 (⋅ _ (⋅ _ (⋅))).
  • 而对于 01 前的 $k$ 个 0, 这些 0 用于表示将当前树节点回溯到前 $k$ 层. 例如 11001 表示的树为 (⋅ (⋅) (⋅)).

注意到每个树节点的双亲 (parent) 节点是唯一的, 因此回溯操作良定, 一次回溯就是将当前节点改为其双亲.

相应的, 可以据此定义 Hille 编码的解析规则, 用于将这样一段有效的二进制序列转换为构造一颗二叉树的若干操作. 我们使用一种类 BNF 文法来定义这个解析器, 仅供读者理解.

由于我们的讨论不涉及具体元素, 不失一般性, 可以固定栈置换的入栈顺序为 $123\cdots n$. 同时这些数字也是二叉树节点的标签. 影响出栈序列的只有压入和弹出两个操作, 而构建二叉树允许的操作粗看起来要多一些. 因此首先需要通过一些技巧将二叉树构建操作的表示简化. 我们将栈的压入和弹出分别编码为 1 和 0, 并将栈置换对应的二进制序列称为栈编码. 对应的, 以 Hille 编码 刻画二叉树的构建.

Example 3. $n=3$ [stack-permutation-000A]

以下写出三节点二叉树的所有 $5$ 种情况, 以展示这些树的二进制序列如何对应到栈置换. 此处二进制序列按栈弹空为标准, 补充了末尾的零.

这个过程的反向实际上并不平凡, 如果只考虑 $n=3$ 也就是上图的情况, 敏锐的读者可以发现, 这些栈置换其实就是二叉树按节点添加顺序 1 编号后的中序遍历序列 2. 我们接下来将解释其中的不平凡之处, 以及这一巧合发生的 具体条件. 首先是对原始文献的一个观察, Hille 原始文献 当中提出的算法实际上存在错误, 将之改写成 Lean4 语言, 即

def encode : Tree → String
  | .node l r => "1" ++ encode l ++ encode r
  | _ => "0"

只要考虑下面这个例子即可发现, 将一棵二叉树转化为它的 Hille 编码并非是简单的中序遍历.

可以验证, 从 110100100 这个编码出发, 无法直接恢复原本的 , 其正确的 Hille 编码应该为 1101000100. 但是另一方面, 如果将序列 110100100 解释为栈的压入弹出操作, 即栈编码, 则可以得到正确的栈置换 2314. 这就意味着, 当二叉树的节点个数 $n > 3$ 时, 存在二叉树使得其栈编码与 Hille 编码不同. 回忆二叉树和栈置换之间的双射关系, 这表明必然存在一套手续允许我们在两者之间互相转换, 下面我们将构造性地给出这个结果. 见 栈编码与 Hille 编码的等价性. 随后通过 相交率 解释, 为何中序遍历在 $n$ 不大情况下能够频繁得到正确的 Hille 编码.

Proposition 4. 栈编码与 Hille 编码的等价性 [stack-permutation-000B]

首先容易验证的是, 中序遍历总是能够给出二叉树 $b \in B$ 到栈置换 $s \in S$ 的映射, 而对于每一个栈置换 $s \in S$, 都能够写出唯一的二进制序列, 即栈编码 $c \in C$. 不考虑末尾连续的 0, 当栈编码 $c$ 与二叉树 $b$ 的 Hille 编码 $h \in H$ 相同时, 对 $B$ 直接进行中序遍历便能得出正确的 Hille 编码.

$$ \begin{CD} B @>>> S \\ @VVV @VVV \\ H @>>> C \end{CD} $$

Proof. [stack-permutation-000C]

记 $B \to H$ 为 $f$, 根据 Hille 编码 的定义, $f$ 是一个双射. 根据二叉树的性质, $g: B \to S$ 是中序遍历, 前文已经固定栈置换的入栈顺序为 $123\cdots n$, 这样一来就固定了 $B$ 的层序遍历, 因此 $g$ 也是双射. 现在来看 $h: S \to C$, 这显然也是一个双射. 最后, 我们能够从 $h \in H$ 当中恢复出 $c \in C$ 的信息, 只要将 $h$ 序列视为栈编码, 并且忽略空栈的弹出, 这就意味着 $H \to C$ 是满射, 随后利用 $C \to S \to B \to H$, 这样就得到了 $H \cong C$.

现在, Hille 原文所使用的 encode 算法就是 $h \circ g: B \to C$, 而预期的正确实现则是 $f$, 因此两者在结果上相差一个同构.

Proposition 5. 相交数 [stack-permutation-000D]

$\gdef\eqdef{\overset{\scriptscriptstyle\text{def}}{=}}$ $\gdef\spaces#1{~ #1 ~}$

所有 $n$ 节点二叉树的 Hille 编码构成的集合记为 $H_n$, 所有 $n$ 节点二叉树的栈编码构成的集合记为 $C_n$. 对于 $H_n \cap C_n$ 的大小 $a_n \eqdef |H_n \cap C_n|$, 我们有如下刻画.

$$ a_n \spaces= \sum_{k = 0}^{n-1} \sum_{j = 0}^{n-k} \frac{1}{j+1}\binom{n-k-j}j \binom kj \binom{k+j+2}j $$

记 $N = n+1$. 等式的证明可以通过分析一个半长为 $N$ 且不包含 UUDD 子序列的 Dyck 路径得到. 同时这也是从 $(0,0)$ 到 $(N,N)$ 不越过对角线且允许步长 $(1,k), (k,1), k \geqslant 1$ 的格路径的个数. 或者更简单地说, 是长度为 $N$ 的斜 Motzkin 路径的个数.

Corollary 6. 相交率 [stack-permutation-000E]

记 Catalan 数为 $c_n$, 也即 $H_n$ 或 $C_n$ 的个数. 自然要问 $|H \cap C_n|$ 在全体 $n$ 节点二叉树个数中所占的比例与 $n$ 的关系. 根据 相交数 与 Catalan 数的渐进估计 $a_{n} \sim \frac{\sqrt{2 + r}}{2\sqrt{\pi}n^{3/2}r^{n}}$, $c_n \sim \frac{4^n}{\sqrt\pi n^{3/2}}$ 可以知道 $\lim\limits_{n\to\infty} \frac{a_n}{c_n} = 0$. 并且事实上只要二叉树的节点个数 $n$ 大于 $8$, $H_n$ 与 $C_n$ 相同的部分就会少于整体的一半.

Exegesis 7. 有效长度的上下界 [stack-permutation-000F]

$\gdef\spaces#1{~ #1 ~}$

一个可供探究的问题是, 给定 $n$ 节点二叉树, 询问其 Hille 编码 $H_n$ 有效长度 $\ell(H_n)$ 的范围. 这里的有效不外乎是指去除末尾连续的 0. 我们将对此问题给出确切的回答.

任意 $n$ 节点二叉树的 Hille 编码的有效长度满足下面的不等式

$$n \spaces\leqslant \ell_{n} \spaces\leqslant \max(0,2n - 1,3n - 4)$$

下界 $n$ 的验证是容易的, 构造一棵 $n$ 节点二叉树最少也需要 $n$ 个 1. 由于 此处 的讨论, 我们只需要验证 $n \geqslant 3$ 时 Hille 编码的有效长度至多是 $3n - 4$.

Proof. [stack-permutation-000G]

注意到为使有效长度最大, 相应的二叉树中的右节点个数和回溯次数要尽可能多. 同时满足这两个要求意味着 $(i)$ 除根节点外至少有一个左结点 1. $(ii)$ 该二叉树必有一个位于根节点右侧的节点 2. 如下图所示

由此出发, 我们将剩余的所有 $n-3$ 个节点全部添加到树中唯一的左节点的右侧. 即

下面我们只需算出 $\ell(M)$, 便可得到 $\ell_n$ 的最大值. 不妨直接写出 $h(M)$

立刻看出 $\ell(M) = 2 + 2(n-3) + (n-2) + 2 = 3n-4$.

1

如若不然, 这颗二叉树只会形如 1010101$\cdots$, 其长度为 $2n - 1$.

2

否则回溯贡献的长度便不是最大值 $n-2$.

反过来, 从树 $M$ 出发, 也可以验证任何使得节点总数不变的操作都不会增加其 Hille 编码的有效长度. 更进一步, 我们可以断言任何使得节点总数不变的操作都将严格减小其 Hille 编码的有效长度. 换言之, 使得 $\ell(B) = 3n-4$ 的二叉树 $B$ 的结构是唯一的, 即 $M$.

1

即按照 Hille 编码逐步添加节点的顺序.

2

如二叉树 1101000100 按添加顺序对节点编号, 然后做中序遍历得到的是 2314.