TitleComputer musings: the associative law, or the anatomy of rotations in binary trees
CreditsKnuth, Donald E.
PublisherUniversity Video Communications
Copyright HolderComputer History Museum
DescriptionFrom University Video Communications' catslog:
"Donald Knuth presents a simple proof of Tamari's theorem: the set of binary trees with 'n' nodes forms a lattice under a one-way associative law. As a consequence of the associative law (ab)c-a(bc), any two ways of parenthesizing a formula are equal when variables appear in the same order from left to right. The one-way associative law (ab)c->a(bc) can be construed as a reduction yielding a right-hand side. After presenting a simple encoding of binary trees, Knuth defines an ordering on the encodings. Right-rotating a tree increases its encoding with respect to the ordering. The relation and the encodings yield a simple non-distributive lattice on binary trees."