罗伯特·塔扬

罗伯特·塔扬（Robert Endre Tarjan，亦译塔尔扬）是以图算法和数据结构分析著称的计算机科学家。他在加州理工学院学习数学，在斯坦福大学取得计算机科学硕士与博士学位，曾在多所大学和贝尔实验室等研究机构工作，并获图灵奖等荣誉。

其研究的特点不只是提出操作步骤，还在于证明这些步骤的正确性和时间界限。同一项工作中，数据结构、更新规则与复杂度证明各有来历；不能因为某项界限以他的名字著称，就把早先已有的全部机制都归为他的发明。

参考：[1] [3]

1972年的论文系统展示了深度优先搜索在图算法中的作用。对于有向图，强连通分量是内部任意两点都能沿有向路径互相到达的最大顶点集合。算法在搜索时给顶点编号，把已经发现、尚未归入分量的顶点压入栈中。

LOWLINK记录与当前搜索子树相关的较早可达编号；遇到仍在栈中的顶点时，相关边才参与这种回溯更新。当一个顶点的LOWLINK等于自身编号，就找到了一个分量的根，可以把栈顶直到该顶点的一段取出。采用邻接表和常数时间的在栈标记，总时间为O(V+E)。关键是把搜索顺序、栈与可达性联系起来，而非逐对检查所有顶点。

参考：[2]

1975年的论文分析了一种已有的集合合并算法。集合以树表示，查找沿父指针找到根；路径压缩让沿途顶点直接指向根，加权合并则把较小集合挂到较大集合下面。两种规则配合，使后续查找通常经过更短的路径。

塔扬证明，一长串查找与合并的总成本由一个与阿克曼函数反函数有关、增长极慢的因子控制。这是对操作序列的摊还分析，不是承诺每一次查找都具有相同的常数上界。论文明确追溯树表示、压缩和加权规则的前人工作，突出其贡献在于给出更紧的数学分析，而不是从零发明所有并查集操作。

参考：[3]

丹尼尔·斯莱特与塔扬在1985年共同发表伸展树研究。伸展树是二叉搜索树：访问节点后，依据节点、父节点和祖父节点的位置进行成对旋转，把它移到根部，同时保持键的排序关系。它无需像严格平衡树那样始终保存固定的平衡形状。

对含n个节点的树，标准操作具有O(log n)的摊还时间界限，意指最坏操作序列上的平均成本；某次操作仍可能很昂贵，因而不能把这一结论当作实时延迟保证。并查集与伸展树共同说明，数据结构的效率有时来自操作对未来状态的改善，而不是每一步都立即便宜。伸展树成果应归于两位合作者。

参考：[4]