0001 template <typename NodePosi> inline //在节点*p与*lc(可能为空)之间建立父(左)子关系 0002 void attachAsLChild ( NodePosi p, NodePosi lc ) { p->lc = lc; if ( lc ) lc->parent = p; } 0003 0004 template <typename NodePosi> inline //在节点*p与*rc(可能为空)之间建立父(右)子关系 0005 void attachAsRChild ( 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 attachAsLChild ( g, p->rc ); attachAsLChild ( p, v->rc ); 0015 attachAsRChild ( p, g ); attachAsRChild ( v, p ); 0016 } else { //zig-zag 0017 attachAsLChild ( p, v->rc ); attachAsRChild ( g, v->lc ); 0018 attachAsLChild ( v, g ); attachAsRChild ( v, p ); 0019 } 0020 else if ( IsRChild ( *p ) ) { //zag-zag 0021 attachAsRChild ( g, p->lc ); attachAsRChild ( p, v->lc ); 0022 attachAsLChild ( p, g ); attachAsLChild ( v, p ); 0023 } else { //zag-zig 0024 attachAsRChild ( p, v->lc ); attachAsLChild ( g, v->rc ); 0025 attachAsRChild ( v, g ); attachAsLChild ( v, p ); 0026 } 0027 if ( !gg ) v->parent = NULL; //若*v原先的曾祖父*gg不存在,则*v现在应为树根 0028 else //否则,*gg此后应该以*v作为左或右孩子 0029 ( g == gg->lc ) ? attachAsLChild ( gg, v ) : attachAsRChild ( gg, v ); 0030 updateHeight ( g ); updateHeight ( p ); updateHeight ( v ); 0031 } //双层伸展结束时,必有g == NULL,但p可能非空 0032 if ( p = v->parent ) { //若p果真非空,则额外再做一次单旋 0033 if ( IsLChild ( *v ) ) { attachAsLChild ( p, v->rc ); attachAsRChild ( v, p ); } 0034 else { attachAsRChild ( p, v->lc ); attachAsLChild ( v, p ); } 0035 updateHeight ( p ); updateHeight ( v ); 0036 } 0037 v->parent = NULL; return v; 0038 } //调整之后新树根应为被伸展的节点,故返回该节点的位置以便上层函数更新树根