伸展树算法分析与设计.doc
24页
伸展树算法分析-彭行雄《计算机算法设计与分析》 伸展树算法分析院 － 系： 软件学院 专 业： 软件工程 年 级： 2014级 学生姓名： 彭行雄 学 号： 20140985 导 师： 肖如良 2014年11月I目录一、伸展树背景 11.查找树的相关问题 12.问题引入 13.伸展树的产生 1二、伸展树的概念 21.术语介绍 22. 伸展树结构 23. 伸展树的核心思想 2三、伸展树的伸展与基本操作 31. 自底向上伸展 32. 自顶向上伸展 43. 自底向上伸展和自顶向下伸展的比较 64.自顶向下伸展的核心代码： 65.伸展树的基本操作 7四、实验设计 9五、总结 11附录：伸展树实现代码（java） 12参考书目 221一、伸展树背景1.查找树的相关问题各种查找树存在不足。
比如：对于一个有n个节点的平衡树，虽然最坏情况下每次查找的时间复杂度不会超过O(logn)，但是如果访问模式不均匀，平衡树的效率就会受到影响此外，它们还需要额外的空间来存储平衡信息这些查找树的设计目标都是减少最坏情况下单次操作时间，但是查找树的典型应用经常需要执行一系列的查找操作，此时更关心的性能指标是所有这些操作总共需要多少时间对于此类应用，更好的目标就是降低操作的摊平时间，此处的摊平时间是指在一系列最坏情况的操作序列中单次操作的平均时间获得摊平效率的一种方法 就是使用“自调整”的数据结构和平衡的或是其它对结构有明确限制的数据结构比起来，自调整数据结构有以下几个优点：1、从摊平角度而言，它们忽略常量因子，因此绝对不会比有明确限制的数据结构差而且由于它们可以根据使用情况进行调整，于是在使用模式不均匀的情况下更加有效2、由于无需存储平衡或者其它的限制信息，它们所需的空间更小3、查找和更新算法概念简单，易于实现当然，自调整结构也有潜在的缺点：1、它们需要更多的局部调整，尤其是在查找期间那些有明确限制的数据结构仅需在更新期间进行调整，查找期间则不用）2、一系列查找操作中的某一个可能会耗时较长，这在实时应用程序中可能是个不足之处。
在讨论AVL树时，主要关注点在于保持树的高度平衡，因此插入和删除都要调整平衡然而，在实际应用中，我们更关心的是如何快速的搜索以及插入和删除，而不是树的状根据研究数据表明，大部分对数据的访问都符合二八定律，即80%的访问都集中在20%的数据上那么在普通二叉树中进行简单的访问，并不能提高效率因此，对于这个80%的频繁访问，如果第二次访问时间小于第一次访问时间，将会极大提高访问效率2.问题引入在讨论AVL树时，主要关注点在于保持树的高度平衡，因此插入和删除都要调整平衡然而，在实际应用中，我们更关心的是如何快速的搜索以及插入和删除，而不是树的形状根据研究数据表明，大部分对数据的访问都符合90-10规则，即90%的访问都集中在10%的数据上那么在普通二叉树中进行简单的访问，并不能提高效率因此，对于这个90%的频繁访问，如果第二次访问时间小于第一次访问时间，将会极大提高访问效率3.伸展树的产生假设想要对一个二叉查找树执行一系列的查找操作为了使整个查找时间更小，被查频率高的那些条目就应当经常处于靠近树根的位置于是想到设计一个简单方法， 在每次查找之后对树进行重构，把被查找的条目搬移到离树根近一些的地方。
splay tree应运而生splay tree是一种自调整形式的二叉查找树，它会沿着从某个节点到树根之间的路径，通过一系列的旋转把这个节点搬移到树根去二、伸展树的概念1.术语介绍1）摊平时间：在一系列最坏情况的操作序列中单次操作的平均时间2） 自调整数据结构：根据使用情况进行调整，结点无需存储平衡或其他限制信息3） 自底向上的伸展树：使用比简单旋转到根策略稍微复杂一点的方法使项旋转到根而形成的树4） 自顶向下的伸展树：在实践中，与自底向上的伸展树相比，自顶向下的伸展树更高效，与红黑树情况一样 伸展树是改进的二叉搜索树，是由John Edward Hopcroft和Robert Endre Tarjan于1985年共同发表的，属于自调整数据结构，可以证明一系列的操作中，每一步“摊平时间”的复杂度都是O(log2n)2. 伸展树结构1） 伸展树属于二叉查找树，即它具有和二叉查找树一样的性质：假设x为树中的任意一个结点，x节点包含关键字key，节点x的key值记为key[x]如果y是x的左子树中的一个结点，则key[y] <= key[x]；如果y是x的右子树的一个结点，则key[y] >= key[x]。
private SplayTreeNode
旋转方式： 1）单旋转 2）一字双旋转 3）之字双旋转假设当前被访问节点为X，X的父亲节点为Y（如果X的父亲节点存在），X的祖父节点为Z（如果X的祖父节点存在），a、b、c、d分别代表子树1） 单旋转（对于单一形状）节点X的父节点Y是根节点这时，如果X是Y的左孩子，我们进行一次右旋操作；如果X 是Y 的右孩子，则我们进行一次左旋操作经过旋转，X成为二叉查找树T的根节点，调整结束如图1所示图1 自底向上的单旋转2） 一字双旋转（对于同构形状）节点X 的父节点Y不是根节点，Y 的父节点为Z，且X与Y同时是各自父节点的左孩子或者同时是各自父节点的右孩子这时，我们进行一次左左旋转操作或者右右旋转操作如图2所示图2 自底向上的一字双旋转3） 之字双旋转（对于异构形状）节点X的父节点Y不是根节点，Y的父节点为Z，X与Y中一个是其父节点的左孩子而另一个是其父节点的右孩子这时，我们进行一次左右旋转操作或者右左旋转操作如图3所示图3 自底向上的之字双旋转算法描述：splaying(g,p,s){//g是p的父结点，p是s的父结点，算法将s移动到根结点位置 while(s不是树的根结点) if(s与前驱p是单一形状) 进行单旋转，将s调整为根结点 else if(s与它的前驱p,g是同构形状) 进行一字旋转，将s上移 else//s与它的前驱p,g是异构形状 进行之字双旋转，将s上移}2. 自顶向上伸展将伸展树分为三部分： 左树：包含所有已经知道比待查节点 X小的节点。
右树：包含所有已经知道比待查节点 X大的节点 中树：包含所有其它节点 在中树自根向下进行节点查找，根据查找情况将中树中的节点移动到左树或右树初始状态时，左树和右树都为空，而中树为整个原伸展树随着查找的进行，左树和右 树会因节点的逐渐移入变大，中树会因节点的逐渐移出变小最后查找结束（找到或遇到空 节点）时组合左中右树并是伸展树自顶向下伸展方法的最终结果 1） 孩子即为要查找的点,只需要一次连接操作即可如图4所示图4 自顶向下的单一旋转2） 孙子为要查找的点,且左右孩子一致.需要首先旋转父亲和祖父节点,然后连接操作如图5所示图5 自顶向下的一字型旋转3） 孙子为要查找的点,且左右孩子不一致.需要两次连接操作如图6所示图6自顶向下的之字型旋转4） 合并如图7所示图7 自顶向下的合并操作算法描述：splay(T,key){//g是p的父结点，p是s的父结点，算法将s移动到根结点位置 while(s不是树的根结点) if(s与前驱p是单一形状) 进行一次旋转，将s调整为根结点 else if(s与它的前驱p,g是同构形状) 进行一次旋转和一次分解，将s调整为根结点 else//s与它的前驱p,g是异构形状 进行两次分解，将s调整为根结点}3. 自底向上伸展和自顶向下伸展的比较不同点： 自顶向下的实现方式比较简单，因为自底向上需要保存已经被访问的节点，而自顶向下可以在搜索的过程中同时完成splay操作。
两者得出的树结构可能不太一样相同点： 他们的平摊时间复杂度都是O(logn)两种实现的基本操作就是伸展(splay)，而且都可以理解为旋转splay将最后被访问到的节点提升为根节点因此在这里我们采用自顶向下的伸展方式4.自顶向下伸展的核心代码 for (;;) { int cmp = pareTo(tree.key); if (cmp < 0) {//要找的结点不是根结点 if (tree.left == null) break; if (pareTo(tree.left.key) < 0) {//左同构，右旋转 c = tree.left; tree.left = c.right; c.right = tree; tree = c; 。
