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 if ( !v ) return NULL; BinNodePosi<T> p; BinNodePosi<T> g; //*v的父亲与祖父 0010 while ( ( p = v->parent ) && ( g = p->parent ) ) { //自下而上,反复对*v做双层伸展 0011 BinNodePosi<T> gg = g->parent; //每轮之后*v都以原曾祖父(great-grand parent)为父 0012 if ( IsLChild ( *v ) ) 0013 if ( IsLChild ( *p ) ) { //zig-zig 0014 attachAsLC ( p->rc, g ); attachAsLC ( v->rc, p ); 0015 attachAsRC ( p, g ); attachAsRC ( v, p ); 0016 } else { //zig-zag 0017 attachAsLC ( v->rc, p ); attachAsRC ( g, v->lc ); 0018 attachAsLC ( g, v ); attachAsRC ( v, p ); 0019 } 0020 else if ( IsRChild ( *p ) ) { //zag-zag 0021 attachAsRC ( g, p->lc ); attachAsRC ( p, v->lc ); 0022 attachAsLC ( g, p ); attachAsLC ( p, v ); 0023 } else { //zag-zig 0024 attachAsRC ( p, v->lc ); attachAsLC ( v->rc, g ); 0025 attachAsRC ( v, g ); attachAsLC ( p, v ); 0026 } 0027 if ( !gg ) v->parent = NULL; //若*v原先的曾祖父*gg不存在,则*v现在应为树根 0028 else //否则,*gg此后应该以*v作为左或右孩子 0029 ( g == gg->lc ) ? attachAsLC ( v, gg ) : attachAsRC ( gg, v ); 0030 updateHeight ( g ); updateHeight ( p ); updateHeight ( v ); 0031 } //双层伸展结束时,必有g == NULL,但p可能非空 0032 if ( p = v->parent ) { //若p果真非空,则额外再做一次单旋 0033 if ( IsLChild ( *v ) ) { attachAsLC ( v->rc, p ); attachAsRC ( v, p ); } 0034 else { attachAsRC ( p, v->lc ); attachAsLC ( p, v ); } 0035 updateHeight ( p ); updateHeight ( v ); 0036 } 0037 v->parent = NULL; return v; 0038 } //调整之后新树根应为被伸展的节点,故返回该节点的位置以便上层函数更新树根