Posted: 27th October 2011

Mysteries of Search Trees by Robert E. Tarjan, Princeton University and HP Labs

 On Thursday 8^th 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.