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 트 리 합병
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;
}