[转] Splay Tree(伸展树)

好久没写过了，比赛的时候就调了一个小时，差点悲剧，重新复习一下，觉得这个写的很不错、转自：here

Splay Tree(伸展树)

二叉查找树（Binary Search Tree）能够支持多种动态集合操作。因此，在信息学竞赛中，二叉排序树起着非常重要的作用，它可以被用来表示有序集合、建立索引或优先队列等。

作用于二叉查找树上的基本操作的时间是与树的高度成正比的。对一个含n各节点的完全二叉树，这些操作的最坏情况运行时间为O(log n)。但如果树是含n个节点的线性链，则这些操作的最坏情况运行时间为O(n)。而有些二叉查找树的变形，其基本操作在最坏情况下性能依然很好，比如红黑树、AVL树等等。

本文将要介绍的伸展树（Splay Tree），也是对二叉查找树的一种改进，虽然它并不能保证树一直是“平衡”的，但对于伸展树的一系列操作，我们可以证明其每一步操作的平摊复杂度都是O(log n)。所以从某种意义上说，伸展树也是一种平衡的二叉查找树。而在各种树状数据结构中，伸展树的空间要求与编程复杂度也都是很优秀的。

【伸展树的基本操作】

伸展树是二叉查找树的一种改进，与二叉查找树一样，伸展树也具有有序性。即伸展树中的每一个节点x都满足：该节点左子树中的每一个元素都小于x，而其右子树中的每一个元素都大于x。与普通二叉查找树不同的是，伸展树可以自我调整，这就要依靠伸展操作Splay(x,S)。

伸展操作 Splay(x,S)

伸展操作Splay(x,S)是在保持伸展树有序性的前提下，通过一系列旋转将伸展树S中的元素x调整至树的根部。在调整的过程中，要分以下三种情况分别处理：

情况一：节点x的父节点y是根节点。这时，如果x是y的左孩子，我们进行一次Zig（右旋）操作；如果x 是y 的右孩子，则我们进行一次Zag（左旋）操作。经过旋转，x成为二叉查找树S的根节点，调整结束。即：如果当前结点父结点即为根结点，那么我们只需要进行一次简单旋转即可完成任务，我们称这种旋转为单旋转。如图1所示

（图1）

情况二：节点x 的父节点y 不是根节点，y 的父节点为z，且x 与y 同时是各自父节点的左孩子或者同时是各自父节点的右孩子。这时，我们进行一次Zig-Zig操作或者Zag-Zag操作。即：设当前结点为X ， X 的父结点为Y ，Y 的父结点为Z ，如果Y 和X 同为其父亲的左孩子或右孩子，那么我们先旋转Y ，再旋转X 。我们称这种旋转为一字形旋转。如图2所示

（图2）

情况三：节点x的父节点y不是根节点，y的父节点为z，x与y中一个是其父节点的左孩子而另一个是其父节点的右孩子。这时，我们进行一次Zig-Zag操作或者Zag-Zig 操作。即：这时我们连续旋转两次X 。我们称这种旋转为之字形旋转。如图3所示

(图3)

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

（图4）

（图5）

利用Splay操作，我们可以在伸展树S上进行如下运算：

(1)Find(x,S)：判断元素x是否在伸展树S表示的有序集中。

首先，与在二叉查找树中的查找操作一样，在伸展树中查找元素x。如果x在树中，则再执行Splay(x,S)调整伸展树。

(2)Insert(x,S)：将元素x插入伸展树S表示的有序集中。

首先，也与处理普通的二叉查找树一样，将x 插入到伸展树S中的相应位置上，再执行Splay(x,S)。

(3)Delete(x,S)：将元素x从伸展树S所表示的有序集中删除。

首先，用在二叉查找树中查找元素的方法找到x的位置。如果x没有孩子或只有一个孩子，那么直接将x删去，并通过Splay操作，将x节点的父节点调整

到伸展树的根节点处。否则，则向下查找x的后继y，用y替代x的位置，最后执行Splay(y,S)，将y调整为伸展树的根。

(4)Join(S1,S2)：将两个伸展树S1与S2合并成为一个伸展树。其中S1的所有元素都小于S2的所有元素。首先，我们找到伸展树S1 中最大的一个元素x，再通过Splay(x,S1)将x 调整到伸展树S1 的根。然后再将S2 作为x 节点的右子树。这样，就得到了新的伸展树S。如图6所示

