张开树后面的直觉(自平衡树)

Question

我正在阅读张开树的基础知识.n次操作的摊余成本为O(log n).一些粗略的基本思想是当你访问一个节点时,你展开它,即你把它带到root,这样下次快速访问它时,如果节点很深,它会增强树的平衡性.

我不明白树如何为此示例输入执行摊销O(log n):

假设已经构建了n个节点的树.接下来的n个操作是n次读取.我在深度n处访问深度节点.这需要O(n).确实,在访问之后,树将变得平衡.但是每次我访问最新的深度节点时说.这永远不会小于O(log n).那么我们如何能够弥补第一次昂贵的O(n)操作,并将每次读取的摊销成本计算为O(log n)？

谢谢.

Answer 1

假设您的分析是正确的,并且操作是O(log(n))每次访问并且O(n)第一次......

如果你总是访问最底层的元素(使用某种最坏情况的oracle),那么a将进行一系列访问O(a*log(n) + n).因此,每次操作的摊销成本是O((a*log(n) + n)/a)= O(log(n) + n/a)或者O(log(n))随着访问次数的增加而增加.

这是渐近平均情况性能/时间/空间的定义,也称为"摊销性能/时间/空间".您无意中认为O(n)一步意味着所有步骤至少O(n); 从长远来看,这样一个步骤只是一项不变的工作; 该O(...)躲在什么是真正回事,这是采取的限制[total amount of work]/ [queries]= [average ("amortized") work per query].

这永远不会小于O(log n).

它必须是为了获得O(log n)平均表现.为了获得直觉,以下网站可能是好的:http://users.informatik.uni-halle.de/~jopsi/dinf504/chap4.shtml特别是图片http://users.informatik.uni-halle.de/ ~jopsi/dinf504/splay_example.gif - 似乎在执行O(n)操作时,您将搜索到的路径移动到树的顶部.O(n)在整个树平衡之前,您可能只执行有限数量的此类操作.

这是考虑它的另一种方式:

考虑一个不平衡的二叉搜索树.你可以花O(n)时间平衡它.假设您没有向其添加元素*,则O(log(n))每个查询需要按照分摊的时间来获取元素.平衡设置成本包含在摊余成本中,因为它实际上是一个常数,正如答案中的方程式所示,它正在通过您正在进行的无限量工作而消失(相形见绌).(*如果你确实添加了元素,你需要一个自平衡的二叉搜索树,其中一个是一个splay树)