对于Splay及Treap的分析及讨论.docVIP

对于Splay的分析和讨论 班级:09级物理学类 姓名:曹青 学号:2009112045 对于Splay的分析和讨论 摘 要:查找在日常生活和科学研究中占有重要的地位.对于一个已经排序好的(通常为字典序)静态待查集.我们有比较好的算法.可以在log(n)时间内对一个数据项进行查找.但是.对于动态的待查集.这种方式就存在了一定缺陷.因为我们不能保证添加一个数据后,集合中的元素仍然满足一定的序列.有一种解决方式就是每添加一个数据后.我们利用插入排序的方式.始其仍然满足原顺序.但是这种方式过于繁琐.而且效率不高.本文讨论的中心就是利用Splay来实现动态的查找操作. 关键字: Splay.二叉查找树.动态查找. 一些说明:正文部分给出的代码全为伪代码.在文章的附录给出基于visual studio 2008的c++代码. 一.引言 在实际生活中我们发现.对于动态查找,不能单纯套用静态查找的方式.其关在在于每次要原集合进行排序而维持原集合稳定的这种限制.所以我们需要构造一种新的数据结构.来维持这种插入和删除的稳定性. 1.1二叉查找树 我们通过构造一颗二叉树来维持这种稳定性.我们规定:1如果该节点的左子树不为空.则左子树的所有节点都小于根节点的值.2如果该节点的右子树不为空.则右子树的所有节点都大于根节点的值.3该节点的左右子树.也是一颗二叉查找树.显然.如果对该树进行中序遍历.则可以得到一个排序好的数组.对于一颗二叉查找树,它可以执行插入.删除和查找的操作.对于这些操作,需要的时间和数高成正比.我们知道.通常的二叉查找树.它的树高都不超过log(n).但是也会出现极端情况.即二叉树变成一个线性表.则树高就变为了n.于是我们知道,如果使一颗树的树高降低.就可以提高工作效率. 1.2平衡二叉查找树. 有两种典型的平衡二叉查找树:AVL树和红黑树.它们可以保证操作一直满足log(n).但是需要的操作过于复杂.所以我们今天的重点放在了操作简单.还能保证期望为log(n)的查找树. 1.3平衡二叉树的旋转操作 将一个二叉树进行平衡的基本操作我们称之为旋转.旋转分为左旋和右旋两种.旋转后的二叉查找树仍然保持其原有的状态.即旋转后的二叉查找树仍为二叉查找树 . 如图给出了二叉树的左右旋示意图.下面给出伪代码. Zig(右旋) 原理.把x的右子树取下.再将y插入到x的右子树.再将x的原右子树补到y的左子树上.伪代码如下 Leftson(y)=Rightson(x); Rightson(x)=y Zag(左旋) 原理.把y的左子树取下.再将x插入到y的左子树.再将y的原右子树补到x的左子树上.伪代码如下 Rightson(x)=leftson(y) Leftson(y)=x 二.Splay(伸展树) 伸展树的基本思想是将每次查找到的数据调整到离树根近的位置.这样在多次查找的过程中.就可以提高查找的效率. 为了使每次查找到的数据向根转移又不破坏二叉树的平衡性.我们定义伸展操作.(伸展树因此得名) 分一共分为三种情况: 第一种情况：如果的父节点是树根，则旋转连接和的边。（这种情况是最后一步） 此时我们执行一次右旋操作。或者一次左旋操作。如果R是Q的左孩子。我们执行右旋操作。如果R是Q的右孩子。我们执行左旋操作。 第二种情况：如果father(R)不是树根。而father（Q）是树根。并且R和Q同为相应根节点的左儿子或者右儿子。我们进行两次右旋操作或者两次左旋操作。 第三种情况：如果father（R）不是树根。并且R和Q不同为相应节点的左儿子或者右儿子。即R为Q的左儿子，而Q为P的右儿子。我们就先进行一次右旋操作。再执行一次左旋操作。反之同理。 我们发现，在这个过程中。我们不但把R旋转到了根节点。而且将树高降低。从而使查找效率增加。给出完整的伸展伪代码。 我们设x的父亲节点为p（x）。祖父节点为g（x） DO ? IF X 是 P(X)的左孩子节点 THEN ??IF G(X)为空 THEN? ???? 右旋 P(X) ? ELSE IF P(X)是 G(X)的左孩子节点 THEN ???? 右旋 G(X) ???? 右旋 P(X) ELSE ??? 右旋 P(X) ?左旋 P(X)（注意：经过上一次右旋后此处的 P(X)和上一个 P(X)不一样）  ENDIF??? ? ELSE X