$\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]

• November 06, 2024
• kokic

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

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

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

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

¹

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

²

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

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