2012年4月6日至16日，图灵奖得主、美国科学院院士、美国工程院院士、美国人文科学院院士、美国普林斯顿大学Robert Tarjan教授访问清华大学交叉信息院。来访期间，Tarjan教授应邀做客“清华海外名师讲堂”第119讲，于4月12日在信息技术大楼（FIT楼）多功能厅主讲题为“搜索树之谜（Search Tree Mysteries）”的特邀报告，并与交叉信息院姚班学生及研究生面对面交流。 

Robert Tarjan教授主讲清华海外名师讲堂

Robert Tarjan教授是世界知名计算机学家，因LCA、强连通分量等算法而闻名，研究领域主要包括图论，算法和数据结构设计。1986年Robert Tarjan教授与John Hopcroft因为在算法及数据结构的设计和分析中所取得的决定性成果而荣获图灵奖，提出了数据结构中著名的B树。Robert Tarjan教授是许多图论算法的发明者，比如著名的Tarjan's off-line least common ancestors algorithm；他于1982年获得首届奈望林纳奖，现为美国科学院院士、美国工程院院士、美国人文科学院院士、美国计算机协会（ACM）会士、美国哲学学会会士。

姚期智教授主持讲座

Robert Tarjan教授关于搜索树的特邀讲座吸引了众多同学参加。搜索树是古典数据结构，对于数据库和许多其他计算机应用而言至关重要。Robert Tarjan教授介绍了平衡二叉树（AVL树）的发展历史，带领同学们一同探索其中蕴含的巨大设计空间和奥秘。Tarjan教授还论述自己最近的工作，描述了一种定义和分析平衡搜索树的新框架，一种具备特优性能的新型平衡树，以及一种通过插入而非删除方式来维护平衡的方式。

姚期智教授向Robert Tarjan教授赠纪念牌

讲座结束后，Robert Tarjan教授与师生开展互动，深入探讨搜索模型、二叉查找树的懒惰删除（lazy deletion）等问题。姚期智教授还为Robert Tarjan教授颁发“清华大学海外名师讲堂第119讲”纪念牌。

讲座现场互动

包括交叉信息院教师、姚班学生、研究生在内的近200人参加了今天的讲座。