习题[8-1]~[8-2] 第8章 高级搜索树
[8-1] 试扩充 Splay 模板类（教材 208 页代码 8.1），使乊支持多个相等数据顷癿幵存。
为此，需要增加 searchAll(e)和 removeAll(e)接口，以查找戒初除等二指定目标 e 癿所有节点。
同时，原先癿 search(e)和 remove(e)接口，将转而负责查找戒初除等二指定目标 e 癿仸一节点。
【解答】
原理及方法，均与习题[7-10]（149页）和习题[7-16]（152页）完全相同。
请读者独立完成编码和调试任务。
[8-2] 试证明，伸展树所有基本操作接口癿分摊时间复杂度，均为 O(logn)。
【解答】
关于伸展树可在任意情况下均保持良好的操作效率，教材208页图8.7的实例还不足以作为
严格的证明。事实上，伸展树单次操作所需的时间量T起伏极大，并不能始终保证控制在O(logn)
以内。故需沿用教材2.4.4节的方法，从分摊的角度做一分析和评判。具体地，可将实际可能连
续发生的一系列操作视作一个整体过程，将总体所需计算时间分摊至其间的每一操作，如此即可
得到其单次操作的分摊复杂度A，并依此评判伸展树的整体性能。
当然，就具体的某次操作而言，实际执行时间T与分摊执行时间A往往并不一致，如何弥合
二者之间的差异呢？
实际上，分摊分析法在教材中已经而且将会多次出现，比如此前第2.4.4节的可扩充向量、
第5.4节的各种迭代式遍历算法以及后面第11.3.7节的KMP串匹配算法等。相对而言，伸展树的
性能分析更为复杂，以下将采用势能分析法（potential analysis）。
仿照物理学的思想和概念，这里可假想式地认为，每棵伸展树S都具有一定量（非负）的势
能（potential），记作(S)。于是，若经过某一操作并相应地通过旋转完成伸展之后S演化为
另一伸展树S'，则对应的势能变化为：
= (S') - (S)
推而广之，考查对某伸展树S
0
连续实施m >> n次操作的过程。将第i次操作后的伸展树记作
S
i
，则有：
i
= (S
i
) - (S
i-1
), 1 i m
而从该过程的整体来看，应有
=
i=1
m
[(S
i
) - (S
i-1
)] = (S
m
) - (S
0
)
也就是说，整体的势能变化量仅取决于最初和最终状态这与物理学中势能场的规律吻
合。势能函数与物理学中势能的另一相似之处在于，它也可以被看作是能量（计算成本）的一种
存在形式。比如，当某一步计算实际所需的时间小于分摊复杂度时，则可理解为通过势能的增加
评论0