Splay伸展樹

伸展樹（Splay Tree）是一種二叉排序樹，能在最壞平攤LogN時間内完成插入、查找和删除操作。是一種自調整形式的二叉樹，它會沿着某個節點到跟的路徑，通過一系列旋轉把這個節點搬到根節點去。

Splay樹的基本操作：

1、旋轉和伸展

2、查找

3、插入、删除

4、最大最小值

5、前驅後繼

6、合并、分離

一般Splay的節點資料：

struct node{
    int val,size;       //節點值，節點大小
    node * ch[],*fa;   //左右節點，父節點
}*root=NULL;            
           

Splay旋轉：

void Rotate(Node *&x,int c){//c== 左旋 c==右旋 
    Node *y=x->fa;
    //PushDown(y);
    //PushDown(x);
    //PushDown(x->ch[c]);
    y->ch[!c] = x->ch[c];
    if(x->ch[c] != NULL) x->ch[c]->fa = y;
    x->fa = y->fa;
    if(y->fa != NULL)
        if(y->fa->ch[] == y) y->fa->ch[] = x;
        else y->fa->ch[] = x;
    x->ch[c] = y; y->fa = x;
    //UpDate(y);
    if(y == root) root=x;
}
           

注意：前方高能

伸展操作：

情況一：節點x的父節點y是根節點。這時，如果x是p的左孩子，我們進行一次Zig（右旋）操作；如果x 是p 的右孩子，則我們進行一次Zag（左旋）操作。經過旋轉，x成為二叉查找樹的根節點，調整結束。即：如果目前結點父結點即為根結點，那麼我們隻需要進行一次簡單旋轉即可完成任務，我們稱這種旋轉為單旋轉。如圖1所示：

情況二：（一般稱作“一字型旋轉”）節點x 的父節點p 不是根節點，p 的父節點為g，且x 與p 同時是各自父節點的左孩子或者同時是各自父節點的右孩子。這時，我們進行一次Zig-Zig操作或者Zag-Zag操作。即：設目前結點為x ， x 的父結點為p ，p 的父結點為g ，如果p 和x 同為其父親的左孩子或右孩子，那麼我們先旋轉p ，再旋轉x 。如圖2所示：

情況三：（一般稱作“之字型旋轉”）節點x的父節點p不是根節點，p的父節點為g，x與p中一個是其父節點的左孩子而另一個是其父節點的右孩子。這時，我們進行一次Zig-Zag操作或者Zag-Zig 操作。即：這時我們連續旋轉兩次X 。如圖3所示：

說明：這種情況先将x轉到它的父親的位置上，再與g旋轉

SPLAY伸展操作代碼:

// node 為結點類型，其中ch[]表示左結點指針，ch[]表示右結點指針  
// pre 表示指向父親的指針  
void Rotate(Node *&x,int c){//c== 左旋 c==右旋 
    Node *y=x->fa;
    //PushDown(y);
    //PushDown(x);
    //PushDown(x->ch[c]);
    y->ch[!c] = x->ch[c];
    if(x->ch[c] != NULL) x->ch[c]->fa = y;
    x->fa = y->fa;
    if(y->fa != NULL)
        if(y->fa->ch[] == y) y->fa->ch[] = x;
        else y->fa->ch[] = x;
    x->ch[c] = y; y->fa = x;
    //UpDate(y);
    if(y == root) root=x;
} 
void Splay(Node *&cur,Node *&f){//将cur轉到f的位置 
    for(PushDown(cur); cur != f ;){
        if(cur->fa == f) 
            if(f->ch[] == cur) Rotate(cur,);
            else Rotate(cur,);
        else {
            Node *y = cur->fa,*z = y->fa;
            if(z->ch[] == y)
                if(y->ch[] == cur)
                    Rotate(y,),Rotate(cur,);//yi
                else Rotate(cur,),Rotate(cur,);//zhi
            else if(y->ch[] == cur)
                    Rotate(y,),Rotate(cur,);//yi
                else Rotate(cur,),Rotate(cur,);//zhi
            if(z==f) break;
        }
        //UpDate(cur);
    }
    //UpDate(cur);
} 
           

