Sideways Heaps: The Thirteenth Annual Christmas Tree Lecture December 3, 2007

Don Knuth's Computer Musings
Sideways Heaps: The Thirteenth Annual Christmas Tree Lecture

Professor Knuth will discuss an interesting infinite binary tree that has no root, and its applications to implicit data structures. In particular, he'll explain the amazing Schieber--Vishkin algorithm for nearest common ancestors.

Official Website: http://www-cs-staff.stanford.edu/~knuth/musings.html