学术活动发布与订制系统

About the Speaker: 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.

Robert Tarjan教授，著名计算机科学家，以LCA，强连通分量等算法闻名。研究领域主要包括图论，算法和数据结构设计。1986年因其和John Hopcroft在算法及数据结构的设计和分析中所取得的决定性成果而获图灵奖。数据结构中学到的B树就是他们提出的。其还是许多图论算法的发明者，比如Tarjan’s off-line least common ancestors algorithm。

Lecture 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.

搜索树是一个古典的，且无处不在的数据结构，也是数据库和许多其他计算机应用的基本所在。 AVL树是一种平衡二叉搜索树类型，发明于五十年前。从那时起，就开始描述，分析和使用许多不同种类的搜索树。但是，设计空间是巨大的，因此奥秘也就仍然存在。本讲座将介绍作者和其同事最近的工作成果，即发明出一种新的定义和分析平衡搜索树的框架，一种具有优良性质的新型平衡树，以及一种通过插入而不是删除来重新取得和保持平衡的方法。