0001 template <typename T> BinNodePosi(T) BinNode<T>::zig() { //˳ʱת 0002 BinNodePosi(T) lChild = lc; 0003 lChild->parent = this->parent; 0004 if ( lChild->parent ) 0005 ( ( this == lChild->parent->rc ) ? lChild->parent->rc : lChild->parent->lc ) = lChild; 0006 lc = lChild->rc; if ( lc ) lc->parent = this; 0007 lChild->rc = this; this->parent = lChild; 0008 // update heights () 0009 height = 1 + max ( stature ( lc ), stature ( rc ) ); 0010 lChild->height = 1 + max ( stature ( lChild->lc ), stature ( lChild->rc ) ); 0011 for ( BinNodePosi(T) x = lChild->parent; x; x = x->parent ) 0012 if ( HeightUpdated( *x ) ) 0013 break; 0014 else 0015 x->height = 1 + max ( stature ( x->lc ), stature ( x->rc ) ); 0016 return lChild; 0017 }