void splay(Node * &o,int k)
{
int d=o->cmp(k);//cmp函数比较的是k和o->ch[0]->s+1的大小
if(d==1) k-=o->ch[0]->s+1;
if(d!=-1)
{
Node *p=o->ch[d];
int d2=p->cmp(k);
int k2=(d2==0?k:k-p->ch[0]->s-1);
if(d2!=-1)
{
splay(p->ch[d2],k2);
if(d==d2) rotate(o,d^1);/*这个时候已经把k节点伸展到，p->ch[d2]，当d==d2的时候，说明三点
共线，可以先把o向o的d^1方向旋转后，这时o指向是p,然后再让o向相同的方向旋转一次，这个旋转方式和书上说的先旋转x的父亲节点
再旋转x的效果是相同的。
*/
else rotate(o->ch[d],d);/*当d!=d2的时候，说明三点不共线，那么p->ch[d2]旋转到p的位置再然后，然后在以o为节点向d旋转和书
上讲的当三点不共线的时候，旋转方向相反的旋转两次x是相同的效果
*/
}
rotate(o,d^1);
}
}大白书伸展树学习笔记
原文：http://blog.csdn.net/u013491149/article/details/42913483
