伸展树算法分析与设计

《伸展树算法分析与设计》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、伸展树算法分析-彭行雄《计算机算法设计与分析》伸展树算法分析院－系：软件学院专业：软件工程年级：2014级学生姓名：彭行雄学号：20140985导师：肖如良2014年11月I伸展树算法分析-彭行雄目录一、伸展树背景11.查找树的相关问题12.问题引入13.伸展树的产生1二、伸展树的概念21.术语介绍22.伸展树结构23.伸展树的核心思想2三、伸展树的伸展与基本操作31.自底向上伸展32.自顶向上伸展43.自底向上伸展和自顶向下伸展的比较64.自顶向下伸展的核心代码：65.伸展树的基本操作7四、实验设计9五、总结11附录：伸展树实现代码（java）12参考书目221伸展树算法分析-彭行

2、雄一、伸展树背景1.查找树的相关问题各种查找树存在不足。比如：对于一个有n个节点的平衡树，虽然最坏情况下每次查找的时间复杂度不会超过O(logn)，但是如果访问模式不均匀，平衡树的效率就会受到影响。此外，它们还需要额外的空间来存储平衡信息。这些查找树的设计目标都是减少最坏情况下单次操作时间，但是查找树的典型应用经常需要执行一系列的查找操作，此时更关心的性能指标是所有这些操作总共需要多少时间。对于此类应用，更好的目标就是降低操作的摊平时间，此处的摊平时间是指在一系列最坏情况的操作序列中单次操作的平均时间。获得摊平效率的一种方法就是使用“自调整”的数据结构。和平衡的或是其它对结构有明确限

3、制的数据结构比起来，自调整数据结构有以下几个优点：1、从摊平角度而言，它们忽略常量因子，因此绝对不会比有明确限制的数据结构差。而且由于它们可以根据使用情况进行调整，于是在使用模式不均匀的情况下更加有效。2、由于无需存储平衡或者其它的限制信息，它们所需的空间更小。3、查找和更新算法概念简单，易于实现。当然，自调整结构也有潜在的缺点：1、它们需要更多的局部调整，尤其是在查找期间。（那些有明确限制的数据结构仅需在更新期间进行调整，查找期间则不用）2、一系列查找操作中的某一个可能会耗时较长，这在实时应用程序中可能是个不足之处。在讨论AVL树时，主要关注点在于保持树的高度平衡，因此插入和删除都

4、要调整平衡。然而，在实际应用中，我们更关心的是如何快速的搜索以及插入和删除，而不是树的状。根据研究数据表明，大部分对数据的访问都符合二八定律，即80%的访问都集中在20%的数据上。那么在普通二叉树中进行简单的访问，并不能提高效率。因此，对于这个80%的频繁访问，如果第二次访问时间小于第一次访问时间，将会极大提高访问效率。2.问题引入在讨论AVL树时，主要关注点在于保持树的高度平衡，因此插入和删除都要调整平衡。然而，在实际应用中，我们更关心的是如何快速的搜索以及插入和删除，而不是树的形状。根据研究数据表明，大部分对数据的访问都符合90-10规则，即90%的访问都集中在10%的数据上。那

5、么在普通二叉树中进行简单的访问，并不能提高效率。因此，对于这个90%的频繁访问，如果第二次访问时间小于第一次访问时间，将会极大提高访问效率。3.伸展树的产生假设想要对一个二叉查找树执行一系列的查找操作。为了使整个查找时间更小，被查频率高的那些条目就应当经常处于靠近树根的位置。于是想到设计一个简单方法，在每次查找之后对树进行重构，把被查找的条目搬移到离树根近一些的地方。splaytree应运而生。splaytree是一种自调整形式的二叉查找树，它会沿着从某个节点到树根之间的路径，通过一系列的旋转把这个节点搬移到树根去。21伸展树算法分析-彭行雄二、伸展树的概念1.术语介绍1）摊平时间：

6、在一系列最坏情况的操作序列中单次操作的平均时间2）自调整数据结构：根据使用情况进行调整，结点无需存储平衡或其他限制信息3）自底向上的伸展树：使用比简单旋转到根策略稍微复杂一点的方法使项旋转到根而形成的树4）自顶向下的伸展树：在实践中，与自底向上的伸展树相比，自顶向下的伸展树更高效，与红黑树情况一样伸展树是改进的二叉搜索树，是由JohnEdwardHopcroft和RobertEndreTarjan于1985年共同发表的，属于自调整数据结构，可以证明一系列的操作中，每一步“摊平时间”的复杂度都是O(log2n)2.伸展树结构1）伸展树属于二叉查找树，即它具有和二叉查找树一样的性质：假设

7、x为树中的任意一个结点，x节点包含关键字key，节点x的key值记为key[x]。如果y是x的左子树中的一个结点，则key[y]<=key[x]；如果y是x的右子树的一个结点，则key[y]>=key[x]。privateSplayTreeNodemRoot;//根结点publicclassSplayTreeNode>{Tkey;//关键字(键值)SplayTreeNodeleft;//左孩子Spla