0001 template <typename T> //Splay树伸展算法
0002 BinNodePosi<T> Splay<T>::splay( BinNodePosi<T> v ) { //v为因最新访问而需伸展的节点
0003    BinNodePosi<T> p, g; //v的父亲与祖父
0004    while ( ( p = v->parent ) && ( g = p->parent ) ) { //自下而上，反复对v做双层伸展
0005       BinNodePosi<T> gg = g->parent; //每轮之后v都以原曾祖父（great-grand parent）为父
0006       switch ( ((p == g->rc) << 1) | (v == p->rc) ) { //视p、v的拐向，分四种情况
0007          case 0b00 : //zig-zig
0008             g->attachLc( p->rc ); p->attachLc( v->rc );
0009             p->attachRc( g );     v->attachRc( p );     break;
0010          case 0b01 : //zig-zag
0011             p->attachRc( v->lc ); g->attachLc( v->rc );
0012             v->attachRc( g );     v->attachLc( p );     break;
0013          case 0b10 : //zag-zig
0014             p->attachLc( v->rc ); g->attachRc( v->lc );
0015             v->attachLc( g );     v->attachRc( p );     break;
0016          default : //0b11 ~ zag-zag
0017             g->attachRc( p->lc ); p->attachRc( v->lc );
0018             p->attachLc( g );     v->attachLc( p );     break;
0019       }
0020       if ( !gg ) v->parent = NULL; //若v原先的曾祖父gg不存在，则v现在应为树根
0021       else //否则，gg此后应该以v作为左或右孩子
0022          ( g == gg->lc ) ? gg->attachLc( v ) : gg->attachRc( v );
0023       g->updateHeight(); p->updateHeight(); v->updateHeight();
0024    } //双层伸展结束时，必有g == NULL，但p可能非空
0025    if ( p = v->parent ) { //若p果真是根，则额外再做一次单旋
0026       if ( v == p->lc ) { p->attachLc( v->rc ); v->attachRc( p ); }
0027       else              { p->attachRc( v->lc ); v->attachLc( p ); }
0028       p->updateHeight(); v->updateHeight();
0029    }
0030    v->parent = NULL; return v;
0031 } //调整之后新树根应为被伸展的节点，故返回该节点的位置以便上层函数更新树根