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 100
int 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;
}