Artifact Details

Title

Computer musings: the associative law, or the anatomy of rotations in binary trees

Catalog Number

102741371

Type

Moving Image

Date

1993-11

Credits

Knuth, Donald E.

Publisher

University Video Communications

Duration

00:72:04

Format

Betacam SP

Copyright Holder

Computer History Museum

Description

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."

Category

Lecture

Series Title

University Video Communications: Distinguished Lectures

Credit

Gift of University Video Communications

Lot Number

X6636.2013