Title
Computer musings: the associative law, or the anatomy of rotations in binary treesCatalog Number
102741371Type
Moving ImageDescription
From 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."