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