论文标题
两个树的故事：AVL树和二进制堆的新分析
A Tale of Two Trees: New Analysis for AVL Tree and Binary Heap
论文作者
论文摘要
在本文中，我们为两个基于树的数据结构-AVL树和二进制堆提供了新的见解和分析。我们提出了两个简单的属性，这些属性提供了一种更直接的方法，可以将AVL树的大小和斐波那契复发的大小建立，以建立AVL树的对数高度。然后，我们对自下而上的堆结构进行了潜在的基于功能的分析，以使其最差的运行时间更简单，紧密。
In this paper, we provide new insights and analysis for the two elementary tree-based data structures - the AVL tree and binary heap. We presented two simple properties that gives a more direct way of relating the size of an AVL tree and the Fibonacci recurrence to establish the AVL tree's logarithmic height. We then give a potential function-based analysis of the bottom-up heap construction to get a simpler and tight bound for its worst-case running-time.
