【平衡樹】splay

• splay

  平衡樹，也叫伸展樹，有很大的好處，同時也很哲學。。。

• 伸展

  它可以非常柔韌的變化，旋轉伸展合并等等，并且是均攤時間代價，代價很可觀。

• 操作

  伸展就是通過各種旋轉，把查詢删除更改的元素全轉到根，查詢頻率越高代價約可觀。

• 旋轉

  通過雙旋單旋來實作，在某一個節點旋轉到根的過程中路上的所有節點的子樹都會相應平衡，特别神奇，但神奇的同時也随之而來的就是寫法的哲學。。。

• 操作

  通過三種旋轉方法來實作旋轉，具體影響因素有：

  1. 節點x是父節點p的左孩子還是右孩子
  2. 節點p是不是根節點，如果不是
  3. 節點p是父節點g的左孩子還是右孩子

三種基本操作有：

1. zig

   當p為根節點時，進行zip step操作。

   當x是p的左孩子時，對x右旋。

   當x是p的右孩子時，對x左旋。

2. Zig-Zig

   當p不是根節點，且x和p同為左孩子或右孩子時進行Zig-Zig操作。

   當x和p同為左孩子時，依次将p和x右旋。

   當x和p同為右孩子時，依次将p和x左旋。

3. Zig-Zag

   當p不是根節點，且x和p不同為左孩子或右孩子時，進行Zig-Zag操作。

   當p為左孩子，x為右孩子時，将x左旋後再右旋。

   當p為右孩子，x為左孩子時，将x右旋後再左旋。

以上是我學splay時原po上的

• 下面附上我的代碼和模闆代碼：

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <climits>
#define INF 0xffffff
using namespace std;
class splaytree{
public :
    splaytree();
    ~splaytree();
    int maxx();//最大值
    int minn();//最小值
    void del(int x);//删除節點
    void ins(int x);//插入節點
    int get_front();//找前驅
    int get_behind();//找後繼
private :
    struct node{
    int key;
    node *lch,*rch;
    node(){}
    node(int x):key(x){}
    };
    node *nullnode,*root;//nullnode：空節點
    void left_rotate(node *&x);//左旋
    void right_rotate(node *&x);//右旋
    void splay(node *&root,int x);//旋轉到root
};
int splaytree::minn()
{
    node* p=root;
    while(p->lch!=nullnode)
        p=p->lch;
    splay(root,p->key);
    return p->key;
}
int splaytree::maxx()
{
    node* p=root;
    while(p->rch!=nullnode)
        p=p->rch;
    splay(root,p->key);
    return p->key;
}
splaytree::splaytree()
{
    nullnode=new node;
    nullnode->lch=nullnode;
    nullnode->rch=nullnode;
    root=nullnode;
}
splaytree::~splaytree()
{
    while(root!=nullnode)
        del(maxx());
    delete nullnode;
}
void splaytree::del(int x)
{
    node *newroot;
    splay(root,x);
    if(x!=root->key)
        return;
    if(root->lch==nullnode)
        newroot=root->rch;
    else
    {
        newroot=root->rch;
        splay(newroot,x);
        newroot->rch=root->rch;
    }
    delete root;
    root=newroot;
}
void splaytree::ins(int x)
{
    node* newroot=new node(x);
    if(root==NULL)
    {
        newroot->lch=nullnode;
        newroot->rch=nullnode;
        root=newroot;
        return;
    }
    splay(root,x);
    if(x<root->key)
    {
        newroot->lch=root->lch;
        root->lch=nullnode;
        newroot->rch=root;
        root=newroot;
    }
    else
    {
        newroot->rch=root->rch;
        root->rch=nullnode;
        newroot->lch=root;
        root=newroot;
    }
}
void splaytree::left_rotate(node *&x)
{
    node *y=x->rch;
    x->rch=y->lch;
    y->lch=x;
    x=y;
}
void splaytree::right_rotate(node *&x)
{
    node *y=x->lch;
    x->lch=y->rch;
    y->rch=x;
    x=y;
}
void splaytree::splay(node *&root,int x)
{
    node head,*ltree=&head,*rtree=&head;
    head.lch=nullnode;
    head.rch=nullnode;
    while(x!=root->key)
    {
        if(x<root->key)
        {
            if(root->lch!=nullnode&&x<root->lch->key)
                right_rotate(root);
            if(root->lch==nullnode)
                break;
            rtree->lch=root;
            rtree=root;
            root=root->lch;
        }
        else
        {
            if(root->rch!=nullnode&&x>root->rch->key)
                left_rotate(root);
            if(root->rch==nullnode)
                break;
            ltree->rch=root;
            ltree=root;
            root=root->rch;
        }
    }
    ltree->rch=root->lch;
    root->lch=head.rch;
    rtree->lch=root->rch;
    root->rch=head.lch;
}
int splaytree::get_front()
{
    node* tmp=root->lch;
    if(tmp==nullnode) return INF;
    while(tmp->rch!=nullnode)
        tmp=tmp->rch;
    return root->key-tmp->key;
}
int splaytree::get_behind()
{
    node* tmp=root->rch;
    if(tmp==nullnode) return INF;
    while(tmp->lch!=nullnode)
        tmp=tmp->lch;
    return tmp->key-root->key;
}

           

