Strachey Lecture: Mysteries of Search Trees by Professor Robert E. Tarjan
Posted: 27th October 2011
Mysteries of Search Trees by Robert E. Tarjan, Princeton University and HP Labs
On Thursday 8th December at 4:30 p.m
Lecture Theatre B, E-Science Building, 7 Keble Road, Oxford.
The search tree is a classical and ubiquitous data structure. The AVL tree, a type of balanced binary tree, was invented fifty years ago; since then, many different kinds of search trees have been described, analyzed, and used. Yet the design space is vast, mysteries remain. This talk will describe recent work by the speaker and his colleagues that has produced a new framework for defining and analyzing balanced search trees, a new kind of balanced tree with especially nice properties, and a way to maintain balance by rebalancing only on insertion, not on deletion.