Stanford Lecture - Don Knuth - Twintrees, Baxter Permutations, and Floorplans (2022)

Explore the fascinating connections between twintrees, Baxter permutations, and floorplans in this Stanford lecture by renowned computer scientist Donald Knuth. Delve into three seemingly unrelated concepts that are actually in one-to-one correspondence through beautiful algorithms. Learn about the data structure involving pairs of binary trees introduced by Dulucq and Guibert, the class of permutations introduced by Baxter, and the geometric understanding of rectangle decomposition introduced by Murata, Fujiyoshi, Watanabe, and Kajitani. Discover insights on binary tree insertion, pi mutation, sub-rectangles, canonical forms, and junctions as Professor Knuth, the esteemed author of "The Art of Computer Programming," presents his annual Christmas Tree Lecture.

Introduction
Twintrees
Binary tree insertion
The plan
Baxter permutations
Pi mutation
Sub rectangles
Floorplans
Canonical Form
Junctions