【平衡树】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 ;
}
           

代码好长。。。。。。累。。。。