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

引言

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

这三个主题分别是：

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

Twintree

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

叶子和非叶

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

稍微解释下因为 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。