对于伸展树（Splay）复杂度的研究与证明.PDF

对于伸展树（Splay ）复杂度的研究与证明 目录 摘要2 关键字2 0 问题提出 2 1 摊还分析 2 1.1 势能法简介 2 1.2 简单实现 3 1.3 二进制计数器例子 3 2 Splay 简介5 2.1 二叉有哪些信誉好的足球投注网站树性质 5 2.2 splay 的实现5 3 splay 复杂度分析 7 3.1 综述 7 3.2 zig （zag ）操作分析7 3.3 zig-zig(zag-zag)操作分析 8 3.4 zig-zag(zag-zig)操作分析 10 3.5 得出结论11 4 实际应用 12 5 附录与鸣谢 13 1 摘要 Splay （伸展树）是一种常用的数据结构。但 Splay 的时间复杂度，在很多人 看来是无需证明的 ，直接背过。可我们可能会加一些不同的操作，又关系到程序 的时间复杂度。本文简介了摊还分析中的势能法，并用其证明了Splay 的复杂度 ， 填充了 Splay 的时间复杂度分析方面的空白；以后也可以用此方法证明其他操作 的时间复杂度。 关键字 Splay 伸展树 摊还分析 势能法 0 问题提出 在信息学奥赛中，Splay 是一种常用的数据结构。然而在各大网站上，关于 Splay 的复杂度的分析都是一笔带过，如 “请读者自行证明”“Tarjan （发明者） 证明了是” …… 但是这激起了我的兴趣。我在网上有哪些信誉好的足球投注网站到证明 Splay 复杂度的 方法都是用累计分析等方法。我突然想到了是否能用刚刚学习的摊还分析势能法 来证明 Splay 的复杂度，于是总结出了这篇文章。 1 摊还分析 1.1 势能法简介 势能法摊还分析将预付代价表示为势能，把势能和整个数据结构关联起来 2 1.2 简单实现 设一个数据结构为 D ，我们要进行n 个操作 ，对于i=0..n ，令c 为第 i 个操 0 i 作的代价，D 为 i 次操作后所得的数据结构。定义一个函数Φ把数据结构 D 映射 i i 到一个实数Φ(D) ，这个值就是D 的势，第 i个操作的摊还代价为 i i ^ ( ) ci = ci + ΦDi − Φ(Di−1) 因此每个操作的摊还代价为他的实际代价加上势能变化。所以n 个操作的摊 还代价为 n n n ^ ( ) ( ) ( ) ∑ ci = ∑ c + ΦD − ΦD = ∑ c + ΦD − Φ(D ) i i i−1 i n 0 i=1 i=1 i=1 ^