简介: |
Short Bio:
Robert E. Tarjan is the James S. McDonnell Distinguished University Professor of Computer Science at Princeton University and a Senior Fellow at HP labs. His main research areas are the design and analysis of data structures and graph and network algorithms. He has also done work in computational complexity and security. He has held positions at Cornell University, U. C. Berkeley, Stanford University, NYU, Bell Laboratories, NEC, and InterTrust Technologies. He is a member of the National Academy of Sciences, the National Academy of Engineering, the American Philosophical Society, and the American Academy of Arts and Sciences. He was awarded the Nevanlinna Prize in Informatics in 1982 and the Turing Award in 1986.
Abstract:
The search tree is a classical and ubiquitous data structure, fundamental to databases and many other computer applications. 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, and 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. |
