University of Oxford Logo University of OxfordDepartment of Computer Science - Home
On Facebook
Facebook
Follow us on twitter
Twitter
Linked in
Linked in
Flickr
Flickr
Google plus
Google plus
Digg
Digg
Pinterest
Pinterest
Stumble Upon
Stumble Upon

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.   

SHARE THIS: