经过了前面三篇( 一 twintree 树,二 baxter 数,三 floorplan 画) 看似"毫无关系"的介绍,关子也到此结束,终于要揭露他们之间的关系了.相信看完这篇你也能感受到这些数据结构和数学的奇妙之处.
细心的同学发现原来 floorplan 图里的坐标在树上体现不出来,确实如此,我在这里分享原图,感兴趣的同学可以在树的基础上标记出来,看看你能新发现什么.
通过上面不太严谨的表达,我们已经可以看到这三个看似无关的表达,其实却是互通的,每个都可以转化成另一种形式.事实上,根据这篇论文 n 个长方形所组成的 floorplan(准确地说是 mosaic floorplan,区别于 slicing floorplan)的个数和 baxter 数是一样的. 另外在 Knuth 视频的最后也展示了这三种表达能通过程序相互转化(不包括 floorplan 的坐标). 这就是 Knuth 圣诞三重奏所有要讲的,视频里也不忘推荐下他将要出版的 TAOCP 4B,出现在第 7 章的大量练习中,期待中文译本国内也能尽快买到.