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