（图6）

(5)Split(x,S)：以x 为界，将伸展树S 分离为两棵伸展树S1 和S2，其中S1中所有元素都小于x，S2中的所有元素都大于x。首先执行Find(x,S)，将元素x 调整为伸展树的根节点，则x 的左子树就是S1，而右子树为S2。如图7所示

（图7）

除了上面介绍的五种基本操作，伸展树还支持求最大值、求最小值、求前趋、求后继等多种操作，这些基本操作也都是建立在伸展操作的基础上的。

通常来说，每进行一种操作后都会进行一次Splay 操作，这样可以保证每次操作的平摊时间复杂度是O(log n)。关于证明可以参见相关书籍和论文。

既然可以把任何一个结点转到根，那么也就可以把任意一个结点转到其到根路径上任何一个结点的下面（特别地，转到根就是转到空结点Null 的下面）。下面的利用伸展树维护数列就要用到将一个结点转到某个结点下面。

// node 为结点类型，其中ch[0]表示左结点指针，ch[1]表示右结点指针
// pre 表示指向父亲的指针
void Rotate(node *x, int c) // 旋转操作，c=0 表示左旋，c=1 表示右旋
{
    node *y = x->pre;
    y->ch[! c] = x->ch[c];
    if (x->ch[c] != Null) x->ch[c]->pre = y;
    x->pre = y->pre;
    if (y->pre != Null)
        if (y->pre->ch[] == y) y->pre->ch[] = x;
        else y->pre->ch[] = x;
    x->ch[c] = y, y->pre = x;
    if (y == root) root = x; // root 表示整棵树的根结点
}
void Splay(node *x, node *f) // Splay 操作，表示把结点x 转到结点f 的下面
{
    for ( ; x->pre != f; )
        if (x->pre->pre == f) // 父结点的父亲即为f，执行单旋转
            if (x->pre->ch[] == x) Rotate(x, );
            else Rotate(x, );
        else
        {
            node *y = x->pre, *z = y->pre;
            if (z->ch[] == y)
                if (y->ch[] == x)
                    Rotate(y, ), Rotate(x, ); // 一字形旋转
                else
                    Rotate(x, ), Rotate(x, ); // 之字形旋转
            else if (y->ch[] == x)
                Rotate(y, ), Rotate(x, ); // 一字形旋转
            else
                Rotate(x, ), Rotate(x, ); // 之字形旋转
        }
}

【伸展树的区间操作】

首先我们认为伸展树的中序遍历即为我们维护的数列，那么很重要的一个操作就是怎么在伸展树中表示任意一个区间。比如我们要提取区间a,b]，那么我们将a前面一个数对应的结点转到树根，将b 后面一个结点对应的结点转到树根的右边，那么根右边的左子树就对应了区间[a,b]。其中的道理也是很简单的，将a 前面一个数对应的结点转到树根后， a 及a 后面的数就在根的右子树上，然后又将b后面一个结点对应的结点转到树根的右边，那么[a,b]这个区间就是图8中*所示的子树。

利用这个，我们就可以实现线段树的一些功能，比如回答对区间的询问。我们在每个结点上记录关于以这个结点为根的子树的信息，然后询问时先提取区间，再直接读取子树的相关信息。还可以对区间进行整体修改，这也要用到和线段树类似的延迟标记技术，就是对于每个结点，再额外记录一个或多个标记，表示以这个结点为根的子树是否被进行了某种操作，并且这种操作影响其子结点的信息值。当然，既然记录了标记，那么旋转和其他一些操作中也就要相应地将标记向下传递。

（图8）

