伸展树算法分析与设计.doc

伸展树算法分析-彭行雄计算机算法设计与分析 伸展树算法分析院 系： 软件学院 专 业： 软件工程 年 级： 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值记为keyx。如果y是x的左子树中的一个结点，则keyy = keyx。 private SplayTreeNode mRoot; / 根结点 public class SplayTreeNodeT extends Comparable T key; / 关键字(键值) SplayTreeNode left; / 左孩子 SplayTreeNode right; / 右孩子2） 除了拥有二叉查找树的性质之外，伸展树还具有的一个特点是：当某个节点被访问时，伸展树会通过旋转使该节点成为树根。这样做的好处是，下次要访问该节点时，能够迅速的访问到该节点。3） 假设想要对一个二叉查找树执行一系列的查找操作。为了使整个查找时间更小，被查频率高的那些条目就应当经常处于靠近树根的位置。于是想到设计一个简单方法，在每次查找之后对树进行重构，把被查找的条目搬移到离树根近一些的地方。伸展树应运而生，它是一种自调整形式的二叉查找树，它会沿着从某个节点到树根之间的路径，通过一系列的旋转把这个节点搬移到树根去。3. 伸展树的核心思想1） 单一旋转：只要访问子女结点，就将它围绕着它的父结点旋转，上移到靠近根的位置2） 移动到根部：假设正在访问的结点以很高的概率再次被访问，就对它反复进行子女-父结点旋转，直到被访问的结点位于根部为止三、伸展树的伸展与基本操作每次操作一个结点时，伸展树就执行一次“伸展(splaying)”1. 自底向上伸展找到子女结点，然后把它向上旋转到根结点位置。旋转方式：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) /要找的结点不是根结点 if (tree.right = null) break; if (pareTo(tree.right.key) 0) /同构，左旋转 c = tree.right; tree.right = c.left; c.left = tree; tree = c; if (tree.right = null) /子结点以下，没有新的右子结点 break; /左连接 leftTreeMax.right = tree; leftTreeMax = tree; tree = tree.right;/继续深入右子树查找 else /要找的是根结点 break; /左树和右树合并 leftTreeMax.right = tree.left; rightTreeMin.left = tree.right; tree.left = N.right; tree.right = N.left; return tree;5.伸展树的基本操作1）插入： 当一个节点插入时，伸展操作将执行。因此，新插入的节点在根上。2）查找： 如果查找成功（找到），那么由于伸展操作，被查找的节点成为树的新根。如果查找失败（没有），那么在查找遇到NULL之前的那个节点成为新的根。也就是，如果查找的节点在树中，那么，此时根上的节点就是距离这个节点最近的节点。3）查找最大最小： 查找之后执行伸展。4）删除最大最小：A、删除最小： 首先执行查找最小的操作。这时，要删除的节点就在根上。根据二叉查找树的特点，根没有左子节点。使用根的右子结点作为新的根，删除旧的包含最小值的根。B)删除最大：首先执行查找最大的操作。删除根，并把被删除的根的左子结点作为新的根。5）删除： 将要删除的节点移至根。 删除根，剩下两个子树L（左子树）和R（右子树）。 使用DeleteMax查找L的最大节点，此时，L的根没有右子树。 使R成为L的根的右子树。四、实验设计1. 实验目的：利用java实现伸展树的伸展过程以及实现查找、插入、删除等功能2. 实验环境： WinXP32位操作系统，Eclipse 编程语言：java3. 实验步骤： a.新建伸展树 b.向伸展树中依次插入10,50,40,30,20 c.旋转节点，使得30成为根节点 d.利用先序遍历的方法打印出树的结构4. 结果预测：如图8所示图8 手动进行伸展操作的预测结果5.实验结果：如图9所示图9 伸展树算法实验结果6.结果分析：上图展示了插入10,50,40,30,20,之后树的详细信息和旋转结点30为根结点后的树情况。发现与手动操作结果一致。五、总结通过实验的证明，发现伸展树不像红黑树那么复杂。伸展算法的核心在于处理好旋转、连接之间的先后关系，而其他的操作和普通二叉树是一样的。在实际中，我们手动的实现解题的过程方便快捷，但是变成计算机算法时，就必须在时间复杂度与空间复杂度之间找到一个平衡。比如伸展树中的自底向上伸展和自顶向下伸展，虽然自底向上伸展在手动模式下更为简单一些。但是，在计算机中实现时，却不得不为其创建空间来保存已经访问过的结点，并且存在大量重复操作。因此我们才去考虑实现自顶向下伸展的算法。那么问题在于什么时候使用伸展树合适？使用伸展树值得吗？通过查阅资料，发现到目前还没有确切答案，但如果是非随机访问，并遵从类似八二定律，那么在实践中伸展树性能会比其他二叉树更好。而且伸展树并不完美。其中一个问题就在于，因为伸展，造成查找，插入与删除等操作都要进行伸展，代价比较大。因此，当访问序列式随机的、均匀分布的，伸展树的性能不如其他二叉平衡树好。附录：伸展树实现代码（java）1.SplayTree.java文件package pag;/* * Java 语言: 伸展树 * * author pengxingxiong * date 2014/11/01 */public class SplayTreeT extends Comparable private SplayTreeNode mRoot; / 根结点 public class SplayTreeNodeT extends Comparable T key; / 关键字(键值) SplayTreeNode left; / 左孩子 SplayTreeNode right; / 右孩子 /根结点构造函数 public SplayTreeNode() this.left = null; this.right = null; /子女结点构造函数 public SplayTreeNode(T key, SplayTreeNode left, SplayTreeNode right) this.key = key; this.left = left; this.right = right; public SplayTree() mRoot=null; /* * 前序遍历伸展树 */ private void preOrder(SplayTreeNode tree) if(tree != null) System.out.print(tree.key+ ); preOrder(tree.left); preOrder(tree.right); public void preOrder() preOrder(mRoot); /* * 中序遍历伸展树 */ private void inOrder(SplayTreeNode tree) if(tree != null) inOrder(tree.left); System.out.print(tree.key+ ); inOrder(tree.right); public void inOrder() inOrder(mRoot); /* * 后序遍历伸展树 */ private void postOrder(SplayTreeNode tree) if(tree != null) postOrder(tree.left); postOrder(tree.right); System.out.print(tree.key+ ); public void postOrder() postOrder(mRoot); /* * (递归实现)查找伸展树x中键值为key的节点 */ private SplayTreeNode search(SplayTreeNode x, T key) if (x=null) return x; int cmp = pareTo(x.key); if (cmp 0) return search(x.right, key); else return x; public SplayTreeNode search(T key) return search(mRoot, key); /* * (非递归实现)查找伸展树x中键值为key的节点 */ private SplayTreeNode iterativeSearch(SplayTreeNode x, T key) while (x!=null) int cmp = pareTo(x.key); if (cmp 0) x = x.right; else return x; return x; public SplayTreeNode iterativeSearch(T key) return iterativeSearch(mRoot, key); /* * 查找最小结点：返回tree为根结点的伸展树的最小结点。 */ private SplayTreeNode minimum(SplayTreeNode tree) if (tree = null) return null; while(tree.left != null) tree = tree.left; return tree; public T minimum() SplayTreeNode p = minimum(mRoot); if (p != null) return p.key; return null; /* * 查找最大结点：返回tree为根结点的伸展树的最大结点。 */ private SplayTreeNode maximum(SplayTreeNode tree) if (tree = null) return null; while(tree.right != null) tree = tree.right; return tree; public T maximum() SplayTreeNode p = maximum(mRoot); if (p != null) return p.key; return null; /* * 旋转key对应的节点为根节点，并返回根节点。 * * 注意： * (a)：伸展树中存在键值为key的节点。 * 将键值为key的节点旋转为根节点。 * (b)：伸展树中不存在键值为key的节点，并且key tree.key。 * c-1 键值为key的节点的后继节点存在的话，将键值为key的节点的后继节点旋转为根节点。 * c-2 键值为key的节点的后继节点不存在的话，则意味着，key比树中任何键值都大，那么此时，将最大节点旋转为根节点。 */ private SplayTreeNode splay(SplayTreeNode tree, T key) if (tree = null) return tree; SplayTreeNode N = new SplayTreeNode(); SplayTreeNode leftTreeMax = N; SplayTreeNode rightTreeMin = N; SplayTreeNode c; for (;) int cmp = pareTo(tree.key); if (cmp 0) /要找的结点不是根结点 if (tree.left = null) break; if (pareTo(tree.left.key) 0) /要找的结点不是根结点 if (tree.right = null) break; if (pareTo(tree.right.key) 0) /同构，左旋转 c = tree.right; tree.right = c.left; c.left = tree; tree = c; if (tree.right = null) /子结点以下，没有新的右子结点 break; /左连接 leftTreeMax.right = tree; leftTreeMax = tree; tree = tree.right;/继续深入右子树查找 else /要找的是根结点 break; /左树和右树合并 leftTreeMax.right = tree.left; rightTreeMin.left = tree.right; tree.left = N.right; tree.right = N.left; return tree; public void splay(T key) mRoot = splay(mRoot, key); /* * 将结点插入到伸展树中，并返回根节点 * * 参数说明： * tree 伸展树的 * z 插入的结点 */ private SplayTreeNode insert(SplayTreeNode tree, SplayTreeNode z) int cmp; SplayTreeNode y = null; SplayTreeNode x = tree; / 查找z的插入位置 while (x != null) y = x; cmp = pareTo(x.key); if (cmp 0) x = x.right; else System.out.printf(不允许插入相同节点(%d)!n, z.key); z=null; return tree; if (y=null) tree = z; else cmp = pareTo(y.key); if (cmp 0) y.left = z; else y.right = z; return tree; public void insert(T key) SplayTreeNode z=new SplayTreeNode(key,null,null); / 如果新建结点失败，则返回。 if (z=new SplayTreeNode(key,null,null) = null) return ; / 插入节点 mRoot = insert(mRoot, z); / 将节点(key)旋转为根节点 mRoot = splay(mRoot, key); /* * 删除结点(z)，并返回被删除的结点 * * 参数说明： * bst 伸展树 * z 删除的结点 */ private SplayTreeNode remove(SplayTreeNode tree, T key) SplayTreeNode x; if (tree = null) return null; / 查找键值为key的节点，找不到的话直接返回。 if (search(tree, key) = null) return tree; / 将key对应的节点旋转为根节点。 tree = splay(tree, key); if (tree.left != null) / 将tree的前驱节点旋转为根节点 x = splay(tree.left, key); / 移除tree节点 x.right = tree.right; else x = tree.right; tree = null; return x; public void remove(T key) mRoot = remove(mRoot, key); /* * 销毁伸展树 */ private void destroy(SplayTreeNode tree) if (tree=null) return ; if (tree.left != null) destroy(tree.left); if (tree.right != null) destroy(tree.right); tree=null; public void clear() destroy(mRoot); mRoot = null; /* * 打印伸展树 * * key - 节点的键值 * direction - 0，表示该节点是根节点; * -1，表示该节点是它的父结点的左孩子; * 1，表示该节点是它的父结点的右孩子。 */ private void print(SplayTreeNode tree, T key, int direction) if(tree != null) if(direction=0) / tree是根节点 System.out.printf(%2d is rootn, tree.key); else / tree是分支节点 System.out.printf(%2d is %2ds %6s childn, t