展开树介绍展开树（SplayTree）是一种特殊的二叉搜索树。它的特殊性是指它除了是一棵二叉搜索树之外，还有一个特点：当访问一个节点时，splay树会进行旋转，使该节点成为树的根。这样做的好处是下次要访问该节点时，可以快速访问该节点。与普通的二叉搜索树相比，它在任何情况和任何操作下都具有平摊O(log2n)的复杂度，并且时间性能更好。与红黑树、AVL树等一般平衡二叉树相比，维护的节点额外信息更少，空间性能更好，编程复杂度更低。在很多情况下，对于查找操作，后续查询与之前的查询高度相关。这样，每次查询操作都会将检测到的节点旋转到树的根节点位置，这样可以快速完成下一次查询操作，完成区间的查询、修改、删除，而行可以实现线段树和树数组。所有旋转splay树实现O(log2n)级别摊销复杂度的函数都依赖于每次对splay树进行查询、修改、删除操作后的旋转操作Splay(x,root)，将节点x旋转到根树的。splay树中有六种旋转类型，如果删除镜像重复，则为三种：zig(zag)、zig-zig(zag-zag)、zig-zag(zag-zig)。1bottom-uprotation1.1zigrotation如图所示，节点x的父节点为y，x为y的左子节点，节点y为根。那么它只需要对节点x进行右旋转（zig操作），使其成为y的父节点，这样x就可以成为扩展树的根节点。1.2Zig-zig旋转如上图所示，节点x的父节点y，和y的父节点z，都在inline链上。此时zig先旋转y节点和z节点，然后zig旋转x节点和y节点，最后变成右图，x成为y和z的祖先节点。1.3zig-zagrotation如上图所示，节点x的父节点y和y的父节点z在zigzag链上。此时先对x节点和y节点进行zig旋转，再对x节点和y节点进行zag旋转。最后如右图所示，x成为y和z的祖先节点。2以自上而下的方式旋转这种方法不需要节点存储对其父节点的引用。当我们向下搜索树中的节点x时，搜索路径上的节点及其子树将被删除。建造两棵临时树——左树和右树。由未被删除的节点组成的树称为中间树。当前节点x是中间树的根。左树L保存小于x的节点，右树R保存大于x的节点。一开始，x是树T的根，左树L和右树R都是空的。三种旋转操作：2.1zig旋转如图，x节点的子节点y就是我们要找的节点，所以我们只需要对y节点进行一次右旋转（zig操作）即可它是x的父节点，然后可以让y成为splay树的根节点。将y作为中间树的根节点，同时将x节点移动到右树R中。显然，右树上的节点比要查找的节点大。2.2zig-zigrotation如上图所示，节点x的左子节点y，和y的左子节点z都在内联链上，待查找的节点位于以节点z为根的子树中.此时先对x节点和y节点进行zig，再对z和y进行zig，使z成为中间树的根，同时将y及其子树挂载到右树R上。2.3Zig-zagrotation如上图所示，节点x的左子节点y和y的右子节点z在zigzag链上，要查找的元素位于以z为根的子树上。此时先对x节点和y节点进行zig旋转，将x及其右子树挂载到右树R上，此时y成为中间树的根节点；然后对z节点和y节点进行zag旋转，使z成为树的根节点。2.4合并最后，在找到节点或遇到空节点后，需要合并左、中、右三棵树。如图所示，左树挂载在中间树的左下方（满足遍历顺序要求），右树挂载在中间树的最右下方（满足遍历顺序要求）。stretchtree的实现1.NodepublicclassSplayTree>{privateSplayTreeNodemRoot;//根节点publicclassSplayTreeNode>{Tkey;//关键字（键值）SplayTreeNodeleft;//左孩子SplayTreeNoderight;//右孩子publicSplayTreeNode(){this.left=null;this.right=null;}publicSplayTreeNode(Tkey,SplayTreeNodeleft,SplayTreeNoderight){this.key=key;this.left=left;this.right=right;}}}SplayTree是一个splay树，SplayTreeNode是一个splay树节点。在这里，我将SplayTreeNode定义为SplayTree的内部类。展开树的根节点mRoot包含在展开树SplayTree中。SplayTreeNode由几个元素组成：key–是一个关键字，用于对splay树的节点进行排序。left——是左孩子。right——是正确的孩子。2.rotation/**rotationkey对应的节点为根节点，返回根节点。**注：*(a)：展开的树中有一个“key值为key的节点”。*轮转“key值为key的节点”为根节点。*(b)：扩展树中不存在“键值为key的节点”，且keytree.key。*c-1如果“键值为key的节点”的后继节点存在，则将“键值为key的节点”的后继节点轮换到根节点。*c-2如果“key值为key的节点”的后继节点不存在，则表示该key大于树中任意一个key值，则此时轮换最大的节点为根节点。*/privateSplayTreeNodesplay(SplayTreeNodetree,Tkey){if(tree==null)returntree;SplayTreeNodeN=newSplayTreeNode();SplayTreeNodel=N;SplayTreeNoder=N;SplayTreeNodec;for(;;){intcmp=key.compareTo(tree.key);if(cmp<0){if(key.compareTo(tree.left.key)<0){c=tree.left;/*rotateright*/tree.left=c.right;c.right=tree;tree=c;if(tree.left==null)break;}r.left=tree;/*linkright*/r=tree;tree=tree.left;}elseif(cmp>0){if(tree.right==null)break;if(key.compareTo(tree.right.key)>0){c=tree.right;/*rotateleft*/tree.right=c.left;c.left=tree;tree=c;if(tree.right==null)break;}l.right=tree;/*linkleft*/l=tree;tree=tree.right;}else{break;}}l.right=tree.left;/*assemble*/r.left=tree.right;tree.left=N.right;tree.right=N.left;returntree;}publicvoidsplay(Tkey){mRoot=splay(mRoot,key);}上面代码的作用：将“key值为key的节点”旋转到根节点，返回根节点。其处理条件包括：(a)：扩展树中存在“key值为key的节点”。轮转“key为key的节点”为根节点。(b)：扩展树中不存在“键值为key的节点”，且keykey。b-1)如果“键值为key的节点”的前驱节点存在，则轮换“键值为key的节点”的前驱节点为根节点。b-2)如果“key值为key的节点”的前驱节点存在，说明该key小于树中任意一个key值，则此时轮换最小的节点为根节点.(c)：扩展树中不存在“key值为key的节点”，key>tree->key。c-1)如果“键值为key的节点”的后继节点存在，则轮换“键值为key的节点”的后继节点为根节点。c-2)如果“key为key的节点”的后继节点不存在，说明该key大于树中任意一个key，则此时轮换最大的节点为根节点.下面分别举例说明。在下面的扩展树中找到10个，包括“右旋转”->“右链接”->“组合”3个步骤。01，右旋转对应代码的“向右旋转”部分02，右链接对应代码的“链接右”部分03.组合对应代码的“组装”部分提示：如果你在上面的stretchtree中搜索“70”，它与“例1”正好对称，对应的操作是“向左旋转”、“向左链接”和“组装”。其他的情况，比如“求15是b-1的情况，求5是b-2的情况”等等，这些都比较简单，大家可以自己分析。3.插入/***将节点插入splay树并返回根节点*@paramtreesplay树根节点*@paramz插入节点*@return*/privateSplayTreeNodeinsert(SplayTreeNodetree,SplayTreeNodez){intcmp;SplayTreeNodey=null;SplayTreeNodex=tree;//找到z的插入位置while(x!=null){y=x;cmp=z.key.compareTo(x.key);if(cmp<0)x=x.left;elseif(cmp>0)x=x.right;else{System.out.printf("不允许插入相同的节点(%d)!\n",z.key);z=null;returntree;}}if(y==null)tree=z;else{cmp=z.key.compareTo(y.key);if(cmp<0)y.left=z;elsey.right=z;}returntree;}publicvoidinsert(Tkey){SplayTreeNodez=newSplayTreeNode(key,null,null);//如果新节点失败，返回。if((z=newSplayTreeNode(key,null,null))==null)return;//插入节点mRoot=insert(mRoot,z);//旋转节点(key)到根节点mRoot=splay(mRoot,key);}insert(key)是对外提供的接口，其作用是新建一个节点（节点的key值为key），并将该节点插入到扩展树中；然后，旋转该节点作为根节点。insert(tree,z)是一个内部接口，其作用是将节点z插入到树中。insert(tree,z)将z插入tree时只把tree当作二叉搜索树处理，不允许插入相同的节点。4.删除/****@paramtree扩展树*@paramkey删除节点*@return*/privateSplayTreeNoderemove(SplayTreeNodetree,Tkey){SplayTreeNodex;if(tree==null)returnnull;//查找key值为key的节点，没有找到直接返回。if(search(tree,key)==null)returntree;//旋转key对应的节点作为根节点。tree=splay(tree,key);if(tree.left!=null){//将“树的前驱节点”旋转到根节点x=splay(tree.left,key);//移除树nodex.right=tree.right;}elsex=tree.right;tree=null;returnx;}publicvoidremove(Tkey){mRoot=remove(mRoot,key);}remove(key)为对外接口，remove(tree,key)是内部接口。remove(tree,key)的作用是删除扩展树中key值为key的节点。它会先在splaytree中寻找key值为key的节点。如果没有找到，直接返回。如果找到，将该节点旋转为根节点，然后删除该节点。拉伸树实现完整代码publicclassSplayTree>{privateSplayTreeNodemRoot;//根节点publicclassSplayTreeNode>{Tkey;//keyword（键值）SplayTreeNodeleft;//LeftchildSplayTreeNoderight;//右孩子publicSplayTreeNode(){this.left=null;this.right=null;}publicSplayTreeNode(Tkey,SplayTreeNodeleft,SplayTreeNoderight){this.key=key;this.left=left;this.right=right;}}/**rotationkey对应的节点为根节点，返回根节点。**注：*(a)：展开的树中有一个“key值为key的节点”。*轮转“key值为key的节点”为根节点。*(b)：扩展树中不存在“键值为key的节点”，且keytree.key。*c-1如果“键值为key的节点”的后继节点存在，则将“键值为key的节点”的后继节点轮换到根节点。*c-2如果“key值为key的节点”的后继节点不存在，则表示该key大于树中任意一个key值，则此时轮换最大的节点为根节点。*/privateSplayTreeNodesplay(SplayTreeNodetree,Tkey){if(tree==null)returntree;SplayTreeNodeN=newSplayTreeNode();SplayTreeNodel=N;SplayTreeNoder=N;SplayTreeNodec;for(;;){intcmp=key.compareTo(tree.key);if(cmp<0){if(key.compareTo(tree.left.key)<0){c=tree.left;/*rotateright*/tree.left=c.right;c.right=tree;tree=c;if(tree.left==null)break;}r.left=tree;/*linkright*/r=tree;tree=tree.left;}elseif(cmp>0){if(tree.right==null)break;if(key.compareTo(tree.right.key)>0){c=tree.right;/*rotateleft*/tree.right=c.left;c.left=tree;tree=c;if(tree.right==null)break;}l.right=tree;/*linkleft*/l=tree;tree=tree.right;}else{break;}}l.right=tree.left;/*assemble*/r.left=tree.right;tree.left=N.right;tree.right=N.left;returntree;}publicvoidsplay(Tkey){mRoot=splay(mRoot,key);}/***将结束点插入到伸展树中，并返回根节点*@paramtree伸展树的根节点*@paramz插入的结束点*@return*/privateSplayTreeNodeinsert(SplayTreeNodetree,SplayTreeNodez){intcmp;SplayTreeNodey=null;SplayTreeNodex=tree;//找到z的插入位置while(x!=null){y=x;cmp=z.key.compareTo(x.key);if(cmp<0)x=x.left;elseif(cmp>0)x=x.right;else{System.out.printf("不允许插入相同节点(%d)!\n",z.key);z=null;returntree;}}if(y==null)tree=z;else{cmp=z.key.compareTo(y.key);if(cmp<0)y.left=z;elsey.right=z;}returntree;}publicvoidinsert(Tkey){SplayTreeNodez=newSplayTreeNode(key,null,null);//如果新节点失效，returnif((z=newSplayTreeNode(key,null,null))==null)return;//插入节点mRoot=insert(mRoot,z);//旋转节点（key）到根节点mRoot=splay(mRoot,key);}/**删除节点(z)并返回删除的节点**参数说明：*bst扩展树*z删除节点*//****@paramtree扩展树*@删除的节点paramkey*@return*/privateSplayTreeNoderemove(SplayTreeNodetree,Tkey){SplayTreeNodex;if(tree==null)returnnull;//查找key值为key的节点，如果找不到，直接返回。if(search(tree,key)==null)returntree;//旋转key对应的节点作为根节点。tree=splay(tree,key);if(tree.left!=null){//将“树的前驱节点”旋转到根节点x=splay(tree.left,key);//移除树nodex.right=tree.right;}elsex=tree.right;tree=null;returnx;}publicvoidremove(Tkey){mRoot=remove(mRoot,key);}/**(递归实现)找到“扩展树x"key值为key*的节点/privateSplayTreeNodesearch(SplayTreeNodex,Tkey){if(x==null)returnx;intcmp=key.compareTo(x.key);if(cmp<0)returnsearch(x.left,key);elseif(cmp>0)returnsearch(x.right,key);elsereturnx;}publicSplayTreeNodesearch(Tkey){returnsearch(mRoot,key);}/**找到最小节点：返回根节点为树的扩展树的最小节点。*/privateSplayTreeNodeminimum(SplayTreeNodetree){if(tree==null)returnnull;while(tree.left!=null)tree=tree.left;returntree;}publicTminimum(){SplayTreeNodep=minimum(mRoot);if(p!=null)returnp.key;returnnull;}/**求最大节点：返回根节点为tree的扩展树的最大节点。*/privateSplayTreeNodemaximum(SplayTreeNodetree){if(tree==null)returnnull;while(tree.right!=null)tree=tree.right;returntree;}publicTmaximum(){SplayTreeNodep=最大值（mRoot）；如果（p！=null）returnp.key；returnnull；}
