伸展树(Splay tree)浅谈

树看的越来越多，越来越神奇。

看伸展树这种神级数据结构之前，建议大家首先彻底明白二叉搜索树，这是万树的基础。

然后可以去看下treap,最好再去看下红黑树。如果有线段树的基础那更好了，我们会发现线段树难以实现一些直接删除，直接插入的数据。

这个时候就体现出神级数据解耦 伸展树的魅力了，他的区间操作的非常优雅的。

有了这些基础之后，那就可以splay了。

zig,zag,zig和zag的组合。splay也就是通过一系列的左右旋转达到了splay的目的，把当前节点旋转到指定节点的下面。

具体信息可以查看：http://blog.csdn.net/niuox/article/details/8018280

里面有介绍如何运用伸展树进行区间操作，这是我们学伸展树的一个关键所在，否则，一般的二叉搜索树，我们用treap或者set完全可以搞定。

昨天睡不着我想，splay不过是一种平衡树而已，我们是不是可以用红黑树来达到区间操作的呢，或者用treap。。。。不晓得。不过红黑树代码太长。。。

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[0] == y) y->pre->ch[0] = x;
        else y->pre->ch[1] = x;
    x->ch[c] = y, y->pre = x;
    if (y == root) root = x; // root 表示整棵树的根结点
}

具体的题目：

hdu 1754  

我先闪人  有空再来继续。。。。未完待续。。。。

伸展树(Splay tree)浅谈,布布扣,bubuko.com

伸展树(Splay tree)浅谈

原文：http://blog.csdn.net/cnh294141800/article/details/23341337