下面附上原po用模闆寫的代碼

#include <cstdio>
#include <iostream>
using namespace std;

template<typename T>
class SplayTree
{
public:
    SplayTree();
    ~SplayTree();

    void del(const T &x);
    void insert(const T &x);
    const T & max()
    {
        Node * p = root;
        while(p->rch != nullnode)
            p = p->rch;
        splay(root,p->key);
        return p->key;
    }
    const T & min()
    {
        Node * p = root;
        while(p->lch != nullnode)
            p = p->lch;
        splay(root,p->key);
        return p->key;
    }

    struct Node
    {
        T key;
        Node *lch,* rch;
        Node(){}
        Node(const T & x) : key(x){}
    }* nullnode,* root;
    void left_rotate(Node * & x);
    void right_rotate(Node * & x);
    void splay(Node * & root,const T & x);
};
template<typename T>
SplayTree<T>::SplayTree()
{
    nullnode = new Node;
    nullnode->lch = nullnode;
    nullnode->rch = nullnode;
    root = nullnode;
}
template<typename T>
SplayTree<T>::~SplayTree()
{
    while(root != nullnode)
        del(max());
    delete nullnode;
}
template<typename T>
void SplayTree<T>::del(const T & x)
{
    Node * newroot;
    splay(root,x);
    if(x != root->key)
        return;         // No found...

    if(root->lch == nullnode)
        newroot = root->rch;
    else
    {
        newroot = root->rch;
        splay(newroot,x);
        newroot->rch = root->rch;
    }
    delete root;
    root = newroot;
}
template<typename T>
void SplayTree<T>::insert(const T & x)
{
    Node * newroot = new Node(x);
    if(root == NULL)
    {
        newroot->lch = nullnode;
        newroot->rch = nullnode;
        root = newroot;
        return;
    }
    splay(root,x);
    if(x < root->key)
    {
        newroot->lch = root->lch;
        root->lch = nullnode;
        newroot->rch = root;
        root = newroot;
    }
    else
    {
        newroot->rch = root->rch;
        root->rch = nullnode;
        newroot->lch = root;
        root = newroot;
    }
}

template <typename T>
void SplayTree<T>::left_rotate(Node * & x)
{
    Node * y = x->rch;
    x->rch = y->lch;
    y->lch = x;
    x = y;
}

template <typename T>
void SplayTree<T>::right_rotate(Node * & x)
{
    Node * y = x->lch;
    x->lch = y->rch;
    y->rch = x;
    x = y;
}

template <typename T>
void SplayTree<T>::splay(Node * & root,const T & x)
{
    Node head,*ltree = & head,*rtree = & head;
    head.lch = nullnode;
    head.rch = nullnode;
    while(x != root->key)
    {
        if(x < root->key)
        {
            if(root->lch != nullnode && x < root->lch->key)
                right_rotate(root);
            if(root->lch == nullnode)
                break;
            rtree->lch = root;
            rtree = root;
            root = root->lch;
        }
        else
        {
            if(root->rch != nullnode && x > root->rch->key)
                left_rotate(root);
            if(root->rch == nullnode)
                break;
            ltree->rch = root;
            ltree = root;
            root = root->rch;
        }
    }
    ltree->rch = root->lch;
    root->lch = head.rch;
    rtree->lch = root->rch;
    root->rch = head.lch;
}

int main()
{
    SplayTree<int> st;
    st.insert();
    cout << st.root->key << endl;
    st.insert();
    cout << st.root->key << endl;
    st.insert();
    cout << st.root->key << endl;
    st.insert();
    cout << st.root->key << endl;
    st.insert();
    cout << st.root->key << endl;
    st.insert();
    cout << st.root->key << endl;
    return ;
}
           

代碼好長。。。。。。累。。。。