伸展树 splay tree

1、伸展树,伸展树是二叉查找树的一种改进，与二叉查找树一样，伸展树也具有有序性。即伸展树中的每一个节点x都满足：该节点左子树中的每一个元素都小于x，而其右子树中的每一个元素都大于x。与普通二叉查找树不同的是，伸展树可以自我调整，这就要依靠伸展操作Splay(x,S)。 伸展操作Splay(x,S): 把x旋转到树根, 同时保持树是一棵合法的BST,splay作为一个二叉排序树所具有特点用一句来概述就是“可以让你把指的结点放在树根的位置或者作为树根的儿子”很多参考资料都会这么介绍 splay 说它是一个自调整树，把最近访问的节点移到根处以使得下次再访问它时可以快速找到，我理解的 splay 就只有一

2、种操作就是把一个节点移动到根处，在这个过程中我们不需要处理平衡的问题，尽管它可能会变成一个线性的形状但这都是小概率事件,splay 强大之处在于对它可以快速的对区间进行操作，比如对一个序列的指定子序列进行反转或者把它们整体移动到一个新的位置（参考TOJ-3578）.。还对在区间的指定位置处随意插入、删除、更新元素，同时可以很快取得指定子区间的和、指定子区间的连续或者区间内的最大、最小值（参考SPOJ-4487）,初看起来询问区间最大最小值与子区间和或者连续最大和 这些不都是线段树干的活。是的你没有想错，在学会 splay 之前，线段树的确是处理这个区间问题的高手，但在你完全掌握 splay 后

3、，它能让你处理更多的区间操作，对一些问题它内功要远远高于线段树，至于一些复杂问题都到了非用它不可的地步。,在谈伸展树之前，我们还是先看一下回忆下AVL树，尤其是它的调整规律,AVL实际上是平衡查找树，英文名称应该是BBST才对，AVL来自于发明它的人名，这里不追究了. 平衡，顾名思义，就是两边看起来比较对称，但很多时候我们是做不到绝对的对称（绝对对称即对任意子树而言，左右节点的数量都相等），因为只有(2n-1)元素数目的二叉树才能做到绝对对称，所以我们使用了“高度”（height）这么个概念，某节点的高度指的是它离它的子树的叶子的最远距离：,那么我再引申出两个概念，左高和右高：左高 = 左节点

4、空 ? 0 : (左节点高+1)右高 = 右节点空 ? 0 : (右节点高+1)那我们就可以给AVL下个定义了，对AVL的任意节点而言：定义一个平衡因BF(balance factor) BF=(左高 - 右高) ; abs(BF)=1;,做到了这点，这棵树看起来就比较平衡了，如何生成一棵AVL树呢？算法十分不简单，那我们先通过图来获得一些最直观的认识，就先按1，2，3，4这样的自然数顺序加入到树中，下图体现出了树的构造变化：,随着新节点的加入，树自动调整自身结构，达到新的平衡状态，这就是我们想要的AVL树。我们先要分析，为什么树会失衡？是由于插入了一个元素，对吧，那我们能不能把不同的插入情况

5、全部概括起来并作出统一的调整来使得树重新平衡？答案是肯定的，也有人帮我们研究好了，所以直接给出算法示意图和范例。LL 型调整过程：1）经AB向右顺时针旋转90度，把A的右孩子变为B的左孩子2）B变为A的右孩子，A替代B的位置,再给一个LL型调整的实例：,RR型调整，其实就是LL型调整的镜像而已：,这是一个RR型调整的实例,LR型双向旋转，先左后右最小失衡点的左子树根节点的右子树上插入节点。,LR型调整过程1）先将BC（以B为中心）向左逆时针旋转90度，把c的左子树变为B的右子树，B变为c的左孩子。,2）将CA向右顺时针旋转90度，c的右孩子变为A的左孩子，A为C右孩子，C代替A的位置,LR的一

