给它一个图形和一棵生成树，一个transmuter是一个从它衍生出来的辅助图形，可以加速原始图形上的某些操作。它是由Tarjan发明的：为给定的图形及其生成树构建一个transmuter
Robert E. Tarjan. Applications of Path Compression on Balanced Trees. Journal of the ACM, 26(4):690–715, 1979.
Robert E. Tarjan. Sensitivity Analysis of Minimum Spanning Trees and Shortest Path Trees. Information Processing Letters, 14(1):30–33, 1982.
我发现自己需要一个transmuter。不幸的是，我无法访问这两个文件。有人可以知道transmuter和/或有权访问这些文件详细介绍transmuter和构建它的算法吗？
http://www.cs.princeton.edu/courses/archive/fall03/cs528/handouts/applications%20of%20path%20compression.pdf从http://scholar.google.com/scholar?q=%22Applications+of+Path+Compression+on+Balanced+Trees.%22从http://www.informatik.uni-trier.de/~ley/db/journals/jacm/jacm26.html#Tarjan79
不幸http://scholar.google.com/scholar?q=%22Sensitivity+Analysis+of+Minimum+Spanning+Trees+and+Shortest+Path+Trees.%22没有PDF链接。如果有其他文件可能有所帮助，请参阅http://www.informatik.uni-trier.de/~ley/db/indices/a-tree/t/Tarjan:Robert_Endre.html。
谢谢安德鲁。这可能是迄今为止我能得到的最好结果。如果没有人能够给出算法本身的解释，我会等待一会儿再接受你的答案。 – edwardw
你想要这些文件还是只讨论如何构建一个图并在其上运行最小生成树？你也想要关于压缩的二叉搜索树的信息吗？ B-Trees可能是你正在寻找的东西（http://en.wikipedia.org/wiki/B-tree）。 –
文件将做。但是不，我对构建一个图形和一棵生成树不感兴趣。我想知道如何构建一个transmuter，这也是一个图表。我编辑了这个问题来阐明我的意图。 – edwardw
以下是有点误导。我没有编辑权限。 “有人可以知道数据结构和/或有权访问这些文件，详细阐述一下关于transmuter和构建它的算法吗？”。此外，ACM文章不是免费的，我认为免费发行它们打破了版权法？ –