如果說要把某個節點轉到根的位置，你可以假設還有一個須根，目前樹的根永遠吊在須根上！！（個人心得、僅供參考）

Splay樹的遞歸建立

當建樹節點的值是有序的時候，可以利用遞歸方式建樹，類似于線段樹的建樹方式，效率還是比較高的。

void build(node *fa,node *&cur,int l,int r){
    if(l>r)return;
    int mid=(l+r)>>;
    cur=newnode(sz[mid]);
    cur->pre=fa;
    build(cur,cur->ch[],l,mid-);
    build(cur,cur->ch[],mid+,r);
    update(cur);
}
           

Splay的節點查找

首先按照二叉排序樹的性質（左子樹都比它小，右子樹都比它大），然後将該節點伸展到根節點。。

//查找鍵值為X的節點的位置并将其旋轉到根節點 
node *bst_search(node *cur,int x){
    if(!cur) return NULL;
    if(cur->sh == x) return cur;
    else if(x > cur->sh)
        return bst_search(cur->ch[],x);
    else if(x < cur->sh)
        return bst_search(cur->ch[],x);
}
//bst_search 傳回的是鍵值為x的元素的位置 
node *search(node *cur,int x){
    node *p=bst_search(cur,x);
    //此時p即為元素x的位置
    splay(p,cur->pre);
    return p;
}
           

找到處在中序周遊第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[];
    }
    Push_Down(t);
    splay(t,f); // 執行旋轉
}
           

Splay節點插入：

按照二叉排序樹插入，然後将其旋轉到根節點下

結構體裡寫上這個函數：

node *newnode(int x){
    node *cur=new node;
    cur->val = x;
    cur->ch[] = cur->ch[] = cur->pre = NULL;
}
           

然後是插入函數：

//插入值為x的一個新節點 
void insert(node * cur,int x){
    if(root==NULL){//cur不可改變，root要特判
        root=newnode(x);
        return ;
    }
    node *p;
    while(cur!=NULL){
        p=cur;
        if(cur->val>x) cur = cur->ch[];
        else cur = cur->ch[];
    }
    //在 while 過程當中 p始終保持是cur的父節點 
    cur=newnode(x);
    if(cur->val < p->val) p->ch[]=cur; //注意判讀條件，不可用cur==p->ch[0]
    else p->ch[]=cur;
    cur->pre = p;
    splay(cur,NULL);
}
           

Splay的合并：

将倆棵伸展樹合并必須保證第二課伸展樹的值都大于第一棵伸展樹，隻需要将第一棵伸展樹的最大節點轉到根的位置上，這時候該節點的有孩子為空（因為：該節點是最大的節點，如果他還有右孩子的話根據二叉排序樹的定義他的右孩子比他大），直接将第二棵伸展樹挂到第一棵伸展樹的最大節點的右孩子上。。

node *merge(node *x,node *y){
    if(!x) return y;
    if(!y) return x;
    while(x->ch[]) x = x->ch[];
    splay(x,NULL);
    x->ch[] = y;
    y->pre = x;
    return x;
}
           

Splay分離：

方法：查找給定值得節點并伸展到根，傳回它的左右孩子

//Splay 分離
void split(node *cur,int x,node *&x,node *&y){
    node *t=search(cur,x);
    x=cur->ch[];x->pre=NULL;
    y=cur->ch[];y->pre=NULL;
}
           

Splay節點删除：

//值為x的節點删除 
node *del(node *cur,int x){
    node *t=search(cur,x);
    return merge(cur->ch[],cur->ch[]);
}
           

上面的内容看看還行，代碼就算了，代碼是我粘的我們呂老師的，指針寫的是又臭又長又醜，代碼還的看我的。。