对于Splay和Treap的分析和讨论.doc

《对于Splay和Treap的分析和讨论.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、对于Splay的分析和讨论班级:09级物理学类姓名:曹青学号:2009112045对于Splay的分析和讨论摘要:查找在日常生活和科学研究中占有重要的地位.对于一个已经排序好的(通常为字典序)静态待查集.我们有比较好的算法.可以在log(n)时间内对一个数据项进行查找.但是.对于动态的待查集.这种方式就存在了一定缺陷.因为我们不能保证添加一个数据后,集合中的元素仍然满足一定的序列.有一种解决方式就是每添加一个数据后.我们利用插入排序的方式.始其仍然满足原顺序.但是这种方式过于繁琐.而且效率不高.本文讨论的中心就是利用Spl

2、ay来实现动态的查找操作.关键字:Splay.二叉查找树.动态查找.一些说明:正文部分给出的代码全为伪代码.在文章的附录给出基于visualstudio2008的c++代码.一.引言在实际生活中我们发现.对于动态查找,不能单纯套用静态查找的方式.其关在在于每次要原集合进行排序而维持原集合稳定的这种限制.所以我们需要构造一种新的数据结构.来维持这种插入和删除的稳定性.1.1二叉查找树我们通过构造一颗二叉树来维持这种稳定性.我们规定:1如果该节点的左子树不为空.则左子树的所有节点都小于根节点的值.2如果该节点的右子树不为空.则

3、右子树的所有节点都大于根节点的值.3该节点的左右子树.也是一颗二叉查找树.显然.如果对该树进行中序遍历.则可以得到一个排序好的数组.对于一颗二叉查找树,它可以执行插入.删除和查找的操作.对于这些操作,需要的时间和数高成正比.我们知道.通常的二叉查找树.它的树高都不超过log(n).但是也会出现极端情况.即二叉树变成一个线性表.则树高就变为了n.于是我们知道,如果使一颗树的树高降低.就可以提高工作效率.1.2平衡二叉查找树.有两种典型的平衡二叉查找树:AVL树和红黑树.它们可以保证操作一直满足log(n).但是需要的操作过于

4、复杂.所以我们今天的重点放在了操作简单.还能保证期望为log(n)的查找树.1.3平衡二叉树的旋转操作将一个二叉树进行平衡的基本操作我们称之为旋转.旋转分为左旋和右旋两种.旋转后的二叉查找树仍然保持其原有的状态.即旋转后的二叉查找树仍为二叉查找树.如图给出了二叉树的左右旋示意图.下面给出伪代码.Zig(右旋)原理.把x的右子树取下.再将y插入到x的右子树.再将x的原右子树补到y的左子树上.伪代码如下Leftson(y)=Rightson(x);Rightson(x)=yZag(左旋)原理.把y的左子树取下.再将x插入到y的

5、左子树.再将y的原右子树补到x的左子树上.伪代码如下Rightson(x)=leftson(y)Leftson(y)=x二.Splay(伸展树)伸展树的基本思想是将每次查找到的数据调整到离树根近的位置.这样在多次查找的过程中.就可以提高查找的效率.为了使每次查找到的数据向根转移又不破坏二叉树的平衡性.我们定义伸展操作.(伸展树因此得名)分一共分为三种情况:第一种情况：如果R的父节点Q是树根，则旋转连接R和Q的边。（这种情况是最后一步）。如图：此时我们执行一次右旋操作。或者一次左旋操作。如果R是Q的左孩子。我们执行右旋操作。

6、如果R是Q的右孩子。我们执行左旋操作。第二种情况：如果father(R)不是树根。而father（Q）是树根。并且R和Q同为相应根节点的左儿子或者右儿子。我们进行两次右旋操作或者两次左旋操作。第三种情况：如果father（R）不是树根。并且R和Q不同为相应节点的左儿子或者右儿子。即R为Q的左儿子，而Q为P的右儿子。我们就先进行一次右旋操作。再执行一次左旋操作。反之同理。我们发现，在这个过程中。我们不但把R旋转到了根节点。而且将树高降低。从而使查找效率增加。给出完整的伸展伪代码。我们设x的父亲节点为p（x）。祖父节点为g（x

7、）DO IFX是P(X)的左孩子节点THEN  IFG(X)为空THEN     右旋P(X) ELSEIFP(X)是G(X)的左孩子节点THEN    右旋G(X)    右旋P(X)ELSE   右旋P(X) 左旋P(X)（注意：经过上一次右旋后此处的P(X)和上一个P(X)不一样）ENDIFENDIF    ELSEX是P(X)的右孩子节点THEN  IFG(X)为空THEN     左旋P(X)  ELSEIFP(X)是G(X)的右孩子节点THEN    左旋G(X)    左旋P(X)  ELSE  左旋P(X)

8、    右旋P(X)（注意：经过上一次左旋后此处的P(X)和上一个P(X)不一样）  ENDIF ENDIFWHILEP(X)不为空。可执行的操作：可以执行查找，插入，删除等操作。1查找：从根节点开始进行比较。如果小于则向左走。如果大于则向右走。2插入：通过比较找到相应的位置。插入后进行伸展操作维持伸展