论文标题
张开的顶部树木
Splay Top Trees
论文作者
论文摘要
顶部的树数据结构是动态图算法中重要且基本的工具。顶级树已经存在数十年了，如今，在许多最先进的动态图算法中充当了成分。在这项工作中，我们根据张开树的想法提供了新的直接证据，证明了顶部树的存在，从而促进了顶部树的更简单，更直接的实现。该结果取决于新的见解，尤其是顶部树中每个根路径的结构。
The top tree data structure is an important and fundamental tool in dynamic graph algorithms. Top trees have existed for decades, and today serve as an ingredient in many state-of-the-art algorithms for dynamic graphs. In this work, we give a new direct proof of the existence of top trees, facilitating simpler and more direct implementations of top trees, based on ideas from splay trees. This result hinges on new insights into the structure of top trees, and in particular the structure of each root path in a top tree.