6、个实例,RL型调整是LR型调整的镜像，所以不再画图了。,在谈splay tree,假设想要对一个二叉查找树执行一系列的查找操作。为了使整个查找时间更小，被查频率高的那些条目就应当经常处于靠近树根的位置。于是想到设计一个简单方 法，在每次查找之后对树进行重构，把被查找的条目搬移到离树根近一些的地方。splay tree应运而生。splay tree是一种自调整形式的二叉查找树，它会沿着从某个节点到树根之间的路径，通过一系列的旋转把这个节点搬移到树根去。,伸展操作Splay(x,S)是在保持伸展树有序性的前提下，通过一系列旋转将伸展树S中的元素x调整至树的根部。在调整的过程中，要分以下三种情况分别

7、处理：,情况一：节点x的父节点y是根节点。这时，如果x是y的左孩子，我们进行一次Zig（右旋）操作；如果x是y的右孩子，则我们进行一次Zag（左旋）操作。经过旋转，x成为二叉查找树S的根节点，调整结束。如图所示,情况二：节点x的父节点y不是根节点，y的父节点为z，且x与y同时是各自父节点的左孩子或者同时是各自父节点的右孩子。这时，我们进行一次Zig-Zig操作或者Zag-Zag操作。如图,情况三：节点x的父节点y不是根节点，y的父节点为z，x与y中一个是其父节点的左孩子而另一个是其父节点的右孩子。这时，我们进行一次Zig-Zag操作或者Zag-Zig操作。如图所示,如图4所示，执行Splay(

8、1,S)，我们将元素1调整到了伸展树S的根部。再执行Splay(2,S)。如图5所示，我们从直观上可以看出在经过调整后，伸展树比原来“平衡”了许多。而伸展操作的过程并不复杂，只需要根据情况进行旋转就可以了，而三种旋转都是由基本得左旋和右旋组成的，实现较为简单。,Splay tree definition,typedef int ElementType ; typedef struct SplayTreeNode ElementType element ; SplayTreeNode *left,*right; SplayTreeNode; typedef struct SplayTreeNod

9、e *SplayTree; typedef struct SplayTreeNode *Position;,SplayTree single_right_rotate( SplayTree T ) SplayTree x = T; SplayTree y = T-left; x-left = y-right; y-right = x; return y; SplayTree single_left_rotate( SplayTree T ) SplayTree x = T; SplayTree y = T-right; x-right = y-left; y-left = x; return

10、y; ,SplayTree left_right_rotate( SplayTree T ) T-left = single_left_rotate( T-left ); return single_right_rotate( T ); /LR SplayTree right_left_rotate( SplayTree T ) T-right = single_right_rotate( T-right ); return single_left_rotate( T ); /RL,Position splay( Element X, SplayTree *T ) 是伸展函数， 如果X存在就做

11、Splay操作，将包含X的节点移到树根处。并返回包含X节点的位置 如果不存在就返回NULL。,SplayTree insert(ElementType X,SplayTree T); 将元素x插入伸展树S表示的有序集中。 首先，也与处理普通的二叉查找树一样，将x插入到伸展树S中的相应位置上，再执行Splay(x,S)。,SplatTree delete( ElementType X, SplayTree ) 返回是删除后的树。如果X存在，就删除X， 否则不做任何修改。 首先，用在二叉查找树中查找元素的方法找到x的位置。如果x没有孩子或只有一个孩子，那么直接将x删去，并通过Splay操作，将x节点的父节点调整到伸展树的根节点处。否则，则向下查找x的后继y，用y替代x的位置，最后执行Splay(y,S)，将y调整为伸展树的根。,应用一、字典,要求: 支持以下操作 INSERT(key) DELETE(key) FIND(key) 实现: 直接用伸展树即可. 每个操作平摊时间均为O(logn),应用二、前趋后继,要求: 支持以下操作 INSERT(key) DELETE(key) FIND(key) PRED(key) SUCC(key) 前