這是我的第一篇博文，由于被splay坑得太慘，是以毅然決定以此開博。 蜘蛛快來：伸展樹 解釋splay的文章滿大街都是，但用pascal的畢竟少，是以這是用pascal代碼來解釋的（C++代碼在最後） 知道BST的請自動跳到第6段 要學splay，首先要知道BST（二叉排序樹）的概念 它或是一棵空樹；或者是具有下列性質的二叉樹： （1）若左子樹不空，則左子樹上所有結點的值均小于它的根結點的值； （2）若右子樹不空，則右子樹上所有結點的值均大于它的根結點的值； （3）左、右子樹也分别為二叉排序樹；
BST可以簡單地用遞歸實作，下面是插入節點的操作：
procedure ins(p,k:longint);
begin
if p<a[k] then
if next[k].l=0 then
begin
inc(tot);
next[k].l:=tot;
a[tot]:=p;
end else
ins(p,next[k].l)else
if next[k].r=0 then
begin
inc(tot);
next[k].r:=tot;
a[tot]:=p;
end else
ins(p,next[k].r);
end;
不難看出，裸的BST很容易被卡，雖然期望複雜度是O(log n)，但對付退化成一條鍊的資料就變成O(n). 是以，平衡樹（BBST）應運而生 BBST有treap、splay、AVL、RBT、SBT等等 這裡隻講splay。伸展樹不像AVL，它不保證嚴格的平衡，但是程式設計複雜度大大降低，效率有點似乎萎。但功能很強大，幾乎能實作其他平衡樹的一切功能，是成本效益很高的東西。 基本概念1：旋轉 ①ZIG與ZAG
若B是根節點左節點，則對其ZIG，把B拎起來，拉到根的位置，讓A變成B的孩子，發現B有3個孩子了，就把E作為A的左兒子
顯然，這樣不會違反BST的性質，ZAG就是ZIG的反演。 ②Zig-Zig與Zag-Zag 若節點x的父節點y不是根節點，且x與y同時是各自父節點的左孩子，則進行ZIG-ZIG 若都是右孩子，則進行ZAG-ZAG Zig-Zig：先Zig【y】節點，再Zig【x】節點
Zag-Zag：先Zag【y】節點，再Zag【x】節點 建議讀者自己畫一畫，了解一下。 ③Zig-Zag 與Zag-Zig 若節點x的父節點y不是根節點，x與y中一個是其父節點的左孩子而另一個是其父節點的右孩子，則進行此操作。 這裡的Zig和Zag與Zig-Zig及Zag-Zag裡的不同，這裡的旋轉都是對【x】節點進行的。
有人讀到這裡可能會問，為什麼要定義先旋轉y，再旋轉x的雙旋呢？，都隻對x進行旋轉操作不是更好麼？而且都隻對x旋轉對其他節點相對高度改變小，不正符合了splay把常通路節點提上來的初衷麼？我也有這樣的疑問，但是經過無數資料的測試，定義如是雙旋比隻對x旋轉優了50%，這個Tarjan會證，我不會…… 基本概念②：伸展（splay） 這個概念容易了解，就是對每次被查找、插入等操作的節點用上述方法旋轉到根的位置。 代碼：定義 father數組——》存儲該節點的父節點 son數組——》son[x,1]表示x節點的左兒子,son[x,2]表示x節點的右兒子 Data數組——》存儲節點的值 value數組——》存儲該節點的值出現了幾次 count數組——》count[x]表示以x為根的子樹結點數量 其實用記錄類型寫會更漂亮和友善，但是這樣存儲有些地方可以壓縮代碼，雖然大多數人不喜歡，調試也麻煩，然而為了培養讀者自己寫代碼的能力……（好吧其實是我不想改了） Code：旋轉操作
procedure Rotate(x,w:longint);inline;//x是要旋轉的節點，w=1左旋，w=2右旋
var y:longint;
begin
y:=father[x];
count[y]:=count[y]-count[x]+count[son[x,w]];
count[x]:=count[x]-count[son[x,w]]+count[y];
son[y,3-w]:=son[x,w];//若右旋，将其父節點的左兒子設定為目前節點的右兒子，相反就……
if son[x,w]<>0 then father[son[x,w]]:=y;//設定目前節點兒子的父節點，相反也是……
father[x]:=father[y];
if father[y]<>0 then
if y=son[father[y],1] then son[father[y],1]:=x else son[father[y],2]:=x;
//修改x與其旋轉後父節點的關聯
father[y]:=x;son[x,w]:=y;//設定旋轉後x與y的關系
end;
伸展操作
procedure splay(x:longint);inline;//伸展操作無需多解釋，細心即可
var y:longint;
begin
while father[x]<>0 do
begin
y:=father[x];
if father[y]=0 then
if x=son[y,1]then rotate(x,2)//ZIG
else rotate(x,1)//ZAG
else
if y=son[father[y],1] then
if x=son[y,1]
then begin rotate(y,2);rotate(x,2)end//ZIG-ZIG
else begin rotate(x,1);rotate(x,2)end//ZAG-ZIG
else
if x=son[y,2]
then begin rotate(y,1);rotate(x,1)end//ZAG-ZAG
else begin rotate(x,2);rotate(x,1)end//ZIG-ZAG
end;
root:=x;//x成為根
end;
查找
function search(x,w:longint):longint;inline;//在以x為根的子樹中，w為要查詢的數，傳回節點編号
begin
while data[x]<>w do
begin
if w=data[x] then exit(x);//找到就退出
if w<data[x] then//這裡操作與BST一樣
begin
if son[x,1]=0 then break;
x:=son[x,1];
end else
begin
if son[x,2]=0 then break;
x:=son[x,2];
end
end;
exit(x);
end;
插入
procedure insert(w:longint);inline;
var k,kk:longint;flag:boolean;
begin
if tot=0 then//tot記錄目前樹中的節點總數
begin
inc(tot);
father[1]:=0;count[1]:=1;data[1]:=w;root:=1;value[1]:=1;//root是根的編号
exit;
end;
k:=search(root,w);
if data[k]=w then//如果該數值已存在于樹中，就隻要……
begin
inc(value[k]);kk:=k;
flag:=true;
end else
begin//否則建立節點
inc(tot);
data[tot]:=w;father[tot]:=k;count[tot]:=1;value[tot]:=1;
if data[k]>w then son[k,1]:=tot else son[k,2]:=tot;
flag:=false;
end;
while k<>0 do
begin
inc(count[k]);//更新count值，自己yy一下
k:=father[k];
end;
if flag then splay(kk)else splay(tot);//flag決定伸展哪個節點
end;
求極值（類似于查找，自己yy即可）
function Extreme(x,w:longint):longint;inline;//x是要通路子樹的根,w=1求max，w=2求min
const lala:array[1..2]of longint=(maxlongint,-maxlongint);
var k:longint;
begin
k:=search(x,lala[w]);
Extreme:=data[k];
splay(k);
end;
删除（核心思想即伸展欲删節點，合并左右子樹）
procedure delete(x:longint);inline;//x是要删除的【數值】
var k,y:longint;
begin
k:=search(root,x);
if data[k]<>x then splay(k)//如果此數不在樹中，伸展k
else
begin
splay(k);
if value[k]>1 then begin dec(value[k]);dec(count[k]);end else
if son[k,1]=0 then
begin
y:=son[k,2];
son[k,2]:=0;count[k]:=0;data[k]:=0;value[k]:=0;
root:=y;father[root]:=0;
end else
begin
father[son[k,1]]:=0;//切斷左子樹與根的關聯
y:=Extreme(son[k,1],1);//左子樹中的max
son[root,2]:=son[k,2];//左右子樹合并
count[root]:=count[root]+count[son[k,2]];
if son[root,2]<>0 then father[son[root,2]]:=root;
data[k]:=0;son[k,1]:=0;son[k,2]:=0;value[k]:=0;
end
end
end;//有些賦為0的操作其實可以省略
求前驅後繼
function pred(x:longint):longint;inline;//求前驅
var k:longint;
begin
k:=search(root,x);splay(k);
if data[k]<x then exit(data[k]);
exit(Extreme(son[k,1],1));
end;
function succ(x:longint):longint;inline;//求後繼
var k:longint;
begin
k:=search(root,x);splay(k);
if data[k]>x then exit(data[k]);
exit(Extreme(son[k,2],2));
end;
求第k極值
function kth(x,w:longint):longint;inline;//w=1為求第x小值，w=2為求第x大值
var i:longint;
begin
i:=root;
while not((x>=count[son[i,w]]+1)and(x<=count[son[i,w]]+value[i]))and (i<>0)do
begin
if x>count[son[i,w]]+value[i] then
begin
x:=x-count[son[i,w]]-value[i];
i:=son[i,3-w];
end
else i:=son[i,w];
end;
kth:=i;
splay(i);
end;
求x是第幾大
function findnum(x:longint):longint;inline;
var K:longint;
begin
k:=search(root,x);splay(k);
root:=k;
exit(count[son[k,1]]+1);
end;
我能想到的基本操作大概就這些，最後推薦一道模闆題 in wikioi in BZOJ in tyvj 這題的code就是把上面的過程函數拼起來就行。 然後下面是C++的完整代碼
#include<cstdio>
#include<iostream>
#include <cstdlib>
using namespace std;
int n,root,i,tot,opt,x;
int father[100000],count[100000],data[100000],value[100000];
int son[100000][3];
inline void Rotate(int x,int w)
{
int y;
y=father[x];
count[y]=count[y]-count[x]+count[son[x][w]];
count[x]=count[x]-count[son[x][w]]+count[y];
son[y][3-w]=son[x][w];
if (son[x][w]) father[son[x][w]]=y;
father[x]=father[y];
if (father[y])
if (y==son[father[y]][1]) son[father[y]][1]=x;
else son[father[y]][2]=x;
father[y]=x;
son[x][w]=y;
}
inline void splay(int x)
{
int y;
while (father[x])
{
y=father[x];
if (!father[y])
if (x==son[y][1]) Rotate(x,2);
else Rotate(x,1);
else
if (y==son[father[y]][1])
if (x==son[y][1])
{
Rotate(y,2);Rotate(x,2);
}
else
{
Rotate(x,1);Rotate(x,2);
}
else
if (x==son[y][2])
{
Rotate(y,1);Rotate(x,1);
}
else
{
Rotate(x,2);Rotate(x,1);
}
}
root=x;
}
inline int search(int x,int w)
{
while (data[x]!=w)
{
if (w==data[x]) return x;
if (w<data[x])
{
if (!son[x][1]) break;
x=son[x][1];
}
else
{
if (son[x][2]==0) break;
x=son[x][2];
}
}
return x;
}
inline void insert(int w)
{
int k,kk;bool flag;
if (!tot)
{
tot=1;
father[1]=0;count[1]=1;data[1]=w;root=1;value[1]=1;
return;
}
k=search(root,w);
if (data[k]==w)
{
value[k]++;kk=k;
flag=true;
}
else
{
tot++;
data[tot]=w;
father[tot]=k;
count[tot]=1;
value[tot]=1;
if (data[k]>w) son[k][1]=tot;else son[k][2]=tot;
flag=0;
}
while (k)
{
count[k]++;
k=father[k];
}
if (flag) splay(kk);else splay(tot);
}
inline int Extreme(int x,int w)
{
const int lala[3]={0,2147483647,-2147483647};
int k,tmp;
k=search(x,lala[w]);
tmp=data[k];
splay(k);
return tmp;
}
inline void del(int x)
{
int k,y;
k=search(root,x);
if (data[k]!=x) splay(k);else
{
splay(k);
if (value[k]>1)
{
value[k]--;
count[k]--;
}
else
if (!son[k][1])
{
y=son[k][2];
son[k][2]=0;
count[k]=0;
data[k]=0;
value[k]=0;
root=y;
father[root]=0;
}
else
{
father[son[k][1]]=0;
y=Extreme(son[k][1],1);
son[root][2]=son[k][2];
count[root]=count[root]+count[son[k][2]];
if (son[root][2]!=0) father[son[root][2]]=root;
data[k]=0;son[k][1];son[k][2]=0;
value[k]=0;
}
}
}
inline int pred(int x)
{
int k;
k=search(root,x);
splay(k);
if (data[k]<x) return data[k];
return Extreme(son[k][1],1);
}
inline int succ(int x)
{
int k;
k=search(root,x);
splay(k);
if (data[k]>x) return data[k];
return Extreme(son[k][2],2);
}
inline int kth(int x,int w)
{
int i,tmp;
i=root;
while (!((x>=count[son[i][w]]+1)&&(x<=count[son[i][w]]+value[i]))&&(i!=0))
{
if (x>count[son[i][w]]+value[i])
{
x=x-count[son[i][w]]-value[i];
i=son[i][3-w];
}
else
i=son[i][w];
}
tmp=i;
splay(i);
return tmp;
}
inline int findnum(int x)
{
int k;
k=search(root,x);splay(k);
root=k;
return count[son[k][1]]+1;
}
int main()
{
scanf("%d",&n);
for(i=1;i<=n;i++)
{
if (i==3)
i=3;
scanf("%d%d",&opt,&x);
switch(opt)
{
case 1:insert(x);break;
case 2:del(x);break;
case 3:printf("%d\n",findnum(x));break;
case 4:printf("%d\n",data[kth(x,1)]);break;
case 5:printf("%d\n",pred(x));break;
case 6:printf("%d\n",succ(x));break;
default:break;
}
}
return 0;
}
~~~~~~~~~~~~~~感謝閱讀~~~~~~~~~~~~~~