伸展树（自平衡树）背后的直觉
我正在阅读八字树的基础知识。在 n 次操作中，一次操作的摊余成本为 O(log n)。一些粗略的基本思想是，当您访问一个节点时，您将其展开，即您将其置于根节点，因此下次可以快速访问该节点，并且如果该节点很深，则可以增强树的平衡性。
我不明白树如何为此示例输入执行摊销 O(log n)：
假设已经构建了 n 个节点的树。我接下来的 n 次操作是 n 次读取。我访问深度为 n 的深度节点。这需要 O(n)。确实，在这次访问之后，树将变得平衡。但是说每次我访问最新的深层节点时。这永远不会小于 O(log n)。那么我们如何才能补偿第一个昂贵的 O(n) 操作并将每次读取的摊余成本变为 O(log n) 呢？
谢谢。
I am reading the basics of splay trees. The amortized cost of an operation is O(log n) over n operations. Some rough basic idea is that when you access a node, you splay it i.e. you take it to root so next time this is quickly accessed and also if the node was deep, it enhances balance-ness of tree.
I don't understand how the tree can perform amortized O(log n) for this sample input:
Say a tree of n nodes is already built. My next n operations are n reads. I access a deep node say at depth n. This takes O(n). True that after this access, the tree will become balanced. But say every time I access the most current deep node. This will never be less than O(log n). then how we can ever compensate for the first costly O(n) operation and bring the amortized cost of each read as O(log n)?
Thanks.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
假设您的分析是正确的，并且每次访问的操作都是
O(log(n))，第一次的操作是O(n)...如果您总是访问最底部的元素（使用某种最坏情况的预言），
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(...)隐藏了真正发生的事情，它受到[工作总量]/[查询]=[每个查询的平均（“摊销”）工作量]。它必须是为了获得
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))摊销时间来获取元素。平衡设置成本包含在摊余成本中，因为它实际上是一个常数，如答案中的方程所示，它会因您正在做的无限量工作而消失（相形见绌）。 （*如果确实向其中添加元素，则需要一棵自平衡二叉搜索树，其中之一是展开树）Assuming your analysis is correct and the operations are
O(log(n))per access andO(n)the first time...If you always access the bottommost element (using some kind of worst-case oracle), a sequence of
aaccesses will takeO(a*log(n) + n). And thus the amortized cost per operation isO((a*log(n) + n)/a)=O(log(n) + n/a)or justO(log(n))as the number of accesses grows large.This is the definition of asymptotic average-case performance/time/space, also called "amortized performance/time/space". You are accidentally thinking that a single
O(n)step means all steps are at leastO(n); one such step is only a constant amount of work in the long run; theO(...)is hiding what's really going on, which is taking the limit of[total amount of work]/[queries]=[average ("amortized") work per query].It has to be in order to get
O(log n)average performance. To get intuition, the following website may be good: http://users.informatik.uni-halle.de/~jopsi/dinf504/chap4.shtml specifically the image http://users.informatik.uni-halle.de/~jopsi/dinf504/splay_example.gif -- it seems that while performing theO(n)operations, you move the path you searched scrunching it towards the top of the tree. You probably only have a finite number of suchO(n)operations to perform until the entire tree is balanced.Here's another way to think about it:
Consider an unbalanced binary search tree. You can spend
O(n)time balancing it. Assuming you don't add elements to it*, it takesO(log(n))amortized time per query to fetch an element. The balancing setup cost is included in the amortized cost because it is effectively a constant which, as demonstrated in the equations in the answer, disappears (is dwarfed) by the infinite amount of work you are doing. (*if you do add elements to it, you need a self-balancing binary search tree, one of which is a splay tree)