1. 三重奏其一 twintree
  2. 三重奏其二 baxter
  3. 三重奏其三 floorplan
  4. 三重奏终章

引言

Knuth 今年圣诞在 Stanford 做了一次演讲,讲了三种看似毫无关联的主题,但最终能相互转换,这系列文章将会分成 4 部分依次介绍这 3 个主题,最后再将这些“调料”烩在一起组成一道“圣诞大餐”。感兴趣的可以直接观看原视频。

这三个主题分别是:

  1. Twintree 孪生二叉树
  2. Baxter permutation 一种组合数学中的排列
  3. Floorplan 一种切分长方形为更小长方形的方法。

Twintree

Twintree 是一种二叉树的表达,对于 1 到 n 的任意排列,按照该排列进行二叉树插入,我们称这棵树为蓝树,然后反转排列再次进行二叉树插入,称这棵树为红树,比如演讲中提到的排列 \(71532846\) 和它的反转 \(64823517\),插入的二叉树如下图: image

叶子和非叶

注意到蓝树的叶子节点在红树一定是非叶节点,反之亦然,比如 7 在蓝树有 2 个子树,在红树就是叶子节点,那么我们可以列出一个关于左右子树的表格,并把每个节点的左右子树序号填进去,这样没有重复没有遗漏,如下表:

  1 2 3 4 5 6 7 8
L X 1 2 2 3 4 1 7
R 5 3 4 5 6 8 8 X

稍微解释下因为 1 是最小的节点,所以肯定没有右子树,8 是最大的节点,肯定没有右子树,这里用 X 表示。

插入顺序

另外一个性质是,如果一个节点 \(k\) 没有左子树,那么当且仅当 \(k-1\) 在 \(k\) 之前插入,对照上表发现几乎每个节点都有左子树,那这个性质只适用于最小的节点 \(1\) 吗?并不是。因为我们只写了有左子树的节点,而在上一小节说如果节点是非叶则另一棵树的相同节点一定是叶子,比如节点 \(2\) 在红树有左子树,那在蓝树它一定是叶子(即没有左子树),因此在蓝树 \(1\) 节点一定在 \(2\) 之前插入,也就是它的祖先节点。因为 \(k\) 和 \(k-1\) 之间没有别的整数,所以很容易证明充要性。

在刚才的前提下,当且仅当 \(k-1\) 的右子树不为空,因为 \(k\) 在 \(k-1\) 之后插入,所以插入 \(k\) 的时候一定走右边。反过来 \(k-1\) 有右子树,那 \(k\) 一定在 \(k-1\) 之后插入(不这么插肯定是把 \(k\) 插错了)。符号化的表达如下,注意 \(\land\) 这里表示空的意思:

\(L[k]=\land \iff \text{k-1 inserted before k} \iff R[k-1]\not =\land\) \(R[k]=\land \iff \text{k+1 inserted before k} \iff L[k+1]\not =\land\)

未完待续

到这 Twintree 就讲完了,构造就是按照排列正着插入二叉树,再反着插入一遍,两个性质从图和表格上看也很容易理解,下一篇会介绍 Baxter permutation。