到目前为止，伸展树只是实现了线段树能够实现的功能，下面两个功能将是线段树无法办到的。如果我们要在a 后面插入一些数，那么我们先把这些插入的数建成一棵伸展树，我们可以利用分治法建立一棵完全平衡的二叉树，就是说每次把最中间的作为当前区间的根，然后左右递归处理，返回的时候进行维护。接着将a 转到根，将a 后面一个数对应的结点转到根结点的右边，最后将这棵新的子树挂到根右子结点的左子结点上。还有一个操作就是删除一个区间[a,b]内的数，像上面一样，我们先提取区间，然后直接删除那棵子树，即可达到目的。最后还需注意的就是，每当进行一个对数列进行修改的操作后，都要维护伸展树，一种方法就是对影响到的结点从下往上执行Update 操作。但还有一种方法，就是将修改的结点旋转到根，因为Splay 操作在旋转的同时也会维护每个结点的值，因此可以达到对整个伸展树维护的目的。最后还有一个小问题，因为数列中第一个数前面没有数字了，并且最后一个数后面也没有数字了，这样提取区间时就会出一些问题。为了不进行过多的特殊判断，我们在原数列最前面和最后面分别加上一个数，在伸展树中就体现为结点，这样提取区间的时候原来的第k个数就是现在的第k +1个数。并且我们还要注意，这两个结点维护的信息不能影响到正确的结果。下面看一下新的Splay 操作的程序（能对结点信息进行维护）：

// node 为结点类型，其中ch[0]表示左结点指针，ch[1]表示右结点指针
// pre 表示指向父亲的指针
void Rotate(node *x, int c) // 旋转操作，c=0 表示左旋，c=1 表示右旋
{
    node *y = x->pre;
    Push_Down(y), Push_Down(x);
// 先将Y 结点的标记向下传递（因为Y 在上面），再把X 的标记向下传递
    y->ch[! c] = x->ch[c];
    if (x->ch[c] != Null) x->ch[c]->pre = y;
    x->pre = y->pre;
    if (y->pre != Null)
        if (y->pre->ch[] == y) y->pre->ch[] = x;
        else y->pre->ch[] = x;
    x->ch[c] = y, y->pre = x, Update(y); // 维护Y 结点
    if (y == root) root = x; // root 表示整棵树的根结点
}
void Splay(node *x, node *f) // Splay 操作，表示把结点x 转到结点f 的下面
{
    for (Push_Down(x) ; x->pre != f; ) // 一开始就将X 的标记下传
        if (x->pre->pre == f) // 父结点的父亲即为f，执行单旋转
            if (x->pre->ch[] == x) Rotate(x, );
            else Rotate(x, );
        else
        {
            node *y = x->pre, *z = y->pre;
            if (z->ch[] == y)
                if (y->ch[] == x)
                    Rotate(y, ), Rotate(x, ); // 一字形旋转
                else
                    Rotate(x, ), Rotate(x, ); // 之字形旋转
            else if (y->ch[] == x)
                Rotate(y, ), Rotate(x, ); // 一字形旋转
            else
                Rotate(x, ), Rotate(x, ); // 之字形旋转
        }
    Update(x); // 最后再维护X 结点
}

可能有人会问，为什么在旋转的时候只对X 结点的父亲进行维护，而不对X结点进行维护，但是Splay 操作的最后却又维护了X 结点？原因很简单。因为除了一字形旋转，在Splay 操作里我们进行的旋转都只对X 结点进行，因此过早地维护是多余的；而在一字形旋转中，好像在旋转中没有对X 的父亲进行维护，但后面紧接着就是旋转X 结点，又会对X 的父亲进行维护，也是没问题的。这样可以节省不少冗余的Update 操作，能减小程序隐含的常数。

最后我们看看怎么样实现把数列中第k 个数对应的结点转到想要的位置。对于这个操作，我们要记录每个以结点为根子树的大小，即包含结点的个数，然后从根开始，每次决定是向左走，还是向右走，具体见下面的代码：

// 找到处在中序遍历第k 个结点，并将其旋转到结点f 的下面
void Select(int k, node *f)
{
    int tmp;
    node *t;
    for (t = root; ; ) // 从根结点开始
    {
        Push_Down(t); // 由于要访问t 的子结点，将标记下传
        tmp = t->ch[]->size; // 得到t 左子树的大小
        if (k == tmp + ) break; // 得出t 即为查找结点，退出循环
        if (k <= tmp) // 第k 个结点在t 左边，向左走
            t = t->ch[];
        else // 否则在右边，而且在右子树中，这个结点不再是第k 个
            k -= tmp + , t = t->ch[];
    }
    Splay(t, f); // 执行旋转
}