Splay tree 的实现
Splay tree 伸展树

1.基本思想：把本次访问的结点通过一系列的旋转操作，变换为根结点，同时要保持树为二叉查找树（BST）。

2.旋转操作:Zig,Zag.(代码注释中有说明)

3.核心操作：Splay(伸展).

4.5个基本操作：

Find(x,&Spt); //查找操作,在Spt中查找值为x的元素,然后把x所在的结点变为Splay tree的根结点

Insert(x,&Spt);//在spt中插入值为x的结点,并把x所在的结点变为Splay tree的根结点

Delete(x,&Spt);//在spt中删除值为x的结点

Join(&s1,&s2);//合并s1,s2两棵Splay tree

Split(x,&s,&s1,&s2);//把值为 x的 结点左右子树分离成2个Splay tree（s1,s2）

5.实现：(参考LRJ的书)

5(1).需要用到的数据结构:

int right[].left[],next[],father[];

DataType data[];

5(2).说明:

right[p],left[p]记录的是结点p的右儿子和左儿子.

father[p]是p 的父亲结点.

next[] 是存放结点的表，手动实现内存分配.

data[p]对应p结点存放的数据.

5(3).实现代码:

#include<iostream>#include<queue>using namespace std;/**** author: yfr** date: 2012-1-10** project: splay tree** reference: LRJ's Book**/#define SIZE 100int Left[SIZE],Right[SIZE],father[SIZE],next[SIZE],data[SIZE];/**基本函数声明 **/void Init();int newnode(int d);void delnode(int p);//********************************void Zig(int &);void Zag(int &);void Splay(int &x,int &s);int BST_find(int x,int p);int SPT_find(int x,int &p);int BST_insert(int x,int &p);void SPT_insert(int x,int &p);void remove(int x,int &p);//********************************int findmax(int &s);int findmin(int &s);int join(int &s1,int &s2);void split(int x,int &s,int &s1,int &s2);//********************************/**       /                             \      p                              x     / \         Zig(x)             / \    x  <>   ----------------->     <>  p   / \                                / \  <> <>                              <> <>**///zig zag 函数 注意指针修改时要成对去修改 void Zig(int &x){     int p = father[x];     Left[p] = Right[x];     if(Right[x])//如果右子树存在      father[Right[x]] = p;      Right[x] = p;     father[x] = father[p];     father[p] = x;     //这步很关键!!      if(data[father[x]]>data[x])     Left[father[x]] = x;     else     Right[father[x]] = x;}/**       /                             \      x                              p     / \         Zag(x)             / \    p  <>   <-----------------     <>  x   / \                                / \  <> <>                              <> <>**/void Zag(int &x){     int p = father[x];     Right[p] = Left[x];     if(Left[x])//如果左子树存在      father[Left[x]] = p;     Left[x] = p;     father[x] = father[p];     father[p] = x;     //这步很关键!!      if(data[father[x]]>data[x])     Left[father[x]] = x;     else     Right[father[x]] = x;}//s是树根，x是待伸长的结点 void Splay(int &x,int &s){    int p;    while(father[x])    {       p = father[x];       if(!father[p])//如果p是根       {           if( x == Left[p])           Zig(x);           else if( x == Right[p])           Zag(x);       }        else//如果不是树根        {           int g = father[p];//祖先结点            if(Left[g]==p && Left[p]==x) //LL的情况           {               Zig(p);               Zig(x);           }           else if(Left[g]==p&&Right[p]==x) //LR的情况           {               Zag(x);               Zig(x);           }           else if(Right[g]==p&&Left[p]==x) //RL的情况           {               Zig(x);               Zag(x);           }           else if(Right[g]==p&&Right[p]==x) //RR的情况           {               Zag(p);               Zag(x);           }       }    }     s = x;//变为树根 }//初始化各容器 void Init(){     memset(Left,0,sizeof(Left));     memset(Right,0,sizeof(Right));     memset(father,0,sizeof(father));     for(int i=0;i<SIZE;i++)     next[i] = i+1;}//模拟内存分配函数 int newnode(int d){    int p = next[0];    next[0] = next[p];    data[p] = d;    return p;}void delnode(int p){     Left[p] = Right[p] = father[p] = 0;     next[p] = next[0];     next[0] = p;}//*********返回插入结点的编号,以便用来Splay**************//int BST_insert(int x,int &p){    if(!p){ p = newnode(x); return p;}    else if(x < data[p])    {         int q = BST_insert(x,Left[p]);         father[Left[p]] = p;//修改父亲指针          return q;    }    else if(x >= data[p])    {         int q = BST_insert(x,Right[p]);         father[Right[p]] = p;//修改父亲指针          return q;    }}//SPT的insert操作 void SPT_insert(int x,int &p){    int q = BST_insert(x,p);    Splay(q,p);//伸展 }int BST_find(int x,int p){    if(!p)return 0;//空树    if(x == data[p]) return p;    else if(x < data[p]) return BST_find(x,Left[p]);    else return BST_find(x,Right[p]); }int SPT_find(int x,int &s){    int q = BST_find(x,s);    if(q)//如果查找成功     Splay(q,s);    return q;}int findmax(int &s){      int p = s;      while(Right[p]) p = Right[p];      Splay(p,s);      return p;}int findmin(int &s){      int p = s;      while(Left[p]) p = Left[p];      Splay(p,s);      return p;}/*******************************************************/int join(int &s1,int &s2){    father[s1] = father[s2] = 0;//断开与公共先祖结点的连接 ,此步很关键     if(!s1) return s2;    if(!s2) return s1;    int q = findmax(s1);    Right[s1] = s2;    father[s2] = s1;    return s1;}void split(int x,int &s,int &s1,int &s2){     int p = SPT_find(x,s);     s1 = Left[p];     s2 = Right[p];}void remove(int x,int &p){     int q = SPT_find(x,p);     if(q){//如果找到了x      int temp = p;     p = join(Left[p],Right[p]);     delnode(temp);     }}/****************************************************************///辅助函数 void order(int p){   if(!p)return;   order(Left[p]);   cout<<data[p]<<endl;   order(Right[p]);}void bfs(int p){   if(!p)return;   queue<int> q;   q.push(p);   while(!q.empty())   {      int v = q.front();      q.pop();      if(Left[v]) q.push(Left[v]);      if(Right[v]) q.push(Right[v]);      cout<<data[v]<<endl;   }}int main(){    freopen("dataout.txt","w",stdout);    Init();    int ROOT = 0;    SPT_insert(12,ROOT);//build SPT    SPT_insert(8,ROOT);    SPT_insert(2,ROOT);    SPT_insert(7,ROOT);    SPT_insert(13,ROOT);    remove(13,ROOT);    order(ROOT);    cout<<"--------------"<<endl;    bfs(ROOT);    cout<<"-----------"<<endl;    cout<<father[ROOT]<<endl;    cout<<"------------"<<endl;    int s1,s2;    split(7,ROOT,s1,s2);    bfs(s1);    cout<<"---------"<<endl;    bfs(s2);    return